folly/AtomicHashArray.h

   1 /*
   2  * Copyright 2012-present 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/ThreadCachedInt.h>
  41 #include <folly/Utility.h>
  42 #include <folly/hash/Hash.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 <
 213       typename LookupKeyT = key_type,
 214       typename LookupHashFcn = hasher,
 215       typename LookupEqualFcn = key_equal>
 216   iterator find(LookupKeyT k) {
 217     return iterator(this,
 218         findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k).idx);
 219   }
 220
 221   template <
 222       typename LookupKeyT = key_type,
 223       typename LookupHashFcn = hasher,
 224       typename LookupEqualFcn = key_equal>
 225   const_iterator find(LookupKeyT k) const {
 226     return const_cast<AtomicHashArray*>(this)->
 227       find<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
 228   }
 229
 230   /*
 231    * insert --
 232    *
 233    *   Returns a pair with iterator to the element at r.first and bool success.
 234    *   Retrieve the index with ret.first.getIndex().
 235    *
 236    *   Fails on key collision (does not overwrite) or if map becomes
 237    *   full, at which point no element is inserted, iterator is set to end(),
 238    *   and success is set false.  On collisions, success is set false, but the
 239    *   iterator is set to the existing entry.
 240    */
 241   std::pair<iterator,bool> insert(const value_type& r) {
 242     return emplace(r.first, r.second);
 243   }
 244   std::pair<iterator,bool> insert(value_type&& r) {
 245     return emplace(r.first, std::move(r.second));
 246   }
 247
 248   /*
 249    * emplace --
 250    *
 251    *   Same contract as insert(), but performs in-place construction
 252    *   of the value type using the specified arguments.
 253    *
 254    *   Also, like find(), this method optionally allows 'key_in' to have a type
 255    *   different from that stored in the table; see find(). If and only if no
 256    *   equal key is already present, this method converts 'key_in' to a key of
 257    *   type KeyT using the provided LookupKeyToKeyFcn.
 258    */
 259   template <
 260       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   uint32_t 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   template <
 349       typename LookupKeyT = key_type,
 350       typename LookupHashFcn = hasher,
 351       typename LookupEqualFcn = key_equal,
 352       typename LookupKeyToKeyFcn = Identity,
 353       typename... ArgTs>
 354   SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs);
 355
 356   template <
 357       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(
 402       size_t capacity,
 403       KeyT emptyKey,
 404       KeyT lockedKey,
 405       KeyT erasedKey,
 406       double maxLoadFactor,
 407       uint32_t cacheSize);
 408
 409   ~AtomicHashArray() = default;
 410
 411   inline void unlockCell(value_type* const cell, KeyT newKey) {
 412     cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
 413   }
 414
 415   inline bool tryLockCell(value_type* const cell) {
 416     KeyT expect = kEmptyKey_;
 417     return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
 418       std::memory_order_acq_rel);
 419   }
 420
 421   template <class LookupKeyT = key_type, class LookupHashFcn = hasher>
 422   inline size_t keyToAnchorIdx(const LookupKeyT k) const {
 423     const size_t hashVal = LookupHashFcn()(k);
 424     const size_t probe = hashVal & kAnchorMask_;
 425     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
 426   }
 427
 428
 429 }; // AtomicHashArray
 430
 431 } // namespace folly
 432
 433 #include <folly/AtomicHashArray-inl.h>