2 * Copyright 2015 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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.
25 * Check out AtomicHashMap.h for more thorough documentation on perf and
26 * general pros and cons relative to other hash maps.
28 * @author Spencer Ahrens <sahrens@fb.com>
29 * @author Jordan DeLong <delong.j@fb.com>
32 #ifndef FOLLY_ATOMICHASHARRAY_H_
33 #define FOLLY_ATOMICHASHARRAY_H_
37 #include <boost/iterator/iterator_facade.hpp>
38 #include <boost/noncopyable.hpp>
40 #include <folly/Hash.h>
41 #include <folly/ThreadCachedInt.h>
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>>
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.");
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;
73 const size_t capacity_;
74 const size_t maxEntries_;
75 const KeyT kEmptyKey_;
76 const KeyT kLockedKey_;
77 const KeyT kErasedKey_;
79 template<class ContT, class IterVal>
82 typedef aha_iterator<const AtomicHashArray,const value_type> const_iterator;
83 typedef aha_iterator<AtomicHashArray,value_type> iterator;
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
89 static void destroy(AtomicHashArray*);
92 const size_t kAnchorMask_;
95 void operator()(AtomicHashArray* ptr) {
96 AtomicHashArray::destroy(ptr);
101 typedef std::unique_ptr<AtomicHashArray, Deleter> SmartPtr;
106 * Creates AtomicHashArray objects. Use instead of constructor/destructor.
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
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
119 * Create returns an AHA::SmartPtr which is a unique_ptr with a custom
120 * deleter to make sure everything is cleaned up properly.
126 double maxLoadFactor;
128 int entryCountThreadCacheSize;
129 size_t capacity; // if positive, overrides maxLoadFactor
132 static const KeyT kEmptyKey;
133 static const KeyT kLockedKey;
134 static const KeyT kErasedKey;
137 constexpr Config() : emptyKey(kEmptyKey),
138 lockedKey(kLockedKey),
139 erasedKey(kErasedKey),
142 entryCountThreadCacheSize(1000),
146 static const Config defaultConfig;
147 static SmartPtr create(size_t maxSize, const Config& = defaultConfig);
149 iterator find(KeyT k) {
150 return iterator(this, findInternal(k).idx);
152 const_iterator find(KeyT k) const {
153 return const_cast<AtomicHashArray*>(this)->find(k);
159 * Returns a pair with iterator to the element at r.first and bool success.
160 * Retrieve the index with ret.first.getIndex().
162 * Fails on key collision (does not overwrite) or if map becomes
163 * full, at which point no element is inserted, iterator is set to end(),
164 * and success is set false. On collisions, success is set false, but the
165 * iterator is set to the existing entry.
167 std::pair<iterator,bool> insert(const value_type& r) {
168 SimpleRetT ret = insertInternal(r.first, r.second);
169 return std::make_pair(iterator(this, ret.idx), ret.success);
171 std::pair<iterator,bool> insert(value_type&& r) {
172 SimpleRetT ret = insertInternal(r.first, std::move(r.second));
173 return std::make_pair(iterator(this, ret.idx), ret.success);
176 // returns the number of elements erased - should never exceed 1
177 size_t erase(KeyT k);
179 // clears all keys and values in the map and resets all counters. Not thread
183 // Exact number of elements in the map - note that readFull() acquires a
184 // mutex. See folly/ThreadCachedInt.h for more details.
185 size_t size() const {
186 return numEntries_.readFull() -
187 numErases_.load(std::memory_order_relaxed);
190 bool empty() const { return size() == 0; }
193 iterator it(this, 0);
194 it.advancePastEmpty();
197 const_iterator begin() const {
198 const_iterator it(this, 0);
199 it.advancePastEmpty();
203 iterator end() { return iterator(this, capacity_); }
204 const_iterator end() const { return const_iterator(this, capacity_); }
206 // See AtomicHashMap::findAt - access elements directly
207 // WARNING: The following 2 functions will fail silently for hashtable
208 // with capacity > 2^32
209 iterator findAt(uint32_t idx) {
210 DCHECK_LT(idx, capacity_);
211 return iterator(this, idx);
213 const_iterator findAt(uint32_t idx) const {
214 return const_cast<AtomicHashArray*>(this)->findAt(idx);
217 iterator makeIter(size_t idx) { return iterator(this, idx); }
218 const_iterator makeIter(size_t idx) const {
219 return const_iterator(this, idx);
222 // The max load factor allowed for this map
223 double maxLoadFactor() const { return ((double) maxEntries_) / capacity_; }
225 void setEntryCountThreadCacheSize(uint32_t newSize) {
226 numEntries_.setCacheSize(newSize);
227 numPendingEntries_.setCacheSize(newSize);
230 int getEntryCountThreadCacheSize() const {
231 return numEntries_.getCacheSize();
234 /* Private data and helper functions... */
237 friend class AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>;
239 struct SimpleRetT { size_t idx; bool success;
240 SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
241 SimpleRetT() = default;
245 SimpleRetT insertInternal(KeyT key, T&& value);
247 SimpleRetT findInternal(const KeyT key);
249 static std::atomic<KeyT>* cellKeyPtr(const value_type& r) {
250 // We need some illegal casting here in order to actually store
251 // our value_type as a std::pair<const,>. But a little bit of
252 // undefined behavior never hurt anyone ...
253 static_assert(sizeof(std::atomic<KeyT>) == sizeof(KeyT),
254 "std::atomic is implemented in an unexpected way for AHM");
256 const_cast<std::atomic<KeyT>*>(
257 reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
260 static KeyT relaxedLoadKey(const value_type& r) {
261 return cellKeyPtr(r)->load(std::memory_order_relaxed);
264 static KeyT acquireLoadKey(const value_type& r) {
265 return cellKeyPtr(r)->load(std::memory_order_acquire);
268 // Fun with thread local storage - atomic increment is expensive
269 // (relatively), so we accumulate in the thread cache and periodically
270 // flush to the actual variable, and walk through the unflushed counts when
271 // reading the value, so be careful of calling size() too frequently. This
272 // increases insertion throughput several times over while keeping the count
274 ThreadCachedInt<uint64_t> numEntries_; // Successful key inserts
275 ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
276 std::atomic<int64_t> isFull_; // Used by insertInternal
277 std::atomic<int64_t> numErases_; // Successful key erases
279 value_type cells_[0]; // This must be the last field of this class
281 // Force constructor/destructor private since create/destroy should be
282 // used externally instead
283 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
284 KeyT erasedKey, double maxLoadFactor, size_t cacheSize);
286 ~AtomicHashArray() = default;
288 inline void unlockCell(value_type* const cell, KeyT newKey) {
289 cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
292 inline bool tryLockCell(value_type* const cell) {
293 KeyT expect = kEmptyKey_;
294 return cellKeyPtr(*cell)->compare_exchange_strong(expect, kLockedKey_,
295 std::memory_order_acq_rel);
298 inline size_t keyToAnchorIdx(const KeyT k) const {
299 const size_t hashVal = HashFcn()(k);
300 const size_t probe = hashVal & kAnchorMask_;
301 return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
304 inline size_t probeNext(size_t idx, size_t /*numProbes*/) {
305 //idx += numProbes; // quadratic probing
306 idx += 1; // linear probing
307 // Avoid modulus because it's slow
308 return LIKELY(idx < capacity_) ? idx : (idx - capacity_);
310 }; // AtomicHashArray
314 #include <folly/AtomicHashArray-inl.h>
316 #endif // FOLLY_ATOMICHASHARRAY_H_