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