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   public:
 183     //  Cannot have constexpr ctor because some compilers rightly complain.
 184     Config() : emptyKey((KeyT)-1),
 185                lockedKey((KeyT)-2),
 186                erasedKey((KeyT)-3),
 187                maxLoadFactor(0.8),
 188                growthFactor(-1),
 189                entryCountThreadCacheSize(1000),
 190                capacity(0) {}
 191   };
 192
 193   //  Cannot have pre-instantiated const Config instance because of SIOF.
 194   static SmartPtr create(size_t maxSize, const Config& c = Config());
 195
 196   /*
 197    * find --
 198    *
 199    *
 200    *   Returns the iterator to the element if found, otherwise end().
 201    *
 202    *   As an optional feature, the type of the key to look up (LookupKeyT) is
 203    *   allowed to be different from the type of keys actually stored (KeyT).
 204    *
 205    *   This enables use cases where materializing the key is costly and usually
 206    *   redudant, e.g., canonicalizing/interning a set of strings and being able
 207    *   to look up by StringPiece. To use this feature, LookupHashFcn must take
 208    *   a LookupKeyT, and LookupEqualFcn must take KeyT and LookupKeyT as first
 209    *   and second parameter, respectively.
 210    *
 211    *   See folly/test/ArrayHashArrayTest.cpp for sample usage.
 212    */
 213   template <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 <typename LookupKeyT = key_type,
 222             typename LookupHashFcn = hasher,
 223             typename LookupEqualFcn = key_equal>
 224   const_iterator find(LookupKeyT k) const {
 225     return const_cast<AtomicHashArray*>(this)->
 226       find<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
 227   }
 228
 229   /*
 230    * insert --
 231    *
 232    *   Returns a pair with iterator to the element at r.first and bool success.
 233    *   Retrieve the index with ret.first.getIndex().
 234    *
 235    *   Fails on key collision (does not overwrite) or if map becomes
 236    *   full, at which point no element is inserted, iterator is set to end(),
 237    *   and success is set false.  On collisions, success is set false, but the
 238    *   iterator is set to the existing entry.
 239    */
 240   std::pair<iterator,bool> insert(const value_type& r) {
 241     return emplace(r.first, r.second);
 242   }
 243   std::pair<iterator,bool> insert(value_type&& r) {
 244     return emplace(r.first, std::move(r.second));
 245   }
 246
 247   /*
 248    * emplace --
 249    *
 250    *   Same contract as insert(), but performs in-place construction
 251    *   of the value type using the specified arguments.
 252    *
 253    *   Also, like find(), this method optionally allows 'key_in' to have a type
 254    *   different from that stored in the table; see find(). If and only if no
 255    *   equal key is already present, this method converts 'key_in' to a key of
 256    *   type KeyT using the provided LookupKeyToKeyFcn.
 257    */
 258   template <typename LookupKeyT = key_type,
 259             typename LookupHashFcn = hasher,
 260             typename LookupEqualFcn = key_equal,
 261             typename LookupKeyToKeyFcn = key_convert,
 262             typename... ArgTs>
 263   std::pair<iterator,bool> emplace(LookupKeyT key_in, ArgTs&&... vCtorArgs) {
 264     SimpleRetT ret = insertInternal<LookupKeyT,
 265                                     LookupHashFcn,
 266                                     LookupEqualFcn,
 267                                     LookupKeyToKeyFcn>(
 268                                       key_in,
 269                                       std::forward<ArgTs>(vCtorArgs)...);
 270     return std::make_pair(iterator(this, ret.idx), ret.success);
 271   }
 272
 273   // returns the number of elements erased - should never exceed 1
 274   size_t erase(KeyT k);
 275
 276   // clears all keys and values in the map and resets all counters.  Not thread
 277   // safe.
 278   void clear();
 279
 280   // Exact number of elements in the map - note that readFull() acquires a
 281   // mutex.  See folly/ThreadCachedInt.h for more details.
 282   size_t size() const {
 283     return numEntries_.readFull() -
 284       numErases_.load(std::memory_order_relaxed);
 285   }
 286
 287   bool empty() const { return size() == 0; }
 288
 289   iterator begin() {
 290     iterator it(this, 0);
 291     it.advancePastEmpty();
 292     return it;
 293   }
 294   const_iterator begin() const {
 295     const_iterator it(this, 0);
 296     it.advancePastEmpty();
 297     return it;
 298   }
 299
 300   iterator end()               { return iterator(this, capacity_); }
 301   const_iterator end() const   { return const_iterator(this, capacity_); }
 302
 303   // See AtomicHashMap::findAt - access elements directly
 304   // WARNING: The following 2 functions will fail silently for hashtable
 305   // with capacity > 2^32
 306   iterator findAt(uint32_t idx) {
 307     DCHECK_LT(idx, capacity_);
 308     return iterator(this, idx);
 309   }
 310   const_iterator findAt(uint32_t idx) const {
 311     return const_cast<AtomicHashArray*>(this)->findAt(idx);
 312   }
 313
 314   iterator makeIter(size_t idx) { return iterator(this, idx); }
 315   const_iterator makeIter(size_t idx) const {
 316     return const_iterator(this, idx);
 317   }
 318
 319   // The max load factor allowed for this map
 320   double maxLoadFactor() const { return ((double) maxEntries_) / capacity_; }
 321
 322   void setEntryCountThreadCacheSize(uint32_t newSize) {
 323     numEntries_.setCacheSize(newSize);
 324     numPendingEntries_.setCacheSize(newSize);
 325   }
 326
 327   uint32_t getEntryCountThreadCacheSize() const {
 328     return numEntries_.getCacheSize();
 329   }
 330
 331   /* Private data and helper functions... */
 332
 333  private:
 334 friend class AtomicHashMap<KeyT,
 335                            ValueT,
 336                            HashFcn,
 337                            EqualFcn,
 338                            Allocator,
 339                            ProbeFcn>;
 340
 341   struct SimpleRetT { size_t idx; bool success;
 342     SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
 343     SimpleRetT() = default;
 344   };
 345
 346   template <
 347       typename LookupKeyT = key_type,
 348       typename LookupHashFcn = hasher,
 349       typename LookupEqualFcn = key_equal,
 350       typename LookupKeyToKeyFcn = Identity,
 351       typename... ArgTs>
 352   SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs);
 353
 354   template <typename LookupKeyT = key_type,
 355             typename LookupHashFcn = hasher,
 356             typename LookupEqualFcn = key_equal>
 357   SimpleRetT findInternal(const LookupKeyT key);
 358
 359   template <typename MaybeKeyT>
 360   void checkLegalKeyIfKey(MaybeKeyT key) {
 361     detail::checkLegalKeyIfKeyTImpl(key, kEmptyKey_, kLockedKey_, kErasedKey_);
 362   }
 363
 364   static std::atomic<KeyT>* cellKeyPtr(const value_type& r) {
 365     // We need some illegal casting here in order to actually store
 366     // our value_type as a std::pair<const,>.  But a little bit of
 367     // undefined behavior never hurt anyone ...
 368     static_assert(sizeof(std::atomic<KeyT>) == sizeof(KeyT),
 369                   "std::atomic is implemented in an unexpected way for AHM");
 370     return
 371       const_cast<std::atomic<KeyT>*>(
 372         reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
 373   }
 374
 375   static KeyT relaxedLoadKey(const value_type& r) {
 376     return cellKeyPtr(r)->load(std::memory_order_relaxed);
 377   }
 378
 379   static KeyT acquireLoadKey(const value_type& r) {
 380     return cellKeyPtr(r)->load(std::memory_order_acquire);
 381   }
 382
 383   // Fun with thread local storage - atomic increment is expensive
 384   // (relatively), so we accumulate in the thread cache and periodically
 385   // flush to the actual variable, and walk through the unflushed counts when
 386   // reading the value, so be careful of calling size() too frequently.  This
 387   // increases insertion throughput several times over while keeping the count
 388   // accurate.
 389   ThreadCachedInt<uint64_t> numEntries_;  // Successful key inserts
 390   ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
 391   std::atomic<int64_t> isFull_; // Used by insertInternal
 392   std::atomic<int64_t> numErases_;   // Successful key erases
 393
 394   value_type cells_[0];  // This must be the last field of this class
 395
 396   // Force constructor/destructor private since create/destroy should be
 397   // used externally instead
 398   AtomicHashArray(
 399       size_t capacity,
 400       KeyT emptyKey,
 401       KeyT lockedKey,
 402       KeyT erasedKey,
 403       double maxLoadFactor,
 404       uint32_t cacheSize);
 405
 406   ~AtomicHashArray() = default;
 407
 408   inline void unlockCell(value_type* const cell, KeyT newKey) {
 409     cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
 410   }
 411
 412   inline bool tryLockCell(value_type* const cell) {
 413     KeyT expect = kEmptyKey_;
 414     return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
 415       std::memory_order_acq_rel);
 416   }
 417
 418   template <class LookupKeyT = key_type, class LookupHashFcn = hasher>
 419   inline size_t keyToAnchorIdx(const LookupKeyT k) const {
 420     const size_t hashVal = LookupHashFcn()(k);
 421     const size_t probe = hashVal & kAnchorMask_;
 422     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
 423   }
 424
 425
 426 }; // AtomicHashArray
 427
 428 } // namespace folly
 429
 430 #include <folly/AtomicHashArray-inl.h>