FOLLY: AtomicHashMap














































FOLLY: AtomicHashMap



folly/AtomicHashmap.h

folly/AtomicHashmap.h introduces a synchronized UnorderedAssociativeContainer implementation designed for extreme performance and good memory usage properties.

 Iteration is wait-free, there is minimal memory overhead, insert has key-level lock granularity and permanent 32-bit ids can be used.

 

Limitations

The space for erased elements cannot be reclaimed.

Only supports 32 or 64 bit keys.

Growth beyond initialization reduces performance.

Must manage synchronization externally in order to modify values in the map after insertion

 

Unique Features

AtomicHashMap grows by chaining additional slabs, so elements never need to be moved.

Unique 32-bit ids can be used to reference elements in the map via iterator::getIndex(). This can be helpful to save memory in the rest of the application by replacing 64-bit pointers or keys.

Iterators are never invalidated.

 

Implementation

 Only one AHA is created on initialization, and additional submaps are appended if the first one gets full. If the AHM grows, there will be multiple submaps that must be probed in series to find a given key. More the growth, more number of submaps will be chained, and the slower it will get.

 If the initial size estimate is good, only one submap will ever be created and performance will be optimal.

AtomicHashArray is a fixed-size probing hash map. In it hash collisions are resolved by checking subsequent elements.

The algorithm is simple - when inserting, the key is hash-mod'ed to an offset, and that element-key is atomically compare-and-swap'ed with the locked key value. If successful, the value is written and the element-key is unlocked by setting it to the input key value. If the compare fails, the next element is tried until success or the map is full.

Finds are even simpler. The key is hash-mod'ed to an offset, and the element-key is examined. If it is the same as the input key, the reference is returned, if it's the empty key, failure is returned, otherwise the next key is tried.

Erase is done by finding the key, then compare-and-swap'ing the element-key with the reserved erased key value. If the swap succeeds, return success, otherwise return failure (the element was erased by a competing thread). If the key does not exist, return failure.


Comments