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/Hash.h>
  21 #include <folly/concurrency/ConcurrentHashMap.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         unsigned long val;
 298         auto res = m.insert(k, k).second;
 299         if (res) {
 300           res = m.erase(k);
 301           if (!res) {
 302             printf("Faulre to erase thread %i val %li\n", t, k);
 303             exit(0);
 304           }
 305           EXPECT_TRUE(res);
 306         }
 307         res = m.insert(k, k).second;
 308         if (res) {
 309           res = bool(m.assign(k, k));
 310           if (!res) {
 311             printf("Thread %i update fail %li res%i\n", t, k, res);
 312             exit(0);
 313           }
 314           EXPECT_TRUE(res);
 315           auto res = m.find(k);
 316           if (res == m.cend()) {
 317             printf("Thread %i lookup fail %li\n", t, k);
 318             exit(0);
 319           }
 320           EXPECT_EQ(k, res->second);
 321         }
 322       }
 323     }));
 324   }
 325   for (auto& t : threads) {
 326     join;
 327   }
 328 }
 329
 330 TEST(ConcurrentHashMap, IterateStressTest) {
 331   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 332
 333   unsigned size = 2;
 334   unsigned iters = size * 128 * 2;
 335   ConcurrentHashMap<
 336       unsigned long,
 337       unsigned long,
 338       std::hash<unsigned long>,
 339       std::equal_to<unsigned long>,
 340       std::allocator<uint8_t>,
 341       8,
 342       Atom,
 343       Mutex>
 344       m(2);
 345
 346   for (uint i = 0; i < size; i++) {
 347     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 348     m.insert(k, k);
 349   }
 350   for (uint i = 0; i < 10; i++) {
 351     m.insert(i, i);
 352   }
 353   std::vector<std::thread> threads;
 354   unsigned int num_threads = 32;
 355   for (uint t = 0; t < num_threads; t++) {
 356     threads.push_back(lib::thread([&, t]() {
 357       int offset = (iters * t / num_threads);
 358       for (uint i = 0; i < iters / num_threads; i++) {
 359         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 360         unsigned long val;
 361         auto res = m.insert(k, k).second;
 362         if (res) {
 363           res = m.erase(k);
 364           if (!res) {
 365             printf("Faulre to erase thread %i val %li\n", t, k);
 366             exit(0);
 367           }
 368           EXPECT_TRUE(res);
 369         }
 370         int count = 0;
 371         for (auto it = m.cbegin(); it != m.cend(); it++) {
 372           printf("Item is %li\n", it->first);
 373           if (it->first < 10) {
 374             count++;
 375           }
 376         }
 377         EXPECT_EQ(count, 10);
 378       }
 379     }));
 380   }
 381   for (auto& t : threads) {
 382     join;
 383   }
 384 }
 385
 386 TEST(ConcurrentHashMap, insertStressTest) {
 387   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 388
 389   unsigned size = 2;
 390   unsigned iters = size * 64 * 4;
 391   ConcurrentHashMap<
 392       unsigned long,
 393       unsigned long,
 394       std::hash<unsigned long>,
 395       std::equal_to<unsigned long>,
 396       std::allocator<uint8_t>,
 397       8,
 398       Atom,
 399       Mutex>
 400       m(2);
 401
 402   EXPECT_TRUE(m.insert(0, 0).second);
 403   EXPECT_FALSE(m.insert(0, 0).second);
 404   std::vector<std::thread> threads;
 405   unsigned int num_threads = 32;
 406   for (uint t = 0; t < num_threads; t++) {
 407     threads.push_back(lib::thread([&, t]() {
 408       int offset = (iters * t / num_threads);
 409       for (uint i = 0; i < iters / num_threads; i++) {
 410         auto var = offset + i + 1;
 411         EXPECT_TRUE(m.insert(var, var).second);
 412         EXPECT_FALSE(m.insert(0, 0).second);
 413       }
 414     }));
 415   }
 416   for (auto& t : threads) {
 417     join;
 418   }
 419 }
 420
 421 TEST(ConcurrentHashMap, assignStressTest) {
 422   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 423
 424   unsigned size = 2;
 425   unsigned iters = size * 64 * 4;
 426   struct big_value {
 427     uint64_t v1;
 428     uint64_t v2;
 429     uint64_t v3;
 430     uint64_t v4;
 431     uint64_t v5;
 432     uint64_t v6;
 433     uint64_t v7;
 434     uint64_t v8;
 435     void set(uint64_t v) {
 436       v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
 437     }
 438     void check() const {
 439       auto v = v1;
 440       EXPECT_EQ(v, v8);
 441       EXPECT_EQ(v, v7);
 442       EXPECT_EQ(v, v6);
 443       EXPECT_EQ(v, v5);
 444       EXPECT_EQ(v, v4);
 445       EXPECT_EQ(v, v3);
 446       EXPECT_EQ(v, v2);
 447     }
 448   };
 449   ConcurrentHashMap<
 450       unsigned long,
 451       big_value,
 452       std::hash<unsigned long>,
 453       std::equal_to<unsigned long>,
 454       std::allocator<uint8_t>,
 455       8,
 456       Atom,
 457       Mutex>
 458       m(2);
 459
 460   for (uint i = 0; i < iters; i++) {
 461     big_value a;
 462     a.set(i);
 463     m.insert(i, a);
 464   }
 465
 466   std::vector<std::thread> threads;
 467   unsigned int num_threads = 32;
 468   for (uint t = 0; t < num_threads; t++) {
 469     threads.push_back(lib::thread([&]() {
 470       for (uint i = 0; i < iters; i++) {
 471         auto res = m.find(i);
 472         EXPECT_NE(res, m.cend());
 473         res->second.check();
 474         big_value b;
 475         b.set(res->second.v1 + 1);
 476         m.assign(i, b);
 477       }
 478     }));
 479   }
 480   for (auto& t : threads) {
 481     join;
 482   }
 483 }