Component of the Week #17: bdlc_flathashset and bdlc_flathashmap

Summary:

  • Provide efficient, open-addressed, unordered set/map containers.

The bdlc_flathashset and bdlc_flathashmap components define class templates, bdlc::FlatHashSet and bdlc::FlatHashMap respectively, that implement an open-addressed unordered set/map of items having unique values. These components offer efficient alternatives to bsl::unordered_set and bsl::unordered_map with improved performance characteristics on certain platforms and reduced memory usage across all platforms (and fully support BDE-style allocators).

One of the key advantages of bdlc::FlatHashSet/Map is their improved performance on Intel platforms (Linux, Windows, and pre-ARM Macs), where they generally exhibit better performance than bsl::unordered_set/map due to vectorized implementations being available.

For example, on a Windows machine with an Intel Xeon Gold processor, these components perform find operations 170% faster when the key is present, and “only” 70% faster when searching for missing keys. On a Linux machine with an Intel Xeon Cascade Lake processor, those numbers are even better at 240% and 160% respectively.

Note that there is a performance penalty on non-x86 platforms, such as ARM MacOs or Solaris Sparc. On these platforms the components’ implementations do not yet take advantage of vectorized instruction sets. For example, MacOS M4 Pro these components may be 60%-70% slower on find operations than bsl::unordered_set and bsl::unordered_map. There is a similar performance penalty on Sparc.

The bdlc::FlatHashSet/Map containers use significantly less memory than the bsl::unordered_set/map equivalents across all platforms.

When considering bdlc::FlatHashSet or bdlc::FlatHashMap for your application, remember these key points:

  1. They offer better performance and lower memory usage than bsl::unordered_set (or map) on Intel platforms.

  2. They currently suffer from worse performance than the bsl::unordered_* equivalent on non-Intel platforms (but still benefit from lower memory usage there).

  3. All iterators and references are invalidated when a container’s capacity changes.

  4. The containers automatically manage their load factor and resizing.

  5. They are allocator-aware and follow BDE style for allocator usage.

For more details, see the