folly/docs/AtomicHashMap.md

   1 `folly/AtomicHashmap.h`
   2 ----------------------
   3
   4 `folly/AtomicHashmap.h` introduces a synchronized UnorderedAssociativeContainer
   5 implementation designed for extreme performance in heavily multithreaded
   6 environments (about 2-5x faster than tbb::concurrent_hash_map) and good memory
   7 usage properties.  Find and iteration are wait-free, insert has key-level lock
   8 granularity, there is minimal memory overhead, and permanent 32-bit ids can be
   9 used to reference each element.
  10
  11
  12 ### Limitations
  13 ***
  14
  15 Although it can provide extreme performance, AtomicHashmap has some unique
  16 limitations as well.
  17
  18 * The space for erased elements cannot be reclaimed (they are tombstoned
  19 forever) so it's generally not a good idea to use this if you're erasing things
  20 a lot.
  21
  22 * Only supports 32 or 64 bit keys - this is because they must be atomically
  23 compare-and-swap'ed.
  24
  25 * Growth beyond initialization reduces performance - if you don't know
  26 the approximate number of elements you'll be inserting into the map, you
  27 probably shouldn't use this class.
  28
  29 * Must manage synchronization externally in order to modify values in the map
  30 after insertion.  Lock pools are a common way to do this, or you may
  31 consider using `folly::PackedSyncPtr<T>` as your `ValueT`.
  32
  33 * Must define special reserved key values for empty, erased, and locked
  34 elements.
  35
  36 For a complete list of limitations and departures from the
  37 UnorderedAssociativeContainer concept, see `folly/AtomicHashMap.h`
  38
  39
  40 ### Unique Features
  41 ***
  42
  43 * `value_type` references remain valid as long as the map itself.  Note this is
  44 not true for most other probing hash maps which will move elements when
  45 rehashing, which is necessary for them to grow.  AtomicHashMap grows by chaining
  46 additional slabs, so elements never need to be moved.
  47
  48 * Unique 32-bit ids can be used to reference elements in the map via
  49 `iterator::getIndex()`.  This can be helpful to save memory in the rest of the
  50 application by replacing 64-bit pointers or keys.
  51
  52 * Iterators are never invalidated.  This means you can iterate through the map
  53 while simultaneously inserting and erasing.  This is particularly useful for
  54 non-blocking map serialization.
  55
  56
  57 ### Usage
  58 ***
  59
  60 Usage is similar to most maps, although note the conspicuous lack of operator[]
  61 which encourages non thread-safe access patterns.
  62
  63 Below is a synchronized key counter implementation that allows the counter
  64 values to be incremented in parallel with serializing all the values to a
  65 string.
  66
  67 ```Cpp
  68    class Counters {
  69     private:
  70      AtomicHashMap<int64_t,int64_t> ahm;
  71
  72     public:
  73      explicit Counters(size_t numCounters) : ahm(numCounters) {}
  74
  75      void increment(int64_t obj_id) {
  76        auto ret = ahm.insert(make_pair(obj_id, 1));
  77        if (!ret.second) {
  78          // obj_id already exists, increment
  79          NoBarrier_AtomicIncrement(&ret.first->second, 1);
  80        }
  81      }
  82
  83      int64_t getValue(int64_t obj_id) {
  84        auto ret = ahm.find(obj_id);
  85        return ret != ahm.end() ? ret->second : 0;
  86      }
  87
  88      // Serialize the counters without blocking increments
  89      string toString() {
  90        string ret = "{\n";
  91        ret.reserve(ahm.size() * 32);
  92        for (const auto& e : ahm) {
  93          ret += folly::to<string>(
  94            "  [", e.first, ":", NoBarrier_Load(&e.second), "]\n");
  95        }
  96        ret += "}\n";
  97        return ret;
  98      }
  99    };
 100 ```
 101
 102 ### Implementation
 103 ***
 104
 105 AtomicHashMap is a composition of AtomicHashArray submaps, which implement the
 106 meat of the functionality.  Only one AHA is created on initialization, and
 107 additional submaps are appended if the first one gets full.  If the AHM grows,
 108 there will be multiple submaps that must be probed in series to find a given
 109 key.  The more growth, the more submaps will be chained, and the slower it will
 110 get.  If the initial size estimate is good, only one submap will ever be created
 111 and performance will be optimal.
 112
 113 AtomicHashArray is a fixed-size probing hash map (also referred to as an open
 114 addressed hash map) where hash collisions are resolved by checking subsequent
 115 elements.  This means that they can be allocated in slabs as arrays of
 116 value_type elements, have excellent cache performance, and have no memory
 117 overhead from storing pointers.
 118
 119 The algorithm is simple - when inserting, the key is hash-mod'ed to an offset,
 120 and that element-key is atomically compare-and-swap'ed with the locked key
 121 value.  If successful, the value is written and the element-key is unlocked by
 122 setting it to the input key value.  If the compare fails, the next element is
 123 tried until success or the map is full.
 124
 125 Finds are even simpler.  The key is hash-mod'ed to an offset, and the
 126 element-key is examined.  If it is the same as the input key, the reference is
 127 returned, if it's the empty key, failure is returned, otherwise the next key is
 128 tried.  This can be done wait-free without any atomic instructions because the
 129 elements are always in a valid state.
 130
 131 Erase is done by finding the key, then compare-and-swap'ing the element-key with
 132 the reserved erased key value.  If the swap succeeds, return success, otherwise
 133 return failure (the element was erased by a competing thread).  If the key does
 134 not exist, return failure.