FB Folly's Atomic Hashmap

Recently, I watched Spencer Ahrens's talk on Folly's AtomicHashMap at the Facebook C++ conference. I thought it was pretty cool and was definitely impressed by the tricks that were used to achieved lock-free and wait-free hash map operations. The AtomicHashMap is 1.3x - 5x faster than boost.

Here are the slides and video.

Some cool takeaways:

• Open addressing style
• Growing hashmap: create another submap instead of rehash
• Compare and swap for insert
• ThreadCachedInt
• Thread Local Storage
• Microsharding when atomic inc is a bottleneck
• Modulus is too slow for calculating the hash: so take mod on next power of two and use bit ops
• What's the optimal size? Branch misprediction becomes a factor too.