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 template <class KeyT, class ValueT,
  46           class HashFcn = std::hash<KeyT>,
  47           class EqualFcn = std::equal_to<KeyT>,
  48           class Allocator = std::allocator<char>>
  49 class AtomicHashMap;
  50
  51 template <class KeyT, class ValueT,
  52           class HashFcn = std::hash<KeyT>,
  53           class EqualFcn = std::equal_to<KeyT>,
  54           class Allocator = std::allocator<char>>
  55 class AtomicHashArray : boost::noncopyable {
  56   static_assert((std::is_convertible<KeyT,int32_t>::value ||
  57                  std::is_convertible<KeyT,int64_t>::value ||
  58                  std::is_convertible<KeyT,const void*>::value),
  59              "You are trying to use AtomicHashArray with disallowed key "
  60              "types.  You must use atomically compare-and-swappable integer "
  61              "keys, or a different container class.");
  62  public:
  63   typedef KeyT                key_type;
  64   typedef ValueT              mapped_type;
  65   typedef std::pair<const KeyT, ValueT> value_type;
  66   typedef std::size_t         size_type;
  67   typedef std::ptrdiff_t      difference_type;
  68   typedef value_type&         reference;
  69   typedef const value_type&   const_reference;
  70   typedef value_type*         pointer;
  71   typedef const value_type*   const_pointer;
  72
  73   const size_t  capacity_;
  74   const size_t  maxEntries_;
  75   const KeyT    kEmptyKey_;
  76   const KeyT    kLockedKey_;
  77   const KeyT    kErasedKey_;
  78
  79   template<class ContT, class IterVal>
  80   struct aha_iterator;
  81
  82   typedef aha_iterator<const AtomicHashArray,const value_type> const_iterator;
  83   typedef aha_iterator<AtomicHashArray,value_type> iterator;
  84
  85   // You really shouldn't need this if you use the SmartPtr provided by create,
  86   // but if you really want to do something crazy like stick the released
  87   // pointer into a DescriminatedPtr or something, you'll need this to clean up
  88   // after yourself.
  89   static void destroy(AtomicHashArray*);
  90
  91  private:
  92   const size_t  kAnchorMask_;
  93
  94   struct Deleter {
  95     void operator()(AtomicHashArray* ptr) {
  96       AtomicHashArray::destroy(ptr);
  97     }
  98   };
  99
 100  public:
 101   typedef std::unique_ptr<AtomicHashArray, Deleter> SmartPtr;
 102
 103   /*
 104    * create --
 105    *
 106    *   Creates AtomicHashArray objects.  Use instead of constructor/destructor.
 107    *
 108    *   We do things this way in order to avoid the perf penalty of a second
 109    *   pointer indirection when composing these into AtomicHashMap, which needs
 110    *   to store an array of pointers so that it can perform atomic operations on
 111    *   them when growing.
 112    *
 113    *   Instead of a mess of arguments, we take a max size and a Config struct to
 114    *   simulate named ctor parameters.  The Config struct has sensible defaults
 115    *   for everything, but is overloaded - if you specify a positive capacity,
 116    *   that will be used directly instead of computing it based on
 117    *   maxLoadFactor.
 118    *
 119    *   Create returns an AHA::SmartPtr which is a unique_ptr with a custom
 120    *   deleter to make sure everything is cleaned up properly.
 121    */
 122   struct Config {
 123     KeyT   emptyKey;
 124     KeyT   lockedKey;
 125     KeyT   erasedKey;
 126     double maxLoadFactor;
 127     double growthFactor;
 128     int    entryCountThreadCacheSize;
 129     size_t capacity; // if positive, overrides maxLoadFactor
 130
 131   public:
 132     //  Cannot have constexpr ctor because some compilers rightly complain.
 133     Config() : emptyKey((KeyT)-1),
 134                lockedKey((KeyT)-2),
 135                erasedKey((KeyT)-3),
 136                maxLoadFactor(0.8),
 137                growthFactor(-1),
 138                entryCountThreadCacheSize(1000),
 139                capacity(0) {}
 140   };
 141
 142   //  Cannot have pre-instantiated const Config instance because of SIOF.
 143   static SmartPtr create(size_t maxSize, const Config& c = Config());
 144
 145   iterator find(KeyT k) {
 146     return iterator(this, findInternal(k).idx);
 147   }
 148   const_iterator find(KeyT k) const {
 149     return const_cast<AtomicHashArray*>(this)->find(k);
 150   }
 151
 152   /*
 153    * insert --
 154    *
 155    *   Returns a pair with iterator to the element at r.first and bool success.
 156    *   Retrieve the index with ret.first.getIndex().
 157    *
 158    *   Fails on key collision (does not overwrite) or if map becomes
 159    *   full, at which point no element is inserted, iterator is set to end(),
 160    *   and success is set false.  On collisions, success is set false, but the
 161    *   iterator is set to the existing entry.
 162    */
 163   std::pair<iterator,bool> insert(const value_type& r) {
 164     return emplace(r.first, r.second);
 165   }
 166   std::pair<iterator,bool> insert(value_type&& r) {
 167     return emplace(r.first, std::move(r.second));
 168   }
 169
 170   /*
 171    * emplace --
 172    *
 173    *   Same contract as insert(), but performs in-place construction
 174    *   of the value type using the specified arguments.
 175    */
 176   template <typename... ArgTs>
 177   std::pair<iterator,bool> emplace(KeyT key_in, ArgTs&&... vCtorArgs) {
 178     SimpleRetT ret = insertInternal(key_in, std::forward<ArgTs>(vCtorArgs)...);
 179     return std::make_pair(iterator(this, ret.idx), ret.success);
 180   }
 181
 182   // returns the number of elements erased - should never exceed 1
 183   size_t erase(KeyT k);
 184
 185   // clears all keys and values in the map and resets all counters.  Not thread
 186   // safe.
 187   void clear();
 188
 189   // Exact number of elements in the map - note that readFull() acquires a
 190   // mutex.  See folly/ThreadCachedInt.h for more details.
 191   size_t size() const {
 192     return numEntries_.readFull() -
 193       numErases_.load(std::memory_order_relaxed);
 194   }
 195
 196   bool empty() const { return size() == 0; }
 197
 198   iterator begin() {
 199     iterator it(this, 0);
 200     it.advancePastEmpty();
 201     return it;
 202   }
 203   const_iterator begin() const {
 204     const_iterator it(this, 0);
 205     it.advancePastEmpty();
 206     return it;
 207   }
 208
 209   iterator end()               { return iterator(this, capacity_); }
 210   const_iterator end() const   { return const_iterator(this, capacity_); }
 211
 212   // See AtomicHashMap::findAt - access elements directly
 213   // WARNING: The following 2 functions will fail silently for hashtable
 214   // with capacity > 2^32
 215   iterator findAt(uint32_t idx) {
 216     DCHECK_LT(idx, capacity_);
 217     return iterator(this, idx);
 218   }
 219   const_iterator findAt(uint32_t idx) const {
 220     return const_cast<AtomicHashArray*>(this)->findAt(idx);
 221   }
 222
 223   iterator makeIter(size_t idx) { return iterator(this, idx); }
 224   const_iterator makeIter(size_t idx) const {
 225     return const_iterator(this, idx);
 226   }
 227
 228   // The max load factor allowed for this map
 229   double maxLoadFactor() const { return ((double) maxEntries_) / capacity_; }
 230
 231   void setEntryCountThreadCacheSize(uint32_t newSize) {
 232     numEntries_.setCacheSize(newSize);
 233     numPendingEntries_.setCacheSize(newSize);
 234   }
 235
 236   int getEntryCountThreadCacheSize() const {
 237     return numEntries_.getCacheSize();
 238   }
 239
 240   /* Private data and helper functions... */
 241
 242  private:
 243   friend class AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>;
 244
 245   struct SimpleRetT { size_t idx; bool success;
 246     SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
 247     SimpleRetT() = default;
 248   };
 249
 250   template <typename... ArgTs>
 251   SimpleRetT insertInternal(KeyT key, ArgTs&&... vCtorArgs);
 252
 253   SimpleRetT findInternal(const KeyT key);
 254
 255   static std::atomic<KeyT>* cellKeyPtr(const value_type& r) {
 256     // We need some illegal casting here in order to actually store
 257     // our value_type as a std::pair<const,>.  But a little bit of
 258     // undefined behavior never hurt anyone ...
 259     static_assert(sizeof(std::atomic<KeyT>) == sizeof(KeyT),
 260                   "std::atomic is implemented in an unexpected way for AHM");
 261     return
 262       const_cast<std::atomic<KeyT>*>(
 263         reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
 264   }
 265
 266   static KeyT relaxedLoadKey(const value_type& r) {
 267     return cellKeyPtr(r)->load(std::memory_order_relaxed);
 268   }
 269
 270   static KeyT acquireLoadKey(const value_type& r) {
 271     return cellKeyPtr(r)->load(std::memory_order_acquire);
 272   }
 273
 274   // Fun with thread local storage - atomic increment is expensive
 275   // (relatively), so we accumulate in the thread cache and periodically
 276   // flush to the actual variable, and walk through the unflushed counts when
 277   // reading the value, so be careful of calling size() too frequently.  This
 278   // increases insertion throughput several times over while keeping the count
 279   // accurate.
 280   ThreadCachedInt<uint64_t> numEntries_;  // Successful key inserts
 281   ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
 282   std::atomic<int64_t> isFull_; // Used by insertInternal
 283   std::atomic<int64_t> numErases_;   // Successful key erases
 284
 285   value_type cells_[0];  // This must be the last field of this class
 286
 287   // Force constructor/destructor private since create/destroy should be
 288   // used externally instead
 289   AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
 290                   KeyT erasedKey, double maxLoadFactor, size_t cacheSize);
 291
 292   ~AtomicHashArray() = default;
 293
 294   inline void unlockCell(value_type* const cell, KeyT newKey) {
 295     cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
 296   }
 297
 298   inline bool tryLockCell(value_type* const cell) {
 299     KeyT expect = kEmptyKey_;
 300     return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
 301       std::memory_order_acq_rel);
 302   }
 303
 304   inline size_t keyToAnchorIdx(const KeyT k) const {
 305     const size_t hashVal = HashFcn()(k);
 306     const size_t probe = hashVal & kAnchorMask_;
 307     return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
 308   }
 309
 310   inline size_t probeNext(size_t idx, size_t /*numProbes*/) {
 311     //idx += numProbes; // quadratic probing
 312     idx += 1; // linear probing
 313     // Avoid modulus because it's slow
 314     return LIKELY(idx < capacity_) ? idx : (idx - capacity_);
 315   }
 316 }; // AtomicHashArray
 317
 318 } // namespace folly
 319
 320 #include <folly/AtomicHashArray-inl.h>
 321
 322 #endif // FOLLY_ATOMICHASHARRAY_H_