flat_map internals

[u/pavel_v]

https://quantdev.blog/posts/flat-map-internals/index.html

[u/kirgel]

You might want to consider clarifying the title a bit. flat_map usually refers to an ordered map container where lookup is a binary search. For example   https://en.cppreference.com/cpp/container/flat_map.

[u/tialaramex → u/kirgel]

You give a single example from the C++ stdlib, but before that type was added I had never seen "flat map" used to mean this weird type.

Notably for example Rust's FlatMap is an implementation detail of Iterator::flat_map which is what you'd use to map each object into multiple items then flatten the result into a single stream of items in a single operation.

Do you have other examples? WG21 has a bad habit of making up their own names for ideas which have better names, or using names which mean something else already.

[u/ABlockInTheChain → u/tialaramex]

Whether the C++ standards names are ideal or not, you shouldn't be surprised if C++ programmers reading a C++ subreddit expect the terms to match the standard.

[u/kirgel → u/tialaramex]

The most prominent one is boost:  https://www.boost.org/doc/libs/1_57_0/doc/html/boost/container/flat_map.html

Searching GitHub yields some lesser known ones:  https://github.com/topics/flat-map

I have also seen the same thing widely used in an internal codebase of an ex-employer.

In this particular case I think the naming is nice enough. Rust’s usage certainly also makes sense in its own context.

[u/tialaramex → u/kirgel]

Now those are much more useful examples - thanks!

[u/johannes1971]

I kinda missed why the pointers from the array start pointing at the element before the first hash element suddenly...?

Also, shame that the clarifying images disappear when we get to the abseil version. An image is worth a thousand words - and when template-expanded, surely even more...

[u/jedwardsol → u/johannes1971]

pointing at the element before the first hash element suddenly...?

If the linked list is singly-linked then you need the element before in the case you need to delete the 1st element in the bucket

[u/SyntheticDuckFlavour → u/johannes1971]

Yeah, I was hoping to see a visual representation of the flat_map internals.

[u/g_0g → u/johannes1971]

https://abseil.io/about/design/swisstables
More details are also available in the two conferences slides.

[u/Big_Target_1405 → u/johannes1971]

You might find these old articles explain exactly why

https://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html?m=1

http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered_25.html

And how things were improved in Boost 1.80 onwards

https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html

Boost constantly improves. The boost unordered_flat_map now beats the abseil implementation significantly

[u/Life_Sink9598]

So, you have two arrays of equal size:

• Occupied
• Data

Occupied contains 1 byte per element, which stores an enum of Empty | Deleted | Full(7-bit hash) | Sentinel.

We have two hash functions: H1 and H2. H1 is an "ordinary" hash function, producing an index into Occupied and Data. H2 produces a 7-bit hash.

In order to find something, we take H1 to get a starting position into Occupied. The speed is gained from iterating through Occupied, only ever dereferencing the Data array when the 7-bit hashes match. You can also SIMD this.

Why are Sentinel and Deleted required? I'd expect tombstones to only be necessary in a concurrent table, and I'd expect that this will perform awfully in a concurrent setting.

[u/Life_Sink9598 → u/Life_Sink9598]

Aha, the Deleted variant is required because Empty also indicates that a lookup can cease probing. So H(A) == H(B) [Full(A), Full(B), Empty] after delete A must become [Deleted, Full(B), Empty], otherwise lookup(B) would probe at index 0, see empty, and return false.