folly/AtomicHashArray.h

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /**
  18  *  AtomicHashArray is the building block for AtomicHashMap.  It provides the
  19  *  core lock-free functionality, but is limitted by the fact that it cannot
  20  *  grow past it's initialization size and is a little more awkward (no public
  21  *  constructor, for example).  If you're confident that you won't run out of
  22  *  space, don't mind the awkardness, and really need bare-metal performance,
  23  *  feel free to use AHA directly.
  24  *
  25  *  Check out AtomicHashMap.h for more thorough documentation on perf and
  26  *  general pros and cons relative to other hash maps.
  27  *
  28  *  @author Spencer Ahrens <sahrens@fb.com>
  29  *  @author Jordan DeLong <delong.j@fb.com>
  30  */
  31
  32 #ifndef FOLLY_ATOMICHASHARRAY_H_
  33 #define FOLLY_ATOMICHASHARRAY_H_
  34
  35 #include <atomic>
  36
  37 #include <boost/iterator/iterator_facade.hpp>
  38 #include <boost/noncopyable.hpp>
  39
  40 #include <folly/Hash.h>
  41 #include <folly/ThreadCachedInt.h>
  42
  43 namespace folly {
  44
  45 struct AtomicHashArrayLinearProbeFcn
  46 {
  47   inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
  48     idx += 1; // linear probing
  49
  50     // Avoid modulus because it's slow
  51     return LIKELY(idx < capacity) ? idx : (idx - capacity);
  52   }
  53 };
  54
  55 struct AtomicHashArrayQuadraticProbeFcn
  56 {
  57   inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
  58     idx += numProbes; // quadratic probing
  59
  60     // Avoid modulus because it's slow
  61     return LIKELY(idx < capacity) ? idx : (idx - capacity);
  62   }
  63 };
  64
  65 template <class KeyT, class ValueT,
  66           class HashFcn = std::hash<KeyT>,
  67           class EqualFcn = std::equal_to<KeyT>,
  68           class Allocator = std::allocator<char>,
  69           class ProbeFcn = AtomicHashArrayLinearProbeFcn>
  70 class AtomicHashMap;
  71
  72 template <class KeyT, class ValueT,
  73           class HashFcn = std::hash<KeyT>,
  74           class EqualFcn = std::equal_to<KeyT>,
  75           class Allocator = std::allocator<char>,
  76           class ProbeFcn = AtomicHashArrayLinearProbeFcn>
  77 class AtomicHashArray : boost::noncopyable {
  78   static_assert((std::is_convertible<KeyT,int32_t>::value ||
  79                  std::is_convertible<KeyT,int64_t>::value ||
  80                  std::is_convertible<KeyT,const void*>::value),
  81              "You are trying to use AtomicHashArray with disallowed key "
  82              "types.  You must use atomically compare-and-swappable integer "
  83              "keys, or a different container class.");
  84  public:
  85   typedef KeyT                key_type;
  86   typedef ValueT              mapped_type;
  87   typedef std::pair<const KeyT, ValueT> value_type;
  88   typedef std::size_t         size_type;
  89   typedef std::ptrdiff_t      difference_type;
  90   typedef value_type&         reference;
  91   typedef const value_type&   const_reference;
  92   typedef value_type*         pointer;
  93   typedef const value_type*   const_pointer;
  94
  95   const size_t  capacity_;
  96   const size_t  maxEntries_;
  97   const KeyT    kEmptyKey_;
  98   const KeyT    kLockedKey_;
  99   const KeyT    kErasedKey_;
 100
 101   template<class ContT, class IterVal>
 102   struct aha_iterator;
 103
 104   typedef aha_iterator<const AtomicHashArray,const value_type> const_iterator;
 105   typedef aha_iterator<AtomicHashArray,value_type> iterator;
 106
 107   // You really shouldn't need this if you use the SmartPtr provided by create,
 108   // but if you really want to do something crazy like stick the released
 109   // pointer into a DescriminatedPtr or something, you'll need this to clean up
 110   // after yourself.
 111   static void destroy(AtomicHashArray*);
 112
 113  private:
 114   const size_t  kAnchorMask_;
 115
 116   struct Deleter {
 117     void operator()(AtomicHashArray* ptr) {
 118       AtomicHashArray::destroy(ptr);
 119     }
 120   };
 121
 122  public:
 123   typedef std::unique_ptr<AtomicHashArray, Deleter> SmartPtr;
 124
 125   /*
 126    * create --
 127    *
 128    *   Creates AtomicHashArray objects.  Use instead of constructor/destructor.
 129    *
 130    *   We do things this way in order to avoid the perf penalty of a second
 131    *   pointer indirection when composing these into AtomicHashMap, which needs
 132    *   to store an array of pointers so that it can perform atomic operations on
 133    *   them when growing.
 134    *
 135    *   Instead of a mess of arguments, we take a max size and a Config struct to
 136    *   simulate named ctor parameters.  The Config struct has sensible defaults
 137    *   for everything, but is overloaded - if you specify a positive capacity,
 138    *   that will be used directly instead of computing it based on
 139    *   maxLoadFactor.
 140    *
 141    *   Create returns an AHA::SmartPtr which is a unique_ptr with a custom
 142    *   deleter to make sure everything is cleaned up properly.
 143    */
 144   struct Config {
 145     KeyT   emptyKey;
 146     KeyT   lockedKey;
 147     KeyT   erasedKey;
 148     double maxLoadFactor;
 149     double growthFactor;
 150     int    entryCountThreadCacheSize;
 151     size_t capacity; // if positive, overrides maxLoadFactor
 152
 153   public:
 154     //  Cannot have constexpr ctor because some compilers rightly complain.
 155     Config() : emptyKey((KeyT)-1),
 156                lockedKey((KeyT)-2),
 157                erasedKey((KeyT)-3),
 158                maxLoadFactor(0.8),
 159                growthFactor(-1),
 160                entryCountThreadCacheSize(1000),
 161                capacity(0) {}
 162   };
 163
 164   //  Cannot have pre-instantiated const Config instance because of SIOF.
 165   static SmartPtr create(size_t maxSize, const Config& c = Config());
 166
 167   iterator find(KeyT k) {
 168     return iterator(this, findInternal(k).idx);
 169   }
 170   const_iterator find(KeyT k) const {
 171     return const_cast<AtomicHashArray*>(this)->find(k);
 172   }
 173
 174   /*
 175    * insert --
 176    *
 177    *   Returns a pair with iterator to the element at r.first and bool success.
 178    *   Retrieve the index with ret.first.getIndex().
 179    *
 180    *   Fails on key collision (does not overwrite) or if map becomes
 181    *   full, at which point no element is inserted, iterator is set to end(),
 182    *   and success is set false.  On collisions, success is set false, but the
 183    *   iterator is set to the existing entry.
 184    */
 185   std::pair<iterator,bool> insert(const value_type& r) {
 186     return emplace(r.first, r.second);
 187   }
 188   std::pair<iterator,bool> insert(value_type&& r) {
 189     return emplace(r.first, std::move(r.second));
 190   }
 191
 192   /*
 193    * emplace --
 194    *
 195    *   Same contract as insert(), but performs in-place construction
 196    *   of the value type using the specified arguments.
 197    */
 198   template <typename... ArgTs>
 199   std::pair<iterator,bool> emplace(KeyT key_in, ArgTs&&... vCtorArgs) {
 200     SimpleRetT ret = insertInternal(key_in, std::forward<ArgTs>(vCtorArgs)...);
 201     return std::make_pair(iterator(this, ret.idx), ret.success);
 202   }
 203
 204   // returns the number of elements erased - should never exceed 1
 205   size_t erase(KeyT k);
 206
 207   // clears all keys and values in the map and resets all counters.  Not thread
 208   // safe.
 209   void clear();
 210
 211   // Exact number of elements in the map - note that readFull() acquires a
 212   // mutex.  See folly/ThreadCachedInt.h for more details.
 213   size_t size() const {
 214     return numEntries_.readFull() -
 215       numErases_.load(std::memory_order_relaxed);
 216   }
 217
 218   bool empty() const { return size() == 0; }
 219
 220   iterator begin() {
 221     iterator it(this, 0);
 222     it.advancePastEmpty();
 223     return it;
 224   }
 225   const_iterator begin() const {
 226     const_iterator it(this, 0);
 227     it.advancePastEmpty();
 228     return it;
 229   }
 230
 231   iterator end()               { return iterator(this, capacity_); }
 232   const_iterator end() const   { return const_iterator(this, capacity_); }
 233
 234   // See AtomicHashMap::findAt - access elements directly
 235   // WARNING: The following 2 functions will fail silently for hashtable
 236   // with capacity > 2^32
 237   iterator findAt(uint32_t idx) {
 238     DCHECK_LT(idx, capacity_);
 239     return iterator(this, idx);
 240   }
 241   const_iterator findAt(uint32_t idx) const {
 242     return const_cast<AtomicHashArray*>(this)->findAt(idx);
 243   }
 244
 245   iterator makeIter(size_t idx) { return iterator(this, idx); }
 246   const_iterator makeIter(size_t idx) const {
 247     return const_iterator(this, idx);
 248   }
 249
 250   // The max load factor allowed for this map
 251   double maxLoadFactor() const { return ((double) maxEntries_) / capacity_; }
 252
 253   void setEntryCountThreadCacheSize(uint32_t newSize) {
 254     numEntries_.setCacheSize(newSize);
 255     numPendingEntries_.setCacheSize(newSize);
 256   }
 257
 258   int getEntryCountThreadCacheSize() const {
 259     return numEntries_.getCacheSize();
 260   }
 261
 262   /* Private data and helper functions... */
 263
 264  private:
 265 friend class AtomicHashMap<KeyT,
 266                            ValueT,
 267                            HashFcn,
 268                            EqualFcn,
 269                            Allocator,
 270                            ProbeFcn>;
 271
 272   struct SimpleRetT { size_t idx; bool success;
 273     SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
 274     SimpleRetT() = default;
 275   };
 276
 277
 278
 279   template <typename... ArgTs>
 280   SimpleRetT insertInternal(KeyT key, ArgTs&&... vCtorArgs);
 281
 282   SimpleRetT findInternal(const KeyT key);
 283
 284   static std::atomic<KeyT>* cellKeyPtr(const value_type& r) {
 285     // We need some illegal casting here in order to actually store
 286     // our value_type as a std::pair<const,>.  But a little bit of
 287     // undefined behavior never hurt anyone ...
 288     static_assert(sizeof(std::atomic<KeyT>) == sizeof(KeyT),
 289                   "std::atomic is implemented in an unexpected way for AHM");
 290     return
 291       const_cast<std::atomic<KeyT>*>(
 292         reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
 293   }
 294
 295   static KeyT relaxedLoadKey(const value_type& r) {
 296     return cellKeyPtr(r)->load(std::memory_order_relaxed);
 297   }
 298
 299   static KeyT acquireLoadKey(const value_type& r) {
 300     return cellKeyPtr(r)->load(std::memory_order_acquire);
 301   }
 302
 303   // Fun with thread local storage - atomic increment is expensive
 304   // (relatively), so we accumulate in the thread cache and periodically
 305   // flush to the actual variable, and walk through the unflushed counts when
 306   // reading the value, so be careful of calling size() too frequently.  This
 307   // increases insertion throughput several times over while keeping the count
 308   // accurate.
 309   ThreadCachedInt<uint64_t> numEntries_;  // Successful key inserts
 310   ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
 311   std::atomic<int64_t> isFull_; // Used by insertInternal
 312   std::atomic<int64_t> numErases_;   // Successful key erases
 313
 314   value_type cells_[0];  // This must be the last field of this class
 315
 316   // Force constructor/destructor private since create/destroy should be
 317   // used externally instead
 318   AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
 319                   KeyT erasedKey, double maxLoadFactor, size_t cacheSize);
 320
 321   ~AtomicHashArray() = default;
 322
 323   inline void unlockCell(value_type* const cell, KeyT newKey) {
 324     cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
 325   }
 326
 327   inline bool tryLockCell(value_type* const cell) {
 328     KeyT expect = kEmptyKey_;
 329     return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
 330       std::memory_order_acq_rel);
 331   }
 332
 333   inline size_t keyToAnchorIdx(const KeyT k) const {
 334     const size_t hashVal = HashFcn()(k);
 335     const size_t probe = hashVal & kAnchorMask_;
 336     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
 337   }
 338
 339
 340 }; // AtomicHashArray
 341
 342 } // namespace folly
 343
 344 #include <folly/AtomicHashArray-inl.h>
 345
 346 #endif // FOLLY_ATOMICHASHARRAY_H_