Blender V5.3
mikk_atomic_hash_set.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2012-2021 Meta Platforms, Inc. and affiliates.
2 * SPDX-FileCopyrightText: 2022 Blender Authors
3 *
4 * SPDX-License-Identifier: Apache-2.0 */
5
6/* Simplified version of Folly's AtomicHashArray
7 * (https://github.com/facebook/folly/blob/main/folly/AtomicHashArray.h).
8 *
9 * Notable changes:
10 * - Standalone and header-only.
11 * - Behaves like a set, not like a map: There's no value type anymore, only keys.
12 * - Capacity check logic have been removed, the code assumes you know the required size in
13 * advance.
14 * - Custom allocator support has been removed.
15 * - Erase has been removed.
16 * - Find has been removed.
17 */
18
22
23#pragma once
24
25#ifdef _MSC_VER
26# include <intrin.h>
27#endif
28
29#include <atomic>
30#include <cassert>
31#include <type_traits>
32#include <vector>
33
34namespace mikk {
35
37 size_t operator()(size_t idx, size_t /* numProbes */, size_t capacity) const
38 {
39 idx += 1; // linear probing
40
41 // Avoid modulus because it's slow
42 return LIKELY(idx < capacity) ? idx : (idx - capacity);
43 }
44};
45
47 size_t operator()(size_t idx, size_t numProbes, size_t capacity) const
48 {
49 idx += numProbes; // quadratic probing
50
51 // Avoid modulus because it's slow
52 return LIKELY(idx < capacity) ? idx : (idx - capacity);
53 }
54};
55
56template<class KeyT,
57 bool isAtomic,
58 class KeyHash = std::hash<KeyT>,
59 class KeyEqual = std::equal_to<KeyT>,
60 class ProbeFcn = AtomicHashSetLinearProbeFcn>
62 static_assert((std::is_convertible_v<KeyT, int32_t> || std::is_convertible_v<KeyT, int64_t> ||
63 std::is_convertible_v<KeyT, const void *>),
64 "You are trying to use AtomicHashSet with disallowed key "
65 "types. You must use atomically compare-and-swappable integer "
66 "keys, or a different container class.");
67
68 public:
69 const size_t capacity_;
70 const KeyT kEmptyKey_;
71
72 KeyHash hasher_;
74
75 private:
76 size_t kAnchorMask_;
77 /* When using a single thread, we can avoid overhead by not bothering with atomic cells. */
78 using cell_type = std::conditional_t<isAtomic, std::atomic<KeyT>, KeyT>;
79 std::vector<cell_type> cells_;
80
81 public:
82 struct Config {
83 KeyT emptyKey = KeyT(-1);
84 double maxLoadFactor = 0.8;
85 double growthFactor = -1;
86 size_t capacity = 0; // if positive, overrides maxLoadFactor
87
88 // Cannot have constexpr ctor because some compilers rightly complain.
89 Config() = default;
90 };
91
92 /* Instead of a mess of arguments, we take a max size and a Config struct to
93 * simulate named ctor parameters. The Config struct has sensible defaults
94 * for everything, but is overloaded - if you specify a positive capacity,
95 * that will be used directly instead of computing it based on maxLoadFactor.
96 */
97 AtomicHashSet(size_t maxSize,
98 KeyHash hasher = KeyHash(),
99 KeyEqual equalityChecker = KeyEqual(),
100 const Config &c = Config())
101 : capacity_(size_t(double(maxSize) / c.maxLoadFactor) + 1),
102 kEmptyKey_(c.emptyKey),
103 hasher_(hasher),
104 equalityChecker_(equalityChecker),
105 cells_(capacity_)
106 {
107 /* Get next power of two. Could be done more efficiently with builtin_clz, but this is not
108 * performance-critical. */
109 kAnchorMask_ = 1;
110 while (kAnchorMask_ < capacity_) {
111 kAnchorMask_ *= 2;
112 }
113 /* Get mask for lower bits. */
114 kAnchorMask_ -= 1;
115
116 /* Not great, but the best we can do to support both atomic and non-atomic cells
117 * since std::atomic doesn't have a copy constructor so cells_(capacity_, kEmptyKey_)
118 * in the initializer list won't work. */
119 std::fill(reinterpret_cast<KeyT *>(cells_.data()),
120 reinterpret_cast<KeyT *>(cells_.data()) + capacity_,
121 kEmptyKey_);
122 }
123
124 AtomicHashSet(const AtomicHashSet &) = delete;
126
127 ~AtomicHashSet() = default;
128
129 /* Sequential specialization. */
130 bool tryUpdateCell(KeyT *cell, KeyT &existingKey, KeyT newKey)
131 {
132 if (*cell == existingKey) {
133 *cell = newKey;
134 return true;
135 }
136 existingKey = *cell;
137 return false;
138 }
139
140 /* Atomic specialization. */
141 bool tryUpdateCell(std::atomic<KeyT> *cell, KeyT &existingKey, KeyT newKey)
142 {
143 return cell->compare_exchange_strong(existingKey, newKey, std::memory_order_acq_rel);
144 }
145
146 std::pair<KeyT, bool> emplace(KeyT key)
147 {
148 size_t idx = keyToAnchorIdx(key);
149 size_t numProbes = 0;
150 for (;;) {
151 cell_type *cell = &cells_[idx];
152 KeyT existingKey = kEmptyKey_;
153 /* Try to replace empty cell with our key. */
154 if (tryUpdateCell(cell, existingKey, key)) {
155 /* Cell was empty, we're done. */
156 return std::make_pair(key, true);
157 }
158
159 /* Cell was not empty, check if the existing key is equal. */
160 if (equalityChecker_(existingKey, key)) {
161 /* Found equal element, we're done. */
162 return std::make_pair(existingKey, false);
163 }
164
165 /* Continue to next cell according to probe strategy. */
166 ++numProbes;
167 if (UNLIKELY(numProbes >= capacity_)) {
168 // probed every cell...fail
169 assert(false);
170 return std::make_pair(kEmptyKey_, false);
171 }
172
173 idx = ProbeFcn()(idx, numProbes, capacity_);
174 }
175 }
176
177 private:
178 size_t keyToAnchorIdx(const KeyT k) const
179 {
180 const size_t hashVal = hasher_(k);
181 const size_t probe = hashVal & kAnchorMask_;
182 return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
183 }
184
185}; // AtomicHashSet
186
187} // namespace mikk
#define UNLIKELY(x)
#define LIKELY(x)
AtomicHashSet & operator=(const AtomicHashSet &)=delete
AtomicHashSet(size_t maxSize, KeyHash hasher=KeyHash(), KeyEqual equalityChecker=KeyEqual(), const Config &c=Config())
bool tryUpdateCell(std::atomic< KeyT > *cell, KeyT &existingKey, KeyT newKey)
bool tryUpdateCell(KeyT *cell, KeyT &existingKey, KeyT newKey)
std::pair< KeyT, bool > emplace(KeyT key)
~AtomicHashSet()=default
AtomicHashSet(const AtomicHashSet &)=delete
#define assert(assertion)
#define capacity(const)
size_t operator()(size_t idx, size_t, size_t capacity) const
size_t operator()(size_t idx, size_t numProbes, size_t capacity) const