folly/AtomicHashArray.h

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