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