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.

Sun Java on Ubuntu 12

Sun Java is no longer available on Ubuntu packaging due to licensing issues with Oracle. OpenJDK is provided instead. One solution to this is to use the sun-update-jre package via Dunisoft. However, this did not meet my requirements as the package does not include javac.

My solution was to extract the bin file provided by Sun/Oracle by following the steps here. Do note to fix your symlinks for javadoc, javah and javap.

sudo update-alternatives --install /usr/bin/javac javac /usr/lib/jvm/jdk1.6.0_32/bin/javac 1
sudo update-alternatives --install /usr/bin/java java /usr/lib/jvm/jdk1.6.0_32/bin/java 1
sudo update-alternatives --install /usr/bin/javaws javaws /usr/lib/jvm/jdk1.6.0_32/bin/javaws 1
sudo update-alternatives --install /usr/bin/javadoc javadoc /usr/lib/jvm/jdk1.6.0_32/bin/javadoc 1
sudo update-alternatives --install /usr/bin/javah javah /usr/lib/jvm/jdk1.6.0_32/bin/javah 1
sudo update-alternatives --install /usr/bin/javap javap /usr/lib/jvm/jdk1.6.0_32/bin/javap 1

sudo update-alternatives --config javac
sudo update-alternatives --config java
sudo update-alternatives --config javaws
sudo update-alternatives --config javadoc
sudo update-alternatives --config javah
sudo update-alternatives --config javap