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 // TODO: hazptrs must support DeterministicSchedule
 261
 262 #define Atom std::atomic // DeterministicAtomic
 263 #define Mutex std::mutex // DeterministicMutex
 264 #define lib std // DeterministicSchedule
 265 #define join t.join() // DeterministicSchedule::join(t)
 266 // #define Atom DeterministicAtomic
 267 // #define Mutex DeterministicMutex
 268 // #define lib DeterministicSchedule
 269 // #define join DeterministicSchedule::join(t)
 270
 271 TEST(ConcurrentHashMap, UpdateStressTest) {
 272   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 273
 274   // size must match iters for this test.
 275   unsigned size = 128 * 128;
 276   unsigned iters = size;
 277   ConcurrentHashMap<
 278       unsigned long,
 279       unsigned long,
 280       std::hash<unsigned long>,
 281       std::equal_to<unsigned long>,
 282       std::allocator<uint8_t>,
 283       8,
 284       Atom,
 285       Mutex>
 286       m(2);
 287
 288   for (uint i = 0; i < size; i++) {
 289     m.insert(i, i);
 290   }
 291   std::vector<std::thread> threads;
 292   unsigned int num_threads = 32;
 293   for (uint t = 0; t < num_threads; t++) {
 294     threads.push_back(lib::thread([&, t]() {
 295       int offset = (iters * t / num_threads);
 296       for (uint i = 0; i < iters / num_threads; i++) {
 297         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 298         k = k % (iters / num_threads) + offset;
 299         unsigned long val = 3;
 300         auto res = m.find(k);
 301         EXPECT_NE(res, m.cend());
 302         EXPECT_EQ(k, res->second);
 303         auto r = m.assign(k, res->second);
 304         EXPECT_TRUE(r);
 305         res = m.find(k);
 306         EXPECT_NE(res, m.cend());
 307         EXPECT_EQ(k, res->second);
 308         // Another random insertion to force table resizes
 309         val = size + i + offset;
 310         EXPECT_TRUE(m.insert(val, val).second);
 311       }
 312     }));
 313   }
 314   for (auto& t : threads) {
 315     join;
 316   }
 317 }
 318
 319 TEST(ConcurrentHashMap, EraseStressTest) {
 320   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 321
 322   unsigned size = 2;
 323   unsigned iters = size * 128 * 2;
 324   ConcurrentHashMap<
 325       unsigned long,
 326       unsigned long,
 327       std::hash<unsigned long>,
 328       std::equal_to<unsigned long>,
 329       std::allocator<uint8_t>,
 330       8,
 331       Atom,
 332       Mutex>
 333       m(2);
 334
 335   for (uint i = 0; i < size; i++) {
 336     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 337     m.insert(k, k);
 338   }
 339   std::vector<std::thread> threads;
 340   unsigned int num_threads = 32;
 341   for (uint t = 0; t < num_threads; t++) {
 342     threads.push_back(lib::thread([&, t]() {
 343       int offset = (iters * t / num_threads);
 344       for (uint i = 0; i < iters / num_threads; i++) {
 345         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 346         auto res = m.insert(k, k).second;
 347         if (res) {
 348           res = m.erase(k);
 349           if (!res) {
 350             printf("Faulre to erase thread %i val %li\n", t, k);
 351             exit(0);
 352           }
 353           EXPECT_TRUE(res);
 354         }
 355         res = m.insert(k, k).second;
 356         if (res) {
 357           res = bool(m.assign(k, k));
 358           if (!res) {
 359             printf("Thread %i update fail %li res%i\n", t, k, res);
 360             exit(0);
 361           }
 362           EXPECT_TRUE(res);
 363           auto res = m.find(k);
 364           if (res == m.cend()) {
 365             printf("Thread %i lookup fail %li\n", t, k);
 366             exit(0);
 367           }
 368           EXPECT_EQ(k, res->second);
 369         }
 370       }
 371     }));
 372   }
 373   for (auto& t : threads) {
 374     join;
 375   }
 376 }
 377
 378 TEST(ConcurrentHashMap, IterateStressTest) {
 379   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 380
 381   unsigned size = 2;
 382   unsigned iters = size * 128 * 2;
 383   ConcurrentHashMap<
 384       unsigned long,
 385       unsigned long,
 386       std::hash<unsigned long>,
 387       std::equal_to<unsigned long>,
 388       std::allocator<uint8_t>,
 389       8,
 390       Atom,
 391       Mutex>
 392       m(2);
 393
 394   for (uint i = 0; i < size; i++) {
 395     unsigned long k = folly::hash::jenkins_rev_mix32(i);
 396     m.insert(k, k);
 397   }
 398   for (uint i = 0; i < 10; i++) {
 399     m.insert(i, i);
 400   }
 401   std::vector<std::thread> threads;
 402   unsigned int num_threads = 32;
 403   for (uint t = 0; t < num_threads; t++) {
 404     threads.push_back(lib::thread([&, t]() {
 405       int offset = (iters * t / num_threads);
 406       for (uint i = 0; i < iters / num_threads; i++) {
 407         unsigned long k = folly::hash::jenkins_rev_mix32((i + offset));
 408         auto res = m.insert(k, k).second;
 409         if (res) {
 410           res = m.erase(k);
 411           if (!res) {
 412             printf("Faulre to erase thread %i val %li\n", t, k);
 413             exit(0);
 414           }
 415           EXPECT_TRUE(res);
 416         }
 417         int count = 0;
 418         for (auto it = m.cbegin(); it != m.cend(); it++) {
 419           printf("Item is %li\n", it->first);
 420           if (it->first < 10) {
 421             count++;
 422           }
 423         }
 424         EXPECT_EQ(count, 10);
 425       }
 426     }));
 427   }
 428   for (auto& t : threads) {
 429     join;
 430   }
 431 }
 432
 433 TEST(ConcurrentHashMap, insertStressTest) {
 434   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 435
 436   unsigned size = 2;
 437   unsigned iters = size * 64 * 4;
 438   ConcurrentHashMap<
 439       unsigned long,
 440       unsigned long,
 441       std::hash<unsigned long>,
 442       std::equal_to<unsigned long>,
 443       std::allocator<uint8_t>,
 444       8,
 445       Atom,
 446       Mutex>
 447       m(2);
 448
 449   EXPECT_TRUE(m.insert(0, 0).second);
 450   EXPECT_FALSE(m.insert(0, 0).second);
 451   std::vector<std::thread> threads;
 452   unsigned int num_threads = 32;
 453   for (uint t = 0; t < num_threads; t++) {
 454     threads.push_back(lib::thread([&, t]() {
 455       int offset = (iters * t / num_threads);
 456       for (uint i = 0; i < iters / num_threads; i++) {
 457         auto var = offset + i + 1;
 458         EXPECT_TRUE(m.insert(var, var).second);
 459         EXPECT_FALSE(m.insert(0, 0).second);
 460       }
 461     }));
 462   }
 463   for (auto& t : threads) {
 464     join;
 465   }
 466 }
 467
 468 TEST(ConcurrentHashMap, assignStressTest) {
 469   DeterministicSchedule sched(DeterministicSchedule::uniform(FLAGS_seed));
 470
 471   unsigned size = 2;
 472   unsigned iters = size * 64 * 4;
 473   struct big_value {
 474     uint64_t v1;
 475     uint64_t v2;
 476     uint64_t v3;
 477     uint64_t v4;
 478     uint64_t v5;
 479     uint64_t v6;
 480     uint64_t v7;
 481     uint64_t v8;
 482     void set(uint64_t v) {
 483       v1 = v2 = v3 = v4 = v5 = v6 = v7 = v8 = v;
 484     }
 485     void check() const {
 486       auto v = v1;
 487       EXPECT_EQ(v, v8);
 488       EXPECT_EQ(v, v7);
 489       EXPECT_EQ(v, v6);
 490       EXPECT_EQ(v, v5);
 491       EXPECT_EQ(v, v4);
 492       EXPECT_EQ(v, v3);
 493       EXPECT_EQ(v, v2);
 494     }
 495   };
 496   ConcurrentHashMap<
 497       unsigned long,
 498       big_value,
 499       std::hash<unsigned long>,
 500       std::equal_to<unsigned long>,
 501       std::allocator<uint8_t>,
 502       8,
 503       Atom,
 504       Mutex>
 505       m(2);
 506
 507   for (uint i = 0; i < iters; i++) {
 508     big_value a;
 509     a.set(i);
 510     m.insert(i, a);
 511   }
 512
 513   std::vector<std::thread> threads;
 514   unsigned int num_threads = 32;
 515   for (uint t = 0; t < num_threads; t++) {
 516     threads.push_back(lib::thread([&]() {
 517       for (uint i = 0; i < iters; i++) {
 518         auto res = m.find(i);
 519         EXPECT_NE(res, m.cend());
 520         res->second.check();
 521         big_value b;
 522         b.set(res->second.v1 + 1);
 523         m.assign(i, b);
 524       }
 525     }));
 526   }
 527   for (auto& t : threads) {
 528     join;
 529   }
 530 }