Rehashing Hash Tables And Associative Containers - Eduardo Madrid - CppNow 2022

Slides: https://github.com/boostcon
CppNow Website: https://www.cppnow.org​
CppNow Twitter: @CppNow​
---

Rehashing Hash Tables And Associative Containers - Eduardo Madrid - CppNow 2022

One might think anything about mapping has been discussed twice already; however, because of the powers of Generic Programming we keep finding improvements, even substantial, both in terms of performance and modeling power.

In this presentation we will describe three avenues of improvement we think are novel, and report on their success after having been applied to a large codebase of an application used all over the world.

These are:

1. Opportunities unique to Generic Programming to model associative containers
2. Performance improvement, constexpr facilitation using a different API design to that of the standard map and unordered_map
3. An easy to implement mechanism for compile-time or constexpr "perfect hash tables"

1: The association between a key type and a mapped type can begin as a simple std::vector in which the key type is the index, for example if the set of indices is "dense"; if the application needs change, the good news is we have almost a continuum of data structures already implemented in libraries to choose from, to represent the mapping with optimal support for the new needs, including hash tables, red-black trees, b-trees, tries, Boost's "flat maps", multi-index, cache friendly search maps. The bad news is we don't have a more abstract notion of the association of a key type and a mapped/value type than specific containers, then the evolution of mapping needs in an application typically requires substantial refactoring and re-validation.

What can we do about this? I believe only C++ allows the expression of a very abstract concept such as the mapping between key and value in a way that allows specific realizations of the concept, specific data structures, to work with the same efficiency as they would alone by themselves. We have implemented that missing more abstract notion, we call it "Lookup", we will show how this abstraction decouples the real lookup or mapping needs from the specific implementation choices, and see how specific data structures such as boost::flat_map suffer from operating on two different levels of abstraction. "Lookup" is akin to other container adapters such as "stack" in that it relies on specific data structures but providing a more abstract API.

"stack" is comparatively a very simple container adapter, there are many more things to consider when abstracting key-value mapping, including invariants, algorithms, configuration parameters; we will show how we successfully applied the "expression style" techniques described last year in this conference by my team mate Oleksandr Bacherikov but to the subject of mapping/associative containers.

2: There are several deficiencies in the design of the standard mapping containers, including that they require the key and mapped value to be stored in std::pair, which is not optimal because most use cases require using just the keys far more often than the values, for example, just determining if a key is in the map; then this storage layout can become a significant performance inefficiency. We have made associative containers in which the keys and the mapped values are stored separately; we will detail the consequences and recommendations for alternatives and inter-operation with existing libraries.

3: Another deficiency in the standard is that there is no way to express a hashing function that can be called in two or more "phases". This is a good opportunity to illustrate principles with practical examples: we will put together all of the topics discussed by making a constexpr "perfect hash table" that is easy to make if the hash function allows invocation in phases, like the FNV hashing algorithm, and this will illustrate the benefits of the decoupling provided by "Lookup".
---

Eduardo Madrid
.
Tech Lead at Snap, Inc., helping performance on augmented reality of the Snapchat app. Author of open source libraries and components such as the Zoo type-erasure framework. Prior experience at Fintech, including automated trading. Several times presenter at CPPCon, C++ Now, C++ London
---

Videos Filmed & Edited By Bash Films https://bashfilms.com/
YouTube Channel Managed By Digital Medium Ltd: https://events.digital-medium.co.uk

#Boost​ #Cpp​ #CppNow​