Tuesday, June 26, 2012

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.

No comments: