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.
20 #include <folly/concurrency/ConcurrentHashMap.h>
21 #include <folly/hash/Hash.h>
22 #include <folly/portability/GTest.h>
23 #include <folly/test/DeterministicSchedule.h>
25 using namespace folly::test;
26 using namespace folly;
29 DEFINE_int64(seed, 0, "Seed for random number generators");
31 TEST(ConcurrentHashMap, MapTest) {
32 ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
33 foomap.max_load_factor(1.05);
34 EXPECT_TRUE(foomap.empty());
35 EXPECT_EQ(foomap.find(1), foomap.cend());
36 auto r = foomap.insert(1, 0);
37 EXPECT_TRUE(r.second);
38 auto r2 = foomap.insert(1, 0);
39 EXPECT_EQ(r.first->second, 0);
40 EXPECT_EQ(r.first->first, 1);
41 EXPECT_EQ(r2.first->second, 0);
42 EXPECT_EQ(r2.first->first, 1);
43 EXPECT_EQ(r.first, r2.first);
44 EXPECT_TRUE(r.second);
45 EXPECT_FALSE(r2.second);
46 EXPECT_FALSE(foomap.empty());
47 EXPECT_TRUE(foomap.insert(std::make_pair(2, 0)).second);
48 EXPECT_TRUE(foomap.insert_or_assign(2, 0).second);
49 EXPECT_TRUE(foomap.assign_if_equal(2, 0, 3));
50 EXPECT_TRUE(foomap.insert(3, 0).second);
51 EXPECT_NE(foomap.find(1), foomap.cend());
52 EXPECT_NE(foomap.find(2), foomap.cend());
53 EXPECT_EQ(foomap.find(2)->second, 3);
54 EXPECT_EQ(foomap[2], 3);
55 EXPECT_EQ(foomap[20], 0);
56 EXPECT_EQ(foomap.at(20), 0);
57 EXPECT_FALSE(foomap.insert(1, 0).second);
58 auto l = foomap.find(1);
60 EXPECT_FALSE(foomap.erase(1));
61 EXPECT_EQ(foomap.find(1), foomap.cend());
62 auto res = foomap.find(2);
63 EXPECT_NE(res, foomap.cend());
64 EXPECT_EQ(3, res->second);
65 EXPECT_FALSE(foomap.empty());
67 EXPECT_TRUE(foomap.empty());
70 TEST(ConcurrentHashMap, MaxSizeTest) {
71 ConcurrentHashMap<uint64_t, uint64_t> foomap(2, 16);
72 bool insert_failed = false;
73 for (int i = 0; i < 32; i++) {
74 auto res = foomap.insert(0, 0);
79 EXPECT_TRUE(insert_failed);
82 TEST(ConcurrentHashMap, MoveTest) {
83 ConcurrentHashMap<uint64_t, uint64_t> foomap(2, 16);
84 auto other = std::move(foomap);
85 auto other2 = std::move(other);
86 other = std::move(other2);
92 foo(foo&& o) noexcept {
96 foo& operator=(foo&& o) {
101 foo& operator=(const foo& o) {
115 TEST(ConcurrentHashMap, EmplaceTest) {
116 ConcurrentHashMap<uint64_t, foo> foomap(200);
117 foomap.insert(1, foo());
118 EXPECT_EQ(foo::moved, 0);
119 EXPECT_EQ(foo::copied, 1);
121 // The difference between emplace and try_emplace:
122 // If insertion fails, try_emplace does not move its argument
123 foomap.try_emplace(1, foo());
124 EXPECT_EQ(foo::moved, 0);
125 EXPECT_EQ(foo::copied, 0);
126 foomap.emplace(1, foo());
127 EXPECT_EQ(foo::moved, 1);
128 EXPECT_EQ(foo::copied, 0);
131 TEST(ConcurrentHashMap, MapResizeTest) {
132 ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
133 EXPECT_EQ(foomap.find(1), foomap.cend());
134 EXPECT_TRUE(foomap.insert(1, 0).second);
135 EXPECT_TRUE(foomap.insert(2, 0).second);
136 EXPECT_TRUE(foomap.insert(3, 0).second);
137 EXPECT_TRUE(foomap.insert(4, 0).second);
139 EXPECT_NE(foomap.find(1), foomap.cend());
140 EXPECT_NE(foomap.find(2), foomap.cend());
141 EXPECT_FALSE(foomap.insert(1, 0).second);
142 EXPECT_TRUE(foomap.erase(1));
143 EXPECT_EQ(foomap.find(1), foomap.cend());
144 auto res = foomap.find(2);
145 EXPECT_NE(res, foomap.cend());
146 if (res != foomap.cend()) {
147 EXPECT_EQ(0, res->second);
151 // Ensure we can insert objects without copy constructors.
152 TEST(ConcurrentHashMap, MapNoCopiesTest) {
157 Uncopyable(const Uncopyable& that) = delete;
159 ConcurrentHashMap<uint64_t, Uncopyable> foomap(2);
160 EXPECT_TRUE(foomap.try_emplace(1, 1).second);
161 EXPECT_TRUE(foomap.try_emplace(2, 2).second);
162 auto res = foomap.find(2);
163 EXPECT_NE(res, foomap.cend());
165 EXPECT_TRUE(foomap.try_emplace(3, 3).second);
167 auto res2 = foomap.find(2);
168 EXPECT_NE(res2, foomap.cend());
169 EXPECT_EQ(&(res->second), &(res2->second));
172 TEST(ConcurrentHashMap, MapUpdateTest) {
173 ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
174 EXPECT_TRUE(foomap.insert(1, 10).second);
175 EXPECT_TRUE(bool(foomap.assign(1, 11)));
176 auto res = foomap.find(1);
177 EXPECT_NE(res, foomap.cend());
178 EXPECT_EQ(11, res->second);
181 TEST(ConcurrentHashMap, MapIterateTest2) {
182 ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
183 auto begin = foomap.cbegin();
184 auto end = foomap.cend();
185 EXPECT_EQ(begin, end);
188 TEST(ConcurrentHashMap, MapIterateTest) {
189 ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
190 EXPECT_EQ(foomap.cbegin(), foomap.cend());
191 EXPECT_TRUE(foomap.insert(1, 1).second);
192 EXPECT_TRUE(foomap.insert(2, 2).second);
193 auto iter = foomap.cbegin();
194 EXPECT_NE(iter, foomap.cend());
195 EXPECT_EQ(iter->first, 1);
196 EXPECT_EQ(iter->second, 1);
198 EXPECT_NE(iter, foomap.cend());
199 EXPECT_EQ(iter->first, 2);
200 EXPECT_EQ(iter->second, 2);
202 EXPECT_EQ(iter, foomap.cend());
205 for (auto it = foomap.cbegin(); it != foomap.cend(); it++) {
211 TEST(ConcurrentHashMap, EraseTest) {
212 ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
214 auto f1 = foomap.find(1);
215 EXPECT_EQ(1, foomap.erase(1));
219 // TODO: hazptrs must support DeterministicSchedule
221 #define Atom std::atomic // DeterministicAtomic
222 #define Mutex std::mutex // DeterministicMutex
223 #define lib std // DeterministicSchedule
224 #define join t.join() // DeterministicSchedule::join(t)
225 // #define Atom DeterministicAtomic
226 // #define Mutex DeterministicMutex
227 // #define lib DeterministicSchedule
228 // #define join DeterministicSchedule::join(t)
230 TEST(ConcurrentHashMap, UpdateStressTest) {
231 DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
233 // size must match iters for this test.
234 unsigned size = 128 * 128;
235 unsigned iters = size;
239 std::hash<unsigned long>,
240 std::equal_to<unsigned long>,
241 std::allocator<uint8_t>,
247 for (uint i = 0; i < size; i++) {
250 std::vector<std::thread> threads;
251 unsigned int num_threads = 32;
252 for (uint t = 0; t < num_threads; t++) {
253 threads.push_back(lib::thread([&, t]() {
254 int offset = (iters * t / num_threads);
255 for (uint i = 0; i < iters / num_threads; i++) {
256 unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
257 k = k % (iters / num_threads) + offset;
258 unsigned long val = 3;
259 auto res = m.find(k);
260 EXPECT_NE(res, m.cend());
261 EXPECT_EQ(k, res->second);
262 auto r = m.assign(k, res->second);
265 EXPECT_NE(res, m.cend());
266 EXPECT_EQ(k, res->second);
267 // Another random insertion to force table resizes
268 val = size + i + offset;
269 EXPECT_TRUE(m.insert(val, val).second);
273 for (auto& t : threads) {
278 TEST(ConcurrentHashMap, EraseStressTest) {
279 DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
282 unsigned iters = size * 128 * 2;
286 std::hash<unsigned long>,
287 std::equal_to<unsigned long>,
288 std::allocator<uint8_t>,
294 for (uint i = 0; i < size; i++) {
295 unsigned long k = folly::hash::jenkins_rev_mix32(i);
298 std::vector<std::thread> threads;
299 unsigned int num_threads = 32;
300 for (uint t = 0; t < num_threads; t++) {
301 threads.push_back(lib::thread([&, t]() {
302 int offset = (iters * t / num_threads);
303 for (uint i = 0; i < iters / num_threads; i++) {
304 unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
305 auto res = m.insert(k, k).second;
309 printf("Faulre to erase thread %i val %li\n", t, k);
314 res = m.insert(k, k).second;
316 res = bool(m.assign(k, k));
318 printf("Thread %i update fail %li res%i\n", t, k, res);
322 auto res = m.find(k);
323 if (res == m.cend()) {
324 printf("Thread %i lookup fail %li\n", t, k);
327 EXPECT_EQ(k, res->second);
332 for (auto& t : threads) {
337 TEST(ConcurrentHashMap, IterateStressTest) {
338 DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
341 unsigned iters = size * 128 * 2;
345 std::hash<unsigned long>,
346 std::equal_to<unsigned long>,
347 std::allocator<uint8_t>,
353 for (uint i = 0; i < size; i++) {
354 unsigned long k = folly::hash::jenkins_rev_mix32(i);
357 for (uint i = 0; i < 10; i++) {
360 std::vector<std::thread> threads;
361 unsigned int num_threads = 32;
362 for (uint t = 0; t < num_threads; t++) {
363 threads.push_back(lib::thread([&, t]() {
364 int offset = (iters * t / num_threads);
365 for (uint i = 0; i < iters / num_threads; i++) {
366 unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
367 auto res = m.insert(k, k).second;
371 printf("Faulre to erase thread %i val %li\n", t, k);
377 for (auto it = m.cbegin(); it != m.cend(); it++) {
378 printf("Item is %li\n", it->first);
379 if (it->first < 10) {
383 EXPECT_EQ(count, 10);
387 for (auto& t : threads) {
392 TEST(ConcurrentHashMap, insertStressTest) {
393 DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
396 unsigned iters = size * 64 * 4;
400 std::hash<unsigned long>,
401 std::equal_to<unsigned long>,
402 std::allocator<uint8_t>,
408 EXPECT_TRUE(m.insert(0, 0).second);
409 EXPECT_FALSE(m.insert(0, 0).second);
410 std::vector<std::thread> threads;
411 unsigned int num_threads = 32;
412 for (uint t = 0; t < num_threads; t++) {
413 threads.push_back(lib::thread([&, t]() {
414 int offset = (iters * t / num_threads);
415 for (uint i = 0; i < iters / num_threads; i++) {
416 auto var = offset + i + 1;
417 EXPECT_TRUE(m.insert(var, var).second);
418 EXPECT_FALSE(m.insert(0, 0).second);
422 for (auto& t : threads) {
427 TEST(ConcurrentHashMap, assignStressTest) {
428 DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
431 unsigned iters = size * 64 * 4;
441 void set(uint64_t v) {
442 v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
458 std::hash<unsigned long>,
459 std::equal_to<unsigned long>,
460 std::allocator<uint8_t>,
466 for (uint i = 0; i < iters; i++) {
472 std::vector<std::thread> threads;
473 unsigned int num_threads = 32;
474 for (uint t = 0; t < num_threads; t++) {
475 threads.push_back(lib::thread([&]() {
476 for (uint i = 0; i < iters; i++) {
477 auto res = m.find(i);
478 EXPECT_NE(res, m.cend());
481 b.set(res->second.v1 + 1);
486 for (auto& t : threads) {