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   foo bar; // Make sure to test copy
 118   foomap.insert(1, bar);
 119   EXPECT_EQ(foo::moved, 0);
 120   EXPECT_EQ(foo::copied, 1);
 121   foo::copied = 0;
 122   // The difference between emplace and try_emplace:
 123   // If insertion fails, try_emplace does not move its argument
 124   foomap.try_emplace(1, foo());
 125   EXPECT_EQ(foo::moved, 0);
 126   EXPECT_EQ(foo::copied, 0);
 127   foomap.emplace(1, foo());
 128   EXPECT_EQ(foo::moved, 1);
 129   EXPECT_EQ(foo::copied, 0);
 130 }
 131
 132 TEST(ConcurrentHashMap, MapResizeTest) {
 133   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
 134   EXPECT_EQ(foomap.find(1), foomap.cend());
 135   EXPECT_TRUE(foomap.insert(1, 0).second);
 136   EXPECT_TRUE(foomap.insert(2, 0).second);
 137   EXPECT_TRUE(foomap.insert(3, 0).second);
 138   EXPECT_TRUE(foomap.insert(4, 0).second);
 139   foomap.reserve(512);
 140   EXPECT_NE(foomap.find(1), foomap.cend());
 141   EXPECT_NE(foomap.find(2), foomap.cend());
 142   EXPECT_FALSE(foomap.insert(1, 0).second);
 143   EXPECT_TRUE(foomap.erase(1));
 144   EXPECT_EQ(foomap.find(1), foomap.cend());
 145   auto res = foomap.find(2);
 146   EXPECT_NE(res, foomap.cend());
 147   if (res != foomap.cend()) {
 148     EXPECT_EQ(0, res->second);
 149   }
 150 }
 151
 152 // Ensure we can insert objects without copy constructors.
 153 TEST(ConcurrentHashMap, MapNoCopiesTest) {
 154   struct Uncopyable {
 155     int i_;
 156     Uncopyable(int i) {
 157       i_ = i;
 158     }
 159     Uncopyable(const Uncopyable& that) = delete;
 160     bool operator==(const Uncopyable& o) const {
 161       return i_ == o.i_;
 162     }
 163   };
 164   struct Hasher {
 165     size_t operator()(const Uncopyable&) const {
 166       return 0;
 167     }
 168   };
 169   ConcurrentHashMap<Uncopyable, Uncopyable, Hasher> foomap(2);
 170   EXPECT_TRUE(foomap.try_emplace(1, 1).second);
 171   EXPECT_TRUE(foomap.try_emplace(2, 2).second);
 172   auto res = foomap.find(2);
 173   EXPECT_NE(res, foomap.cend());
 174
 175   EXPECT_TRUE(foomap.try_emplace(3, 3).second);
 176
 177   auto res2 = foomap.find(2);
 178   EXPECT_NE(res2, foomap.cend());
 179   EXPECT_EQ(&(res->second), &(res2->second));
 180 }
 181
 182 TEST(ConcurrentHashMap, MapMovableKeysTest) {
 183   struct Movable {
 184     int i_;
 185     Movable(int i) {
 186       i_ = i;
 187     }
 188     Movable(const Movable&) = delete;
 189     Movable(Movable&& o) {
 190       i_ = o.i_;
 191       o.i_ = 0;
 192     }
 193     bool operator==(const Movable& o) const {
 194       return i_ == o.i_;
 195     }
 196   };
 197   struct Hasher {
 198     size_t operator()(const Movable&) const {
 199       return 0;
 200     }
 201   };
 202   ConcurrentHashMap<Movable, Movable, Hasher> foomap(2);
 203   EXPECT_TRUE(foomap.insert(std::make_pair(Movable(10), Movable(1))).second);
 204   EXPECT_TRUE(foomap.assign(Movable(10), Movable(2)));
 205   EXPECT_TRUE(foomap.insert(Movable(11), Movable(1)).second);
 206   EXPECT_TRUE(foomap.emplace(Movable(12), Movable(1)).second);
 207   EXPECT_TRUE(foomap.insert_or_assign(Movable(10), Movable(3)).second);
 208   EXPECT_TRUE(foomap.assign_if_equal(Movable(10), Movable(3), Movable(4)));
 209   EXPECT_FALSE(foomap.try_emplace(Movable(10), Movable(3)).second);
 210   EXPECT_TRUE(foomap.try_emplace(Movable(13), Movable(3)).second);
 211 }
 212
 213 TEST(ConcurrentHashMap, MapUpdateTest) {
 214   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
 215   EXPECT_TRUE(foomap.insert(1, 10).second);
 216   EXPECT_TRUE(bool(foomap.assign(1, 11)));
 217   auto res = foomap.find(1);
 218   EXPECT_NE(res, foomap.cend());
 219   EXPECT_EQ(11, res->second);
 220 }
 221
 222 TEST(ConcurrentHashMap, MapIterateTest2) {
 223   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
 224   auto begin = foomap.cbegin();
 225   auto end = foomap.cend();
 226   EXPECT_EQ(begin, end);
 227 }
 228
 229 TEST(ConcurrentHashMap, MapIterateTest) {
 230   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
 231   EXPECT_EQ(foomap.cbegin(), foomap.cend());
 232   EXPECT_TRUE(foomap.insert(1, 1).second);
 233   EXPECT_TRUE(foomap.insert(2, 2).second);
 234   auto iter = foomap.cbegin();
 235   EXPECT_NE(iter, foomap.cend());
 236   EXPECT_EQ(iter->first, 1);
 237   EXPECT_EQ(iter->second, 1);
 238   iter++;
 239   EXPECT_NE(iter, foomap.cend());
 240   EXPECT_EQ(iter->first, 2);
 241   EXPECT_EQ(iter->second, 2);
 242   iter++;
 243   EXPECT_EQ(iter, foomap.cend());
 244
 245   int count = 0;
 246   for (auto it = foomap.cbegin(); it != foomap.cend(); it++) {
 247     count++;
 248   }
 249   EXPECT_EQ(count, 2);
 250 }
 251
 252 TEST(ConcurrentHashMap, EraseTest) {
 253   ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
 254   foomap.insert(1, 0);
 255   auto f1 = foomap.find(1);
 256   EXPECT_EQ(1, foomap.erase(1));
 257   foomap.erase(f1);
 258 }
 259
 260 TEST(ConcurrentHashMap, EraseInIterateTest) {
 261   ConcurrentHashMap<uint64_t, uint64_t> foomap(3);
 262   for (uint64_t k = 0; k < 10; ++k) {
 263     foomap.insert(k, k);
 264   }
 265   for (auto it = foomap.cbegin(); it != foomap.cend();) {
 266     if (it->second > 3) {
 267       it = foomap.erase(it);
 268     } else {
 269       ++it;
 270     }
 271   }
 272   EXPECT_EQ(4, foomap.size());
 273   for (auto it = foomap.cbegin(); it != foomap.cend(); ++it) {
 274     EXPECT_GE(3, it->second);
 275   }
 276 }
 277
 278 // TODO: hazptrs must support DeterministicSchedule
 279
 280 #define Atom std::atomic // DeterministicAtomic
 281 #define Mutex std::mutex // DeterministicMutex
 282 #define lib std // DeterministicSchedule
 283 #define join t.join() // DeterministicSchedule::join(t)
 284 // #define Atom DeterministicAtomic
 285 // #define Mutex DeterministicMutex
 286 // #define lib DeterministicSchedule
 287 // #define join DeterministicSchedule::join(t)
 288
 289 TEST(ConcurrentHashMap, UpdateStressTest) {
 290   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 291
 292   // size must match iters for this test.
 293   unsigned size = 128 * 128;
 294   unsigned iters = size;
 295   ConcurrentHashMap<
 296       unsigned long,
 297       unsigned long,
 298       std::hash<unsigned long>,
 299       std::equal_to<unsigned long>,
 300       std::allocator<uint8_t>,
 301       8,
 302       Atom,
 303       Mutex>
 304       m(2);
 305
 306   for (uint i = 0; i < size; i++) {
 307     m.insert(i, i);
 308   }
 309   std::vector<std::thread> threads;
 310   unsigned int num_threads = 32;
 311   for (uint t = 0; t < num_threads; t++) {
 312     threads.push_back(lib::thread([&, t]() {
 313       int offset = (iters * t / num_threads);
 314       for (uint i = 0; i < iters / num_threads; i++) {
 315         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 316         k = k % (iters / num_threads) + offset;
 317         unsigned long val = 3;
 318         auto res = m.find(k);
 319         EXPECT_NE(res, m.cend());
 320         EXPECT_EQ(k, res->second);
 321         auto r = m.assign(k, res->second);
 322         EXPECT_TRUE(r);
 323         res = m.find(k);
 324         EXPECT_NE(res, m.cend());
 325         EXPECT_EQ(k, res->second);
 326         // Another random insertion to force table resizes
 327         val = size + i + offset;
 328         EXPECT_TRUE(m.insert(val, val).second);
 329       }
 330     }));
 331   }
 332   for (auto& t : threads) {
 333     join;
 334   }
 335 }
 336
 337 TEST(ConcurrentHashMap, EraseStressTest) {
 338   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 339
 340   unsigned size = 2;
 341   unsigned iters = size * 128 * 2;
 342   ConcurrentHashMap<
 343       unsigned long,
 344       unsigned long,
 345       std::hash<unsigned long>,
 346       std::equal_to<unsigned long>,
 347       std::allocator<uint8_t>,
 348       8,
 349       Atom,
 350       Mutex>
 351       m(2);
 352
 353   for (uint i = 0; i < size; i++) {
 354     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 355     m.insert(k, k);
 356   }
 357   std::vector<std::thread> threads;
 358   unsigned int num_threads = 32;
 359   for (uint t = 0; t < num_threads; t++) {
 360     threads.push_back(lib::thread([&, t]() {
 361       int offset = (iters * t / num_threads);
 362       for (uint i = 0; i < iters / num_threads; i++) {
 363         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 364         auto res = m.insert(k, k).second;
 365         if (res) {
 366           res = m.erase(k);
 367           if (!res) {
 368             printf("Faulre to erase thread %i val %li\n", t, k);
 369             exit(0);
 370           }
 371           EXPECT_TRUE(res);
 372         }
 373         res = m.insert(k, k).second;
 374         if (res) {
 375           res = bool(m.assign(k, k));
 376           if (!res) {
 377             printf("Thread %i update fail %li res%i\n", t, k, res);
 378             exit(0);
 379           }
 380           EXPECT_TRUE(res);
 381           auto res = m.find(k);
 382           if (res == m.cend()) {
 383             printf("Thread %i lookup fail %li\n", t, k);
 384             exit(0);
 385           }
 386           EXPECT_EQ(k, res->second);
 387         }
 388       }
 389     }));
 390   }
 391   for (auto& t : threads) {
 392     join;
 393   }
 394 }
 395
 396 TEST(ConcurrentHashMap, IterateStressTest) {
 397   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 398
 399   unsigned size = 2;
 400   unsigned iters = size * 128 * 2;
 401   ConcurrentHashMap<
 402       unsigned long,
 403       unsigned long,
 404       std::hash<unsigned long>,
 405       std::equal_to<unsigned long>,
 406       std::allocator<uint8_t>,
 407       8,
 408       Atom,
 409       Mutex>
 410       m(2);
 411
 412   for (uint i = 0; i < size; i++) {
 413     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 414     m.insert(k, k);
 415   }
 416   for (uint i = 0; i < 10; i++) {
 417     m.insert(i, i);
 418   }
 419   std::vector<std::thread> threads;
 420   unsigned int num_threads = 32;
 421   for (uint t = 0; t < num_threads; t++) {
 422     threads.push_back(lib::thread([&, t]() {
 423       int offset = (iters * t / num_threads);
 424       for (uint i = 0; i < iters / num_threads; i++) {
 425         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 426         auto res = m.insert(k, k).second;
 427         if (res) {
 428           res = m.erase(k);
 429           if (!res) {
 430             printf("Faulre to erase thread %i val %li\n", t, k);
 431             exit(0);
 432           }
 433           EXPECT_TRUE(res);
 434         }
 435         int count = 0;
 436         for (auto it = m.cbegin(); it != m.cend(); it++) {
 437           printf("Item is %li\n", it->first);
 438           if (it->first < 10) {
 439             count++;
 440           }
 441         }
 442         EXPECT_EQ(count, 10);
 443       }
 444     }));
 445   }
 446   for (auto& t : threads) {
 447     join;
 448   }
 449 }
 450
 451 TEST(ConcurrentHashMap, insertStressTest) {
 452   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 453
 454   unsigned size = 2;
 455   unsigned iters = size * 64 * 4;
 456   ConcurrentHashMap<
 457       unsigned long,
 458       unsigned long,
 459       std::hash<unsigned long>,
 460       std::equal_to<unsigned long>,
 461       std::allocator<uint8_t>,
 462       8,
 463       Atom,
 464       Mutex>
 465       m(2);
 466
 467   EXPECT_TRUE(m.insert(0, 0).second);
 468   EXPECT_FALSE(m.insert(0, 0).second);
 469   std::vector<std::thread> threads;
 470   unsigned int num_threads = 32;
 471   for (uint t = 0; t < num_threads; t++) {
 472     threads.push_back(lib::thread([&, t]() {
 473       int offset = (iters * t / num_threads);
 474       for (uint i = 0; i < iters / num_threads; i++) {
 475         auto var = offset + i + 1;
 476         EXPECT_TRUE(m.insert(var, var).second);
 477         EXPECT_FALSE(m.insert(0, 0).second);
 478       }
 479     }));
 480   }
 481   for (auto& t : threads) {
 482     join;
 483   }
 484 }
 485
 486 TEST(ConcurrentHashMap, assignStressTest) {
 487   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 488
 489   unsigned size = 2;
 490   unsigned iters = size * 64 * 4;
 491   struct big_value {
 492     uint64_t v1;
 493     uint64_t v2;
 494     uint64_t v3;
 495     uint64_t v4;
 496     uint64_t v5;
 497     uint64_t v6;
 498     uint64_t v7;
 499     uint64_t v8;
 500     void set(uint64_t v) {
 501       v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
 502     }
 503     void check() const {
 504       auto v = v1;
 505       EXPECT_EQ(v, v8);
 506       EXPECT_EQ(v, v7);
 507       EXPECT_EQ(v, v6);
 508       EXPECT_EQ(v, v5);
 509       EXPECT_EQ(v, v4);
 510       EXPECT_EQ(v, v3);
 511       EXPECT_EQ(v, v2);
 512     }
 513   };
 514   ConcurrentHashMap<
 515       unsigned long,
 516       big_value,
 517       std::hash<unsigned long>,
 518       std::equal_to<unsigned long>,
 519       std::allocator<uint8_t>,
 520       8,
 521       Atom,
 522       Mutex>
 523       m(2);
 524
 525   for (uint i = 0; i < iters; i++) {
 526     big_value a;
 527     a.set(i);
 528     m.insert(i, a);
 529   }
 530
 531   std::vector<std::thread> threads;
 532   unsigned int num_threads = 32;
 533   for (uint t = 0; t < num_threads; t++) {
 534     threads.push_back(lib::thread([&]() {
 535       for (uint i = 0; i < iters; i++) {
 536         auto res = m.find(i);
 537         EXPECT_NE(res, m.cend());
 538         res->second.check();
 539         big_value b;
 540         b.set(res->second.v1 + 1);
 541         m.assign(i, b);
 542       }
 543     }));
 544   }
 545   for (auto& t : threads) {
 546     join;
 547   }
 548 }