2 * Copyright 2017-present 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 #include <folly/Optional.h>
19 #include <folly/concurrency/detail/ConcurrentHashMap-detail.h>
20 #include <folly/experimental/hazptr/hazptr.h>
27 * Based on Java's ConcurrentHashMap
29 * Readers are always wait-free.
30 * Writers are sharded, but take a lock.
32 * The interface is as close to std::unordered_map as possible, but there
33 * are a handful of changes:
35 * * Iterators hold hazard pointers to the returned elements. Elements can only
36 * be accessed while Iterators are still valid!
38 * * Therefore operator[] and at() return copies, since they do not
39 * return an iterator. The returned value is const, to remind you
40 * that changes do not affect the value in the map.
42 * * erase() calls the hash function, and may fail if the hash
43 * function throws an exception.
45 * * clear() initializes new segments, and is not noexcept.
47 * * The interface adds assign_if_equal, since find() doesn't take a lock.
49 * * Only const version of find() is supported, and const iterators.
50 * Mutation must use functions provided, like assign().
52 * * iteration iterates over all the buckets in the table, unlike
53 * std::unordered_map which iterates over a linked list of elements.
54 * If the table is sparse, this may be more expensive.
56 * * rehash policy is a power of two, using supplied factor.
58 * * Allocator must be stateless.
60 * * ValueTypes without copy constructors will work, but pessimize the
64 * Single-threaded performance is extremely similar to std::unordered_map.
66 * Multithreaded performance beats anything except the lock-free
67 * atomic maps (AtomicUnorderedMap, AtomicHashMap), BUT only
68 * if you can perfectly size the atomic maps, and you don't
69 * need erase(). If you don't know the size in advance or
70 * your workload frequently calls erase(), this is the
77 typename HashFn = std::hash<KeyType>,
78 typename KeyEqual = std::equal_to<KeyType>,
79 typename Allocator = std::allocator<uint8_t>,
80 uint8_t ShardBits = 8,
81 template <typename> class Atom = std::atomic,
82 class Mutex = std::mutex>
83 class ConcurrentHashMap {
84 using SegmentT = detail::ConcurrentHashMapSegment<
93 static constexpr uint64_t NumShards = (1 << ShardBits);
94 // Slightly higher than 1.0, in case hashing to shards isn't
95 // perfectly balanced, reserve(size) will still work without
97 float load_factor_ = 1.05;
102 typedef KeyType key_type;
103 typedef ValueType mapped_type;
104 typedef std::pair<const KeyType, ValueType> value_type;
105 typedef std::size_t size_type;
106 typedef HashFn hasher;
107 typedef KeyEqual key_equal;
108 typedef ConstIterator const_iterator;
111 * Construct a ConcurrentHashMap with 1 << ShardBits shards, size
112 * and max_size given. Both size and max_size will be rounded up to
113 * the next power of two, if they are not already a power of two, so
114 * that we can index in to Shards efficiently.
116 * Insertion functions will throw bad_alloc if max_size is exceeded.
118 explicit ConcurrentHashMap(size_t size = 8, size_t max_size = 0) {
119 size_ = folly::nextPowTwo(size);
121 max_size_ = folly::nextPowTwo(max_size);
123 CHECK(max_size_ == 0 || max_size_ >= size_);
124 for (uint64_t i = 0; i < NumShards; i++) {
125 segments_[i].store(nullptr, std::memory_order_relaxed);
129 ConcurrentHashMap(ConcurrentHashMap&& o) noexcept {
130 for (uint64_t i = 0; i < NumShards; i++) {
132 o.segments_[i].load(std::memory_order_relaxed),
133 std::memory_order_relaxed);
134 o.segments_[i].store(nullptr, std::memory_order_relaxed);
138 ConcurrentHashMap& operator=(ConcurrentHashMap&& o) {
139 for (uint64_t i = 0; i < NumShards; i++) {
140 auto seg = segments_[i].load(std::memory_order_relaxed);
143 Allocator().deallocate((uint8_t*)seg, sizeof(SegmentT));
146 o.segments_[i].load(std::memory_order_relaxed),
147 std::memory_order_relaxed);
148 o.segments_[i].store(nullptr, std::memory_order_relaxed);
153 ~ConcurrentHashMap() {
154 for (uint64_t i = 0; i < NumShards; i++) {
155 auto seg = segments_[i].load(std::memory_order_relaxed);
158 Allocator().deallocate((uint8_t*)seg, sizeof(SegmentT));
163 bool empty() const noexcept {
164 for (uint64_t i = 0; i < NumShards; i++) {
165 auto seg = segments_[i].load(std::memory_order_acquire);
175 ConstIterator find(const KeyType& k) const {
176 auto segment = pickSegment(k);
177 ConstIterator res(this, segment);
178 auto seg = segments_[segment].load(std::memory_order_acquire);
179 if (!seg || !seg->find(res.it_, k)) {
180 res.segment_ = NumShards;
185 ConstIterator cend() const noexcept {
186 return ConstIterator(NumShards);
189 ConstIterator cbegin() const noexcept {
190 return ConstIterator(this);
193 std::pair<ConstIterator, bool> insert(
194 std::pair<key_type, mapped_type>&& foo) {
195 auto segment = pickSegment(foo.first);
196 std::pair<ConstIterator, bool> res(
197 std::piecewise_construct,
198 std::forward_as_tuple(this, segment),
199 std::forward_as_tuple(false));
200 res.second = ensureSegment(segment)->insert(res.first.it_, std::move(foo));
204 std::pair<ConstIterator, bool> insert(const KeyType& k, const ValueType& v) {
205 auto segment = pickSegment(k);
206 std::pair<ConstIterator, bool> res(
207 std::piecewise_construct,
208 std::forward_as_tuple(this, segment),
209 std::forward_as_tuple(false));
210 res.second = ensureSegment(segment)->insert(res.first.it_, k, v);
214 template <typename... Args>
215 std::pair<ConstIterator, bool> try_emplace(const KeyType& k, Args&&... args) {
216 auto segment = pickSegment(k);
217 std::pair<ConstIterator, bool> res(
218 std::piecewise_construct,
219 std::forward_as_tuple(this, segment),
220 std::forward_as_tuple(false));
221 res.second = ensureSegment(segment)->try_emplace(
222 res.first.it_, k, std::forward<Args>(args)...);
226 template <typename... Args>
227 std::pair<ConstIterator, bool> emplace(Args&&... args) {
228 using Node = typename SegmentT::Node;
229 auto node = (Node*)Allocator().allocate(sizeof(Node));
230 new (node) Node(std::forward<Args>(args)...);
231 auto segment = pickSegment(node->getItem().first);
232 std::pair<ConstIterator, bool> res(
233 std::piecewise_construct,
234 std::forward_as_tuple(this, segment),
235 std::forward_as_tuple(false));
236 res.second = ensureSegment(segment)->emplace(
237 res.first.it_, node->getItem().first, node);
240 Allocator().deallocate((uint8_t*)node, sizeof(Node));
245 std::pair<ConstIterator, bool> insert_or_assign(
247 const ValueType& v) {
248 auto segment = pickSegment(k);
249 std::pair<ConstIterator, bool> res(
250 std::piecewise_construct,
251 std::forward_as_tuple(this, segment),
252 std::forward_as_tuple(false));
253 res.second = ensureSegment(segment)->insert_or_assign(res.first.it_, k, v);
257 folly::Optional<ConstIterator> assign(const KeyType& k, const ValueType& v) {
258 auto segment = pickSegment(k);
259 ConstIterator res(this, segment);
260 auto seg = segments_[segment].load(std::memory_order_acquire);
262 return folly::Optional<ConstIterator>();
264 auto r = seg->assign(res.it_, k, v);
266 return folly::Optional<ConstIterator>();
272 // Assign to desired if and only if key k is equal to expected
273 folly::Optional<ConstIterator> assign_if_equal(
275 const ValueType& expected,
276 const ValueType& desired) {
277 auto segment = pickSegment(k);
278 ConstIterator res(this, segment);
279 auto seg = segments_[segment].load(std::memory_order_acquire);
281 return folly::Optional<ConstIterator>();
283 auto r = seg->assign_if_equal(res.it_, k, expected, desired);
285 return folly::Optional<ConstIterator>();
291 // Copying wrappers around insert and find.
292 // Only available for copyable types.
293 const ValueType operator[](const KeyType& key) {
294 auto item = insert(key, ValueType());
295 return item.first->second;
298 const ValueType at(const KeyType& key) const {
299 auto item = find(key);
300 if (item == cend()) {
301 throw std::out_of_range("at(): value out of range");
306 // TODO update assign interface, operator[], at
308 size_type erase(const key_type& k) {
309 auto segment = pickSegment(k);
310 auto seg = segments_[segment].load(std::memory_order_acquire);
314 return seg->erase(k);
318 // Calls the hash function, and therefore may throw.
319 ConstIterator erase(ConstIterator& pos) {
320 auto segment = pickSegment(pos->first);
321 ConstIterator res(this, segment);
323 ensureSegment(segment)->erase(res.it_, pos.it_);
324 res.next(); // May point to segment end, and need to advance.
328 // NOT noexcept, initializes new shard segments vs.
330 for (uint64_t i = 0; i < NumShards; i++) {
331 auto seg = segments_[i].load(std::memory_order_acquire);
338 void reserve(size_t count) {
339 count = count >> ShardBits;
340 for (uint64_t i = 0; i < NumShards; i++) {
341 auto seg = segments_[i].load(std::memory_order_acquire);
348 // This is a rolling size, and is not exact at any moment in time.
349 size_t size() const noexcept {
351 for (uint64_t i = 0; i < NumShards; i++) {
352 auto seg = segments_[i].load(std::memory_order_acquire);
360 float max_load_factor() const {
364 void max_load_factor(float factor) {
365 for (uint64_t i = 0; i < NumShards; i++) {
366 auto seg = segments_[i].load(std::memory_order_acquire);
368 seg->max_load_factor(factor);
373 class ConstIterator {
375 friend class ConcurrentHashMap;
377 const value_type& operator*() const {
381 const value_type* operator->() const {
385 ConstIterator& operator++() {
391 ConstIterator operator++(int) {
397 bool operator==(const ConstIterator& o) const {
398 return it_ == o.it_ && segment_ == o.segment_;
401 bool operator!=(const ConstIterator& o) const {
402 return !(*this == o);
405 ConstIterator& operator=(const ConstIterator& o) {
407 segment_ = o.segment_;
411 ConstIterator(const ConstIterator& o) {
413 segment_ = o.segment_;
416 ConstIterator(const ConcurrentHashMap* parent, uint64_t segment)
417 : segment_(segment), parent_(parent) {}
421 explicit ConstIterator(const ConcurrentHashMap* parent)
422 : it_(parent->ensureSegment(0)->cbegin()),
425 // Always iterate to the first element, could be in any shard.
430 explicit ConstIterator(uint64_t shards) : it_(nullptr), segment_(shards) {}
433 while (it_ == parent_->ensureSegment(segment_)->cend() &&
434 segment_ < parent_->NumShards) {
436 auto seg = parent_->segments_[segment_].load(std::memory_order_acquire);
437 if (segment_ < parent_->NumShards) {
446 typename SegmentT::Iterator it_;
448 const ConcurrentHashMap* parent_;
452 uint64_t pickSegment(const KeyType& k) const {
453 auto h = HashFn()(k);
454 // Use the lowest bits for our shard bits.
456 // This works well even if the hash function is biased towards the
457 // low bits: The sharding will happen in the segments_ instead of
458 // in the segment buckets, so we'll still get write sharding as
461 // Low-bit bias happens often for std::hash using small numbers,
462 // since the integer hash function is the identity function.
463 return h & (NumShards - 1);
466 SegmentT* ensureSegment(uint64_t i) const {
467 SegmentT* seg = segments_[i].load(std::memory_order_acquire);
469 SegmentT* newseg = (SegmentT*)Allocator().allocate(sizeof(SegmentT));
470 newseg = new (newseg)
471 SegmentT(size_ >> ShardBits, load_factor_, max_size_ >> ShardBits);
472 if (!segments_[i].compare_exchange_strong(seg, newseg)) {
473 // seg is updated with new value, delete ours.
475 Allocator().deallocate((uint8_t*)newseg, sizeof(SegmentT));
483 mutable Atom<SegmentT*> segments_[NumShards];