folly/concurrency/test/ConcurrentHashMapTest.cpp

   1 /*
   2  * Copyright 2017-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 #include <atomic>
  17 #include <memory>
  18 #include <thread>
  19
  20 #include <folly/concurrency/ConcurrentHashMap.h>
  21 #include <folly/hash/Hash.h>
  22 #include <folly/portability/GTest.h>
  23 #include <folly/test/DeterministicSchedule.h>
  24
  25 using namespace folly::test;
  26 using namespace folly;
  27 using namespace std;
  28
  29 DEFINE_int64(seed, 0, "Seed for random number generators");
  30
  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);
  59   foomap.erase(l);
  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());
  66   foomap.clear();
  67   EXPECT_TRUE(foomap.empty());
  68 }
  69
  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);
  75     if (!res.second) {
  76       insert_failed = true;
  77     }
  78   }
  79   EXPECT_TRUE(insert_failed);
  80 }
  81
  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);
  87 }
  88
  89 struct foo {
  90   static int moved;
  91   static int copied;
  92   foo(foo&& o) noexcept {
  93     (void*)&o;
  94     moved++;
  95   }
  96   foo& operator=(foo&& o) {
  97     (void*)&o;
  98     moved++;
  99     return *this;
 100   }
 101   foo& operator=(const foo& o) {
 102     (void*)&o;
 103     copied++;
 104     return *this;
 105   }
 106   foo(const foo& o) {
 107     (void*)&o;
 108     copied++;
 109   }
 110   foo() {}
 111 };
 112 int foo::moved{0};
 113 int foo::copied{0};
 114
 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);
 120   foo::copied = 0;
 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);
 129 }
 130
 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);
 138   foomap.reserve(512);
 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);
 148   }
 149 }
 150
 151 // Ensure we can insert objects without copy constructors.
 152 TEST(ConcurrentHashMap, MapNoCopiesTest) {
 153   struct Uncopyable {
 154     Uncopyable(int i) {
 155       (void*)&i;
 156     }
 157     Uncopyable(const Uncopyable& that) = delete;
 158   };
 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());
 164
 165   EXPECT_TRUE(foomap.try_emplace(3, 3).second);
 166
 167   auto res2 = foomap.find(2);
 168   EXPECT_NE(res2, foomap.cend());
 169   EXPECT_EQ(&(res->second), &(res2->second));
 170 }
 171
 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);
 179 }
 180
 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);
 186 }
 187
 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);
 197   iter++;
 198   EXPECT_NE(iter, foomap.cend());
 199   EXPECT_EQ(iter->first, 2);
 200   EXPECT_EQ(iter->second, 2);
 201   iter++;
 202   EXPECT_EQ(iter, foomap.cend());
 203
 204   int count = 0;
 205   for (auto it = foomap.cbegin(); it != foomap.cend(); it++) {
 206     count++;
 207   }
 208   EXPECT_EQ(count, 2);
 209 }
 210
 211 // TODO: hazptrs must support DeterministicSchedule
 212
 213 #define Atom std::atomic // DeterministicAtomic
 214 #define Mutex std::mutex // DeterministicMutex
 215 #define lib std // DeterministicSchedule
 216 #define join t.join() // DeterministicSchedule::join(t)
 217 // #define Atom DeterministicAtomic
 218 // #define Mutex DeterministicMutex
 219 // #define lib DeterministicSchedule
 220 // #define join DeterministicSchedule::join(t)
 221
 222 TEST(ConcurrentHashMap, UpdateStressTest) {
 223   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 224
 225   // size must match iters for this test.
 226   unsigned size = 128 * 128;
 227   unsigned iters = size;
 228   ConcurrentHashMap<
 229       unsigned long,
 230       unsigned long,
 231       std::hash<unsigned long>,
 232       std::equal_to<unsigned long>,
 233       std::allocator<uint8_t>,
 234       8,
 235       Atom,
 236       Mutex>
 237       m(2);
 238
 239   for (uint i = 0; i < size; i++) {
 240     m.insert(i, i);
 241   }
 242   std::vector<std::thread> threads;
 243   unsigned int num_threads = 32;
 244   for (uint t = 0; t < num_threads; t++) {
 245     threads.push_back(lib::thread([&, t]() {
 246       int offset = (iters * t / num_threads);
 247       for (uint i = 0; i < iters / num_threads; i++) {
 248         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 249         k = k % (iters / num_threads) + offset;
 250         unsigned long val = 3;
 251         auto res = m.find(k);
 252         EXPECT_NE(res, m.cend());
 253         EXPECT_EQ(k, res->second);
 254         auto r = m.assign(k, res->second);
 255         EXPECT_TRUE(r);
 256         res = m.find(k);
 257         EXPECT_NE(res, m.cend());
 258         EXPECT_EQ(k, res->second);
 259         // Another random insertion to force table resizes
 260         val = size + i + offset;
 261         EXPECT_TRUE(m.insert(val, val).second);
 262       }
 263     }));
 264   }
 265   for (auto& t : threads) {
 266     join;
 267   }
 268 }
 269
 270 TEST(ConcurrentHashMap, EraseStressTest) {
 271   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 272
 273   unsigned size = 2;
 274   unsigned iters = size * 128 * 2;
 275   ConcurrentHashMap<
 276       unsigned long,
 277       unsigned long,
 278       std::hash<unsigned long>,
 279       std::equal_to<unsigned long>,
 280       std::allocator<uint8_t>,
 281       8,
 282       Atom,
 283       Mutex>
 284       m(2);
 285
 286   for (uint i = 0; i < size; i++) {
 287     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 288     m.insert(k, k);
 289   }
 290   std::vector<std::thread> threads;
 291   unsigned int num_threads = 32;
 292   for (uint t = 0; t < num_threads; t++) {
 293     threads.push_back(lib::thread([&, t]() {
 294       int offset = (iters * t / num_threads);
 295       for (uint i = 0; i < iters / num_threads; i++) {
 296         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 297         auto res = m.insert(k, k).second;
 298         if (res) {
 299           res = m.erase(k);
 300           if (!res) {
 301             printf("Faulre to erase thread %i val %li\n", t, k);
 302             exit(0);
 303           }
 304           EXPECT_TRUE(res);
 305         }
 306         res = m.insert(k, k).second;
 307         if (res) {
 308           res = bool(m.assign(k, k));
 309           if (!res) {
 310             printf("Thread %i update fail %li res%i\n", t, k, res);
 311             exit(0);
 312           }
 313           EXPECT_TRUE(res);
 314           auto res = m.find(k);
 315           if (res == m.cend()) {
 316             printf("Thread %i lookup fail %li\n", t, k);
 317             exit(0);
 318           }
 319           EXPECT_EQ(k, res->second);
 320         }
 321       }
 322     }));
 323   }
 324   for (auto& t : threads) {
 325     join;
 326   }
 327 }
 328
 329 TEST(ConcurrentHashMap, IterateStressTest) {
 330   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 331
 332   unsigned size = 2;
 333   unsigned iters = size * 128 * 2;
 334   ConcurrentHashMap<
 335       unsigned long,
 336       unsigned long,
 337       std::hash<unsigned long>,
 338       std::equal_to<unsigned long>,
 339       std::allocator<uint8_t>,
 340       8,
 341       Atom,
 342       Mutex>
 343       m(2);
 344
 345   for (uint i = 0; i < size; i++) {
 346     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 347     m.insert(k, k);
 348   }
 349   for (uint i = 0; i < 10; i++) {
 350     m.insert(i, i);
 351   }
 352   std::vector<std::thread> threads;
 353   unsigned int num_threads = 32;
 354   for (uint t = 0; t < num_threads; t++) {
 355     threads.push_back(lib::thread([&, t]() {
 356       int offset = (iters * t / num_threads);
 357       for (uint i = 0; i < iters / num_threads; i++) {
 358         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 359         auto res = m.insert(k, k).second;
 360         if (res) {
 361           res = m.erase(k);
 362           if (!res) {
 363             printf("Faulre to erase thread %i val %li\n", t, k);
 364             exit(0);
 365           }
 366           EXPECT_TRUE(res);
 367         }
 368         int count = 0;
 369         for (auto it = m.cbegin(); it != m.cend(); it++) {
 370           printf("Item is %li\n", it->first);
 371           if (it->first < 10) {
 372             count++;
 373           }
 374         }
 375         EXPECT_EQ(count, 10);
 376       }
 377     }));
 378   }
 379   for (auto& t : threads) {
 380     join;
 381   }
 382 }
 383
 384 TEST(ConcurrentHashMap, insertStressTest) {
 385   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 386
 387   unsigned size = 2;
 388   unsigned iters = size * 64 * 4;
 389   ConcurrentHashMap<
 390       unsigned long,
 391       unsigned long,
 392       std::hash<unsigned long>,
 393       std::equal_to<unsigned long>,
 394       std::allocator<uint8_t>,
 395       8,
 396       Atom,
 397       Mutex>
 398       m(2);
 399
 400   EXPECT_TRUE(m.insert(0, 0).second);
 401   EXPECT_FALSE(m.insert(0, 0).second);
 402   std::vector<std::thread> threads;
 403   unsigned int num_threads = 32;
 404   for (uint t = 0; t < num_threads; t++) {
 405     threads.push_back(lib::thread([&, t]() {
 406       int offset = (iters * t / num_threads);
 407       for (uint i = 0; i < iters / num_threads; i++) {
 408         auto var = offset + i + 1;
 409         EXPECT_TRUE(m.insert(var, var).second);
 410         EXPECT_FALSE(m.insert(0, 0).second);
 411       }
 412     }));
 413   }
 414   for (auto& t : threads) {
 415     join;
 416   }
 417 }
 418
 419 TEST(ConcurrentHashMap, assignStressTest) {
 420   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 421
 422   unsigned size = 2;
 423   unsigned iters = size * 64 * 4;
 424   struct big_value {
 425     uint64_t v1;
 426     uint64_t v2;
 427     uint64_t v3;
 428     uint64_t v4;
 429     uint64_t v5;
 430     uint64_t v6;
 431     uint64_t v7;
 432     uint64_t v8;
 433     void set(uint64_t v) {
 434       v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
 435     }
 436     void check() const {
 437       auto v = v1;
 438       EXPECT_EQ(v, v8);
 439       EXPECT_EQ(v, v7);
 440       EXPECT_EQ(v, v6);
 441       EXPECT_EQ(v, v5);
 442       EXPECT_EQ(v, v4);
 443       EXPECT_EQ(v, v3);
 444       EXPECT_EQ(v, v2);
 445     }
 446   };
 447   ConcurrentHashMap<
 448       unsigned long,
 449       big_value,
 450       std::hash<unsigned long>,
 451       std::equal_to<unsigned long>,
 452       std::allocator<uint8_t>,
 453       8,
 454       Atom,
 455       Mutex>
 456       m(2);
 457
 458   for (uint i = 0; i < iters; i++) {
 459     big_value a;
 460     a.set(i);
 461     m.insert(i, a);
 462   }
 463
 464   std::vector<std::thread> threads;
 465   unsigned int num_threads = 32;
 466   for (uint t = 0; t < num_threads; t++) {
 467     threads.push_back(lib::thread([&]() {
 468       for (uint i = 0; i < iters; i++) {
 469         auto res = m.find(i);
 470         EXPECT_NE(res, m.cend());
 471         res->second.check();
 472         big_value b;
 473         b.set(res->second.v1 + 1);
 474         m.assign(i, b);
 475       }
 476     }));
 477   }
 478   for (auto& t : threads) {
 479     join;
 480   }
 481 }