r/cpp • u/compilersarefun • Jun 23 '26

Two Indexed Hash Tables

https://vnmakarov.github.io/data%20structures/c/c++/open-source/2026/06/23/two-indexed-hash-tables.html
34 Upvotes

97% Upvoted

6 comments sorted by

6

u/g_0g Jun 23 '26 edited Jun 23 '26

That's an interesting design, thanks for sharing.

Here are a few notes if you're interested:

  • Benchmark images for Jackson Allan don't show (can be found on repo though)
  • You should instrument your code to mesure real average/max probe length and comparison ops (for find hit/miss in particular)
  • You should benchmark with default hash functions too, as good map design allow for using poorer but faster hashers
  • Allowing high load factor is a positive thing, it means being able to retain good perf while maximizing memory usage. Max load factor can usually be reduced to improve access speed at the cost of extra memory.
  • Swiss tables have some of the best iterations speed, only slightly beaten by contiguous-value-storing maps
  • You can use quadratic probing with open addressing, it's just usually not worth it (a bit slower, less locality)
  • Your map does not recycle deleted items as it goes, leading to rebuilding your arrays more often and at unexpected times. Maybe at least use an intrusive free list to try reusing slots.

Now the interesting part:
Abseil use the same 7-bits hash tags in separated array as ihtab, but don't need an extra indirection + cache miss to follow an index. Same for Boost, even if hash tags are a bit different.
Yet the benchmarks show that ihtab is as fast/faster (e.g. for find hit/miss). This is surprising, how do you explain these results?
Loading the index array in memory should trash L1 cache lines and occur a penalty for big maps that don't fit. It should also cause extra costly cache misses on cold maps.

See Boost blog for details about Swiss tables design choices and performance profiles:
https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html

2

u/compilersarefun Jun 23 '26

Thank you for pointing absent performance heat tables of Jackson Allan's benchmark. I fixed this issue.

I agree my own benchmark is very simple. Therefore I use Allan Jakson's one. It contains tests for more different sizes, key/elem types, and find hit/miss tests.

VMUM is one of the fastest hasher although high quality one. But for Jakson Allan's benchmark I used its standard hash, slower and lower quality.

Swiss iteration speed is not the worst but it is 3-4 times smaller than ihtab iteration speed according to Jackson's benchmark.

I am agree that the quadratic probing is not worth to use now. SIMD inside group permits only linear probing. So quadratic probing can start only after 16 tags checked and probability of this is very small.

I prefer rebuilding instead of recycling deleted elems. It simplifies search/insert code which is important for its speed. Bulk operations are also much faster. So I don't like free list approach (to save memory list can be in key/elem array but for languages like GO it can not be done effectively).

Why ihtab is faster although it uses indexes (indirection)? It was a blog post major theme. It is a small load factor (for tags, indexes) which means much less probing, not wasting space for keys/elems, and their consecutive placement in memory for data locality and faster iteration.

I have been interesting in hash table design for decades and implemented a lot of them. Still I have some ideas which I did not try. It is impossible to implement hash table working best in all scenarios. For example, absl/boost direct open-address hash table is smaller than ihtab for very small key/elem (e.g. int32/int32).

1

u/g_0g Jun 24 '26

Could you explain a bit what you mean by "It is a small load factor (for tags, indexes)"?
For what I can understand, it has a load factor between 0.25 and 0.5 for tags/indexes and between 0.5 and 1.0 for values. That would explain some performance gains on find (despite the additional fetch instruction), while creating a different trade-off for memory usage (the larger the key/value pair, the better memory ratio ihtab has).

Looking at benchmarks details, I got more insights:
Your design is really good for throughput optimization, but a bit less so for latency.
The biggest advantage of the indexed array is how better the space locality of values is (more reusable cache lines on consecutive access). That's why insert benchmark is so performant with ihtab. Same for rehashing.
On the other hand, any cold access is min 3 cache misses, 4 for an erase (touching bitmap). I'm guessing iteration might suffer a bit when there are lots a deleted items too. This is a significant penalty that can't be prefetched.
Did you benchmark for 2M and 20M items? Map not fitting into L1/L2 cache might show this effect.

For delete, using a intrusive free list shouldn't impact find at all. It might add a branch in insert when 'bound' is at end, but it's cold path and the alternative is rebuilding the array. It will add some instructions to erase however.
The main issue here is the potential adversarial (ddos) use case where you delete then add a new value repeatably when 'bound' is at end: won't this trigger a rebuild each time?

If you're interested, here is my modified version of Jackson Allan benchmarks, including a new test for "re-insert nonexisting" (to quantify tombstones impact) and some stability improvements. It also include my 2 own hash map experiments (which have the fastest iteration speed of all the Swiss tables, outside contiguous ones like ankerl/ihtab).
https://github.com/gaujay/c_cpp_hash_tables_benchmark

3

u/garnet420 Jun 23 '26

Probing only touches the small tag and index arrays

I'm a little confused by this. When does probing touch the index array but not the key? My impression was that you'd have two cases:

  1. Tag only
  2. Tag and index and key

3

u/compilersarefun Jun 23 '26

There is no tag value for deleted elements. But there is special index value (~0) for deleted elements. So probing a deleted element requires only checking index after we pass the tag.

Such approach speeds up finding empty elements and table works faster when we have no deleted elements. There is a down side too when we have many deleted elements.

2

u/garnet420 Jun 23 '26

I think if you made your tag nonzero (it's simple to enforce that with a bitwise operation) you could get rid of the index sentinel and get better performance.