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 // Enables specializing checkLegalKey without specializing its class.
  66 namespace detail {
  67 // Local copy of folly::gen::Identity, to avoid heavy dependencies.
  68 class AHAIdentity {
  69  public:
  70   template<class Value>
  71   auto operator()(Value&& value) const ->
  72     decltype(std::forward<Value>(value)) {
  73     return std::forward<Value>(value);
  74   }
  75 };
  76
  77 template <typename NotKeyT, typename KeyT>
  78 inline void checkLegalKeyIfKeyTImpl(NotKeyT ignored, KeyT emptyKey,
  79                                     KeyT lockedKey, KeyT erasedKey) {
  80 }
  81
  82 template <typename KeyT>
  83 inline void checkLegalKeyIfKeyTImpl(KeyT key_in, KeyT emptyKey,
  84                                     KeyT lockedKey, KeyT erasedKey) {
  85   DCHECK_NE(key_in, emptyKey);
  86   DCHECK_NE(key_in, lockedKey);
  87   DCHECK_NE(key_in, erasedKey);
  88 }
  89 }  // namespace detail
  90
  91 template <class KeyT, class ValueT,
  92           class HashFcn = std::hash<KeyT>,
  93           class EqualFcn = std::equal_to<KeyT>,
  94           class Allocator = std::allocator<char>,
  95           class ProbeFcn = AtomicHashArrayLinearProbeFcn,
  96           class KeyConvertFcn = detail::AHAIdentity>
  97 class AtomicHashMap;
  98
  99 template <class KeyT, class ValueT,
 100           class HashFcn = std::hash<KeyT>,
 101           class EqualFcn = std::equal_to<KeyT>,
 102           class Allocator = std::allocator<char>,
 103           class ProbeFcn = AtomicHashArrayLinearProbeFcn,
 104           class KeyConvertFcn = detail::AHAIdentity>
 105 class AtomicHashArray : boost::noncopyable {
 106   static_assert((std::is_convertible<KeyT,int32_t>::value ||
 107                  std::is_convertible<KeyT,int64_t>::value ||
 108                  std::is_convertible<KeyT,const void*>::value),
 109              "You are trying to use AtomicHashArray with disallowed key "
 110              "types.  You must use atomically compare-and-swappable integer "
 111              "keys, or a different container class.");
 112  public:
 113   typedef KeyT                key_type;
 114   typedef ValueT              mapped_type;
 115   typedef HashFcn             hasher;
 116   typedef EqualFcn            key_equal;
 117   typedef KeyConvertFcn       key_convert;
 118   typedef std::pair<const KeyT, ValueT> value_type;
 119   typedef std::size_t         size_type;
 120   typedef std::ptrdiff_t      difference_type;
 121   typedef value_type&         reference;
 122   typedef const value_type&   const_reference;
 123   typedef value_type*         pointer;
 124   typedef const value_type*   const_pointer;
 125
 126   const size_t  capacity_;
 127   const size_t  maxEntries_;
 128   const KeyT    kEmptyKey_;
 129   const KeyT    kLockedKey_;
 130   const KeyT    kErasedKey_;
 131
 132   template<class ContT, class IterVal>
 133   struct aha_iterator;
 134
 135   typedef aha_iterator<const AtomicHashArray,const value_type> const_iterator;
 136   typedef aha_iterator<AtomicHashArray,value_type> iterator;
 137
 138   // You really shouldn't need this if you use the SmartPtr provided by create,
 139   // but if you really want to do something crazy like stick the released
 140   // pointer into a DescriminatedPtr or something, you'll need this to clean up
 141   // after yourself.
 142   static void destroy(AtomicHashArray*);
 143
 144  private:
 145   const size_t  kAnchorMask_;
 146
 147   struct Deleter {
 148     void operator()(AtomicHashArray* ptr) {
 149       AtomicHashArray::destroy(ptr);
 150     }
 151   };
 152
 153  public:
 154   typedef std::unique_ptr<AtomicHashArray, Deleter> SmartPtr;
 155
 156   /*
 157    * create --
 158    *
 159    *   Creates AtomicHashArray objects.  Use instead of constructor/destructor.
 160    *
 161    *   We do things this way in order to avoid the perf penalty of a second
 162    *   pointer indirection when composing these into AtomicHashMap, which needs
 163    *   to store an array of pointers so that it can perform atomic operations on
 164    *   them when growing.
 165    *
 166    *   Instead of a mess of arguments, we take a max size and a Config struct to
 167    *   simulate named ctor parameters.  The Config struct has sensible defaults
 168    *   for everything, but is overloaded - if you specify a positive capacity,
 169    *   that will be used directly instead of computing it based on
 170    *   maxLoadFactor.
 171    *
 172    *   Create returns an AHA::SmartPtr which is a unique_ptr with a custom
 173    *   deleter to make sure everything is cleaned up properly.
 174    */
 175   struct Config {
 176     KeyT   emptyKey;
 177     KeyT   lockedKey;
 178     KeyT   erasedKey;
 179     double maxLoadFactor;
 180     double growthFactor;
 181     int    entryCountThreadCacheSize;
 182     size_t capacity; // if positive, overrides maxLoadFactor
 183
 184   public:
 185     //  Cannot have constexpr ctor because some compilers rightly complain.
 186     Config() : emptyKey((KeyT)-1),
 187                lockedKey((KeyT)-2),
 188                erasedKey((KeyT)-3),
 189                maxLoadFactor(0.8),
 190                growthFactor(-1),
 191                entryCountThreadCacheSize(1000),
 192                capacity(0) {}
 193   };
 194
 195   //  Cannot have pre-instantiated const Config instance because of SIOF.
 196   static SmartPtr create(size_t maxSize, const Config& c = Config());
 197
 198   /*
 199    * find --
 200    *
 201    *
 202    *   Returns the iterator to the element if found, otherwise end().
 203    *
 204    *   As an optional feature, the type of the key to look up (LookupKeyT) is
 205    *   allowed to be different from the type of keys actually stored (KeyT).
 206    *
 207    *   This enables use cases where materializing the key is costly and usually
 208    *   redudant, e.g., canonicalizing/interning a set of strings and being able
 209    *   to look up by StringPiece. To use this feature, LookupHashFcn must take
 210    *   a LookupKeyT, and LookupEqualFcn must take KeyT and LookupKeyT as first
 211    *   and second parameter, respectively.
 212    *
 213    *   See folly/test/ArrayHashArrayTest.cpp for sample usage.
 214    */
 215   template <typename LookupKeyT = key_type,
 216             typename LookupHashFcn = hasher,
 217             typename LookupEqualFcn = key_equal>
 218   iterator find(LookupKeyT k) {
 219     return iterator(this,
 220         findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k).idx);
 221   }
 222
 223   template <typename LookupKeyT = key_type,
 224             typename LookupHashFcn = hasher,
 225             typename LookupEqualFcn = key_equal>
 226   const_iterator find(LookupKeyT k) const {
 227     return const_cast<AtomicHashArray*>(this)->
 228       find<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
 229   }
 230
 231   /*
 232    * insert --
 233    *
 234    *   Returns a pair with iterator to the element at r.first and bool success.
 235    *   Retrieve the index with ret.first.getIndex().
 236    *
 237    *   Fails on key collision (does not overwrite) or if map becomes
 238    *   full, at which point no element is inserted, iterator is set to end(),
 239    *   and success is set false.  On collisions, success is set false, but the
 240    *   iterator is set to the existing entry.
 241    */
 242   std::pair<iterator,bool> insert(const value_type& r) {
 243     return emplace(r.first, r.second);
 244   }
 245   std::pair<iterator,bool> insert(value_type&& r) {
 246     return emplace(r.first, std::move(r.second));
 247   }
 248
 249   /*
 250    * emplace --
 251    *
 252    *   Same contract as insert(), but performs in-place construction
 253    *   of the value type using the specified arguments.
 254    *
 255    *   Also, like find(), this method optionally allows 'key_in' to have a type
 256    *   different from that stored in the table; see find(). If and only if no
 257    *   equal key is already present, this method converts 'key_in' to a key of
 258    *   type KeyT using the provided LookupKeyToKeyFcn.
 259    */
 260   template <typename LookupKeyT = key_type,
 261             typename LookupHashFcn = hasher,
 262             typename LookupEqualFcn = key_equal,
 263             typename LookupKeyToKeyFcn = key_convert,
 264             typename... ArgTs>
 265   std::pair<iterator,bool> emplace(LookupKeyT key_in, ArgTs&&... vCtorArgs) {
 266     SimpleRetT ret = insertInternal<LookupKeyT,
 267                                     LookupHashFcn,
 268                                     LookupEqualFcn,
 269                                     LookupKeyToKeyFcn>(
 270                                       key_in,
 271                                       std::forward<ArgTs>(vCtorArgs)...);
 272     return std::make_pair(iterator(this, ret.idx), ret.success);
 273   }
 274
 275   // returns the number of elements erased - should never exceed 1
 276   size_t erase(KeyT k);
 277
 278   // clears all keys and values in the map and resets all counters.  Not thread
 279   // safe.
 280   void clear();
 281
 282   // Exact number of elements in the map - note that readFull() acquires a
 283   // mutex.  See folly/ThreadCachedInt.h for more details.
 284   size_t size() const {
 285     return numEntries_.readFull() -
 286       numErases_.load(std::memory_order_relaxed);
 287   }
 288
 289   bool empty() const { return size() == 0; }
 290
 291   iterator begin() {
 292     iterator it(this, 0);
 293     it.advancePastEmpty();
 294     return it;
 295   }
 296   const_iterator begin() const {
 297     const_iterator it(this, 0);
 298     it.advancePastEmpty();
 299     return it;
 300   }
 301
 302   iterator end()               { return iterator(this, capacity_); }
 303   const_iterator end() const   { return const_iterator(this, capacity_); }
 304
 305   // See AtomicHashMap::findAt - access elements directly
 306   // WARNING: The following 2 functions will fail silently for hashtable
 307   // with capacity > 2^32
 308   iterator findAt(uint32_t idx) {
 309     DCHECK_LT(idx, capacity_);
 310     return iterator(this, idx);
 311   }
 312   const_iterator findAt(uint32_t idx) const {
 313     return const_cast<AtomicHashArray*>(this)->findAt(idx);
 314   }
 315
 316   iterator makeIter(size_t idx) { return iterator(this, idx); }
 317   const_iterator makeIter(size_t idx) const {
 318     return const_iterator(this, idx);
 319   }
 320
 321   // The max load factor allowed for this map
 322   double maxLoadFactor() const { return ((double) maxEntries_) / capacity_; }
 323
 324   void setEntryCountThreadCacheSize(uint32_t newSize) {
 325     numEntries_.setCacheSize(newSize);
 326     numPendingEntries_.setCacheSize(newSize);
 327   }
 328
 329   int getEntryCountThreadCacheSize() const {
 330     return numEntries_.getCacheSize();
 331   }
 332
 333   /* Private data and helper functions... */
 334
 335  private:
 336 friend class AtomicHashMap<KeyT,
 337                            ValueT,
 338                            HashFcn,
 339                            EqualFcn,
 340                            Allocator,
 341                            ProbeFcn>;
 342
 343   struct SimpleRetT { size_t idx; bool success;
 344     SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
 345     SimpleRetT() = default;
 346   };
 347
 348
 349
 350   template <typename LookupKeyT = key_type,
 351             typename LookupHashFcn = hasher,
 352             typename LookupEqualFcn = key_equal,
 353             typename LookupKeyToKeyFcn = detail::AHAIdentity,
 354             typename... ArgTs>
 355   SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs);
 356
 357   template <typename LookupKeyT = key_type,
 358             typename LookupHashFcn = hasher,
 359             typename LookupEqualFcn = key_equal>
 360   SimpleRetT findInternal(const LookupKeyT key);
 361
 362   template <typename MaybeKeyT>
 363   void checkLegalKeyIfKey(MaybeKeyT key) {
 364     detail::checkLegalKeyIfKeyTImpl(key, kEmptyKey_, kLockedKey_, kErasedKey_);
 365   }
 366
 367   static std::atomic<KeyT>* cellKeyPtr(const value_type& r) {
 368     // We need some illegal casting here in order to actually store
 369     // our value_type as a std::pair<const,>.  But a little bit of
 370     // undefined behavior never hurt anyone ...
 371     static_assert(sizeof(std::atomic<KeyT>) == sizeof(KeyT),
 372                   "std::atomic is implemented in an unexpected way for AHM");
 373     return
 374       const_cast<std::atomic<KeyT>*>(
 375         reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
 376   }
 377
 378   static KeyT relaxedLoadKey(const value_type& r) {
 379     return cellKeyPtr(r)->load(std::memory_order_relaxed);
 380   }
 381
 382   static KeyT acquireLoadKey(const value_type& r) {
 383     return cellKeyPtr(r)->load(std::memory_order_acquire);
 384   }
 385
 386   // Fun with thread local storage - atomic increment is expensive
 387   // (relatively), so we accumulate in the thread cache and periodically
 388   // flush to the actual variable, and walk through the unflushed counts when
 389   // reading the value, so be careful of calling size() too frequently.  This
 390   // increases insertion throughput several times over while keeping the count
 391   // accurate.
 392   ThreadCachedInt<uint64_t> numEntries_;  // Successful key inserts
 393   ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
 394   std::atomic<int64_t> isFull_; // Used by insertInternal
 395   std::atomic<int64_t> numErases_;   // Successful key erases
 396
 397   value_type cells_[0];  // This must be the last field of this class
 398
 399   // Force constructor/destructor private since create/destroy should be
 400   // used externally instead
 401   AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
 402                   KeyT erasedKey, double maxLoadFactor, size_t cacheSize);
 403
 404   ~AtomicHashArray() = default;
 405
 406   inline void unlockCell(value_type* const cell, KeyT newKey) {
 407     cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
 408   }
 409
 410   inline bool tryLockCell(value_type* const cell) {
 411     KeyT expect = kEmptyKey_;
 412     return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
 413       std::memory_order_acq_rel);
 414   }
 415
 416   template <class LookupKeyT = key_type, class LookupHashFcn = hasher>
 417   inline size_t keyToAnchorIdx(const LookupKeyT k) const {
 418     const size_t hashVal = LookupHashFcn()(k);
 419     const size_t probe = hashVal & kAnchorMask_;
 420     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
 421   }
 422
 423
 424 }; // AtomicHashArray
 425
 426 } // namespace folly
 427
 428 #include <folly/AtomicHashArray-inl.h>
 429
 430 #endif // FOLLY_ATOMICHASHARRAY_H_