folly/test/AtomicHashMapTest.cpp

   1 /*
   2  * Copyright 2017 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
  17 #include <folly/AtomicHashMap.h>
  18
  19 #include <atomic>
  20 #include <memory>
  21 #include <thread>
  22
  23 #include <glog/logging.h>
  24
  25 #include <folly/Benchmark.h>
  26 #include <folly/Conv.h>
  27 #include <folly/portability/GTest.h>
  28 #include <folly/portability/SysTime.h>
  29
  30 using std::vector;
  31 using std::string;
  32 using folly::AtomicHashMap;
  33 using folly::AtomicHashArray;
  34 using folly::StringPiece;
  35
  36 // Tunables:
  37 DEFINE_double(targetLoadFactor, 0.75, "Target memory utilization fraction.");
  38 DEFINE_double(maxLoadFactor, 0.80, "Max before growth.");
  39 DEFINE_int32(numThreads, 8, "Threads to use for concurrency tests.");
  40 DEFINE_int64(numBMElements, 12 * 1000 * 1000, "Size of maps for benchmarks.");
  41
  42 const double LF = FLAGS_maxLoadFactor / FLAGS_targetLoadFactor;
  43 const int maxBMElements = int(FLAGS_numBMElements * LF); // hit our target LF.
  44
  45 static int64_t nowInUsec() {
  46   timeval tv;
  47   gettimeofday(&tv, nullptr);
  48   return int64_t(tv.tv_sec) * 1000 * 1000 + tv.tv_usec;
  49 }
  50
  51 TEST(Ahm, BasicStrings) {
  52   typedef AtomicHashMap<int64_t,string> AHM;
  53   AHM myMap(1024);
  54   EXPECT_TRUE(myMap.begin() == myMap.end());
  55
  56   for (int i = 0; i < 100; ++i) {
  57     myMap.insert(make_pair(i, folly::to<string>(i)));
  58   }
  59   for (int i = 0; i < 100; ++i) {
  60     EXPECT_EQ(myMap.find(i)->second, folly::to<string>(i));
  61   }
  62
  63   myMap.insert(std::make_pair(999, "A"));
  64   myMap.insert(std::make_pair(999, "B"));
  65   EXPECT_EQ(myMap.find(999)->second, "A"); // shouldn't have overwritten
  66   myMap.find(999)->second = "B";
  67   myMap.find(999)->second = "C";
  68   EXPECT_EQ(myMap.find(999)->second, "C");
  69   EXPECT_EQ(myMap.find(999)->first, 999);
  70 }
  71
  72
  73 TEST(Ahm, BasicNoncopyable) {
  74   typedef AtomicHashMap<int64_t,std::unique_ptr<int>> AHM;
  75   AHM myMap(1024);
  76   EXPECT_TRUE(myMap.begin() == myMap.end());
  77
  78   for (int i = 0; i < 50; ++i) {
  79     myMap.insert(make_pair(i, std::unique_ptr<int>(new int(i))));
  80   }
  81   for (int i = 50; i < 100; ++i) {
  82     myMap.insert(i, std::unique_ptr<int>(new int (i)));
  83   }
  84   for (int i = 100; i < 150; ++i) {
  85     myMap.emplace(i, new int (i));
  86   }
  87   for (int i = 150; i < 200; ++i) {
  88     myMap.emplace(i, new int (i), std::default_delete<int>());
  89   }
  90   for (int i = 0; i < 200; ++i) {
  91     EXPECT_EQ(*(myMap.find(i)->second), i);
  92   }
  93   for (int i = 0; i < 200; i+=4) {
  94     myMap.erase(i);
  95   }
  96   for (int i = 0; i < 200; i+=4) {
  97     EXPECT_EQ(myMap.find(i), myMap.end());
  98   }
  99 }
 100
 101 typedef int32_t     KeyT;
 102 typedef int32_t     ValueT;
 103
 104 typedef AtomicHashMap<KeyT,ValueT> AHMapT;
 105 typedef AHMapT::value_type RecordT;
 106 typedef AtomicHashArray<KeyT,ValueT> AHArrayT;
 107 AHArrayT::Config config;
 108 typedef folly::QuadraticProbingAtomicHashMap<KeyT,ValueT> QPAHMapT;
 109 QPAHMapT::Config qpConfig;
 110 static AHArrayT::SmartPtr globalAHA(nullptr);
 111 static std::unique_ptr<AHMapT> globalAHM;
 112 static std::unique_ptr<QPAHMapT> globalQPAHM;
 113
 114 // Generate a deterministic value based on an input key
 115 static int genVal(int key) {
 116   return key / 3;
 117 }
 118
 119 static bool legalKey(const char* a);
 120
 121 struct EqTraits {
 122   bool operator()(const char* a, const char* b) {
 123     return legalKey(a) && (strcmp(a, b) == 0);
 124   }
 125   bool operator()(const char* a, const char& b) {
 126     return legalKey(a) && (a[0] != '\0') && (a[0] == b);
 127   }
 128   bool operator()(const char* a, const StringPiece b) {
 129     return legalKey(a) &&
 130       (strlen(a) == b.size()) && (strcmp(a, b.begin()) == 0);
 131   }
 132 };
 133
 134 struct HashTraits {
 135   size_t operator()(const char* a) {
 136     size_t result = 0;
 137     while (a[0] != 0) result += static_cast<size_t>(*(a++));
 138     return result;
 139   }
 140   size_t operator()(const char& a) {
 141     return static_cast<size_t>(a);
 142   }
 143   size_t operator()(const StringPiece a) {
 144     size_t result = 0;
 145     for (const auto& ch : a) result += static_cast<size_t>(ch);
 146     return result;
 147   }
 148 };
 149
 150 typedef AtomicHashMap<const char*, int64_t, HashTraits, EqTraits> AHMCstrInt;
 151 AHMCstrInt::Config cstrIntCfg;
 152
 153 static bool legalKey(const char* a) {
 154   return a != cstrIntCfg.emptyKey &&
 155     a != cstrIntCfg.lockedKey &&
 156     a != cstrIntCfg.erasedKey;
 157 }
 158
 159 TEST(Ahm, BasicLookup) {
 160   AHMCstrInt myMap(1024, cstrIntCfg);
 161   EXPECT_TRUE(myMap.begin() == myMap.end());
 162   myMap.insert(std::make_pair("f", 42));
 163   EXPECT_EQ(42, myMap.find("f")->second);
 164   {
 165     // Look up a single char, successfully.
 166     auto it = myMap.find<char>('f');
 167     EXPECT_EQ(42, it->second);
 168   }
 169   {
 170     // Look up a single char, unsuccessfully.
 171     auto it = myMap.find<char>('g');
 172     EXPECT_TRUE(it == myMap.end());
 173   }
 174   {
 175     // Look up a string piece, successfully.
 176     const StringPiece piece("f");
 177     auto it = myMap.find(piece);
 178     EXPECT_EQ(42, it->second);
 179   }
 180 }
 181
 182 TEST(Ahm, grow) {
 183   VLOG(1) << "Overhead: " << sizeof(AHArrayT) << " (array) " <<
 184     sizeof(AHMapT) + sizeof(AHArrayT) << " (map/set) Bytes.";
 185   uint64_t numEntries = 10000;
 186   float sizeFactor = 0.46f;
 187
 188   std::unique_ptr<AHMapT> m(new AHMapT(int(numEntries * sizeFactor), config));
 189
 190   // load map - make sure we succeed and the index is accurate
 191   bool success = true;
 192   for (uint64_t i = 0; i < numEntries; i++) {
 193     auto ret = m->insert(RecordT(i, genVal(i)));
 194     success &= ret.second;
 195     success &= (m->findAt(ret.first.getIndex())->second == genVal(i));
 196   }
 197   // Overwrite vals to make sure there are no dups
 198   // Every insert should fail because the keys are already in the map.
 199   success = true;
 200   for (uint64_t i = 0; i < numEntries; i++) {
 201     auto ret = m->insert(RecordT(i, genVal(i * 2)));
 202     success &= (ret.second == false);  // fail on collision
 203     success &= (ret.first->second == genVal(i)); // return the previous value
 204     success &= (m->findAt(ret.first.getIndex())->second == genVal(i));
 205   }
 206   EXPECT_TRUE(success);
 207
 208   // check correctness
 209   EXPECT_GT(m->numSubMaps(), 1);  // make sure we grew
 210   success = true;
 211   EXPECT_EQ(m->size(), numEntries);
 212   for (size_t i = 0; i < numEntries; i++) {
 213     success &= (m->find(i)->second == genVal(i));
 214   }
 215   EXPECT_TRUE(success);
 216
 217   // Check findAt
 218   success = true;
 219   AHMapT::const_iterator retIt;
 220   for (int32_t i = 0; i < int32_t(numEntries); i++) {
 221     retIt = m->find(i);
 222     retIt = m->findAt(retIt.getIndex());
 223     success &= (retIt->second == genVal(i));
 224     // We use a uint32_t index so that this comparison is between two
 225     // variables of the same type.
 226     success &= (retIt->first == i);
 227   }
 228   EXPECT_TRUE(success);
 229
 230   // Try modifying value
 231   m->find(8)->second = 5309;
 232   EXPECT_EQ(m->find(8)->second, 5309);
 233
 234   // check clear()
 235   m->clear();
 236   success = true;
 237   for (uint64_t i = 0; i < numEntries / 2; i++) {
 238     success &= m->insert(RecordT(i, genVal(i))).second;
 239   }
 240   EXPECT_TRUE(success);
 241   EXPECT_EQ(m->size(), numEntries / 2);
 242 }
 243
 244 TEST(Ahm, iterator) {
 245   int numEntries = 10000;
 246   float sizeFactor = .46f;
 247   std::unique_ptr<AHMapT> m(new AHMapT(int(numEntries * sizeFactor), config));
 248
 249   // load map - make sure we succeed and the index is accurate
 250   for (int i = 0; i < numEntries; i++) {
 251     m->insert(RecordT(i, genVal(i)));
 252   }
 253
 254   bool success = true;
 255   int count = 0;
 256   FOR_EACH(it, *m) {
 257     success &= (it->second == genVal(it->first));
 258     ++count;
 259   }
 260   EXPECT_TRUE(success);
 261   EXPECT_EQ(count, numEntries);
 262 }
 263
 264 class Counters {
 265  private:
 266   // Note: Unfortunately can't currently put a std::atomic<int64_t> in
 267   // the value in ahm since it doesn't support types that are both non-copy
 268   // and non-move constructible yet.
 269   AtomicHashMap<int64_t,int64_t> ahm;
 270
 271  public:
 272   explicit Counters(size_t numCounters) : ahm(numCounters) {}
 273
 274   void increment(int64_t obj_id) {
 275     auto ret = ahm.insert(std::make_pair(obj_id, 1));
 276     if (!ret.second) {
 277       // obj_id already exists, increment count
 278       __sync_fetch_and_add(&ret.first->second, 1);
 279     }
 280   }
 281
 282   int64_t getValue(int64_t obj_id) {
 283     auto ret = ahm.find(obj_id);
 284     return ret != ahm.end() ? ret->second : 0;
 285   }
 286
 287   // export the counters without blocking increments
 288   string toString() {
 289     string ret = "{\n";
 290     ret.reserve(ahm.size() * 32);
 291     for (const auto& e : ahm) {
 292       ret += folly::to<string>(
 293         "  [", e.first, ":", e.second, "]\n");
 294     }
 295     ret += "}\n";
 296     return ret;
 297   }
 298 };
 299
 300 // If you get an error "terminate called without an active exception", there
 301 // might be too many threads getting created - decrease numKeys and/or mult.
 302 TEST(Ahm, counter) {
 303   const int numKeys = 10;
 304   const int mult = 10;
 305   Counters c(numKeys);
 306   vector<int64_t> keys;
 307   FOR_EACH_RANGE(i, 1, numKeys) {
 308     keys.push_back(i);
 309   }
 310   vector<std::thread> threads;
 311   for (auto key : keys) {
 312     FOR_EACH_RANGE(i, 0, key * mult) {
 313       threads.push_back(std::thread([&, key] { c.increment(key); }));
 314     }
 315   }
 316   for (auto& t : threads) {
 317     t.join();
 318   }
 319   string str = c.toString();
 320   for (auto key : keys) {
 321     int val = key * mult;
 322     EXPECT_EQ(val, c.getValue(key));
 323     EXPECT_NE(string::npos, str.find(folly::to<string>("[",key,":",val,"]")));
 324   }
 325 }
 326
 327 class Integer {
 328
 329  public:
 330   explicit Integer(KeyT v = 0) : v_(v) {}
 331
 332   Integer& operator=(const Integer& a) {
 333     static bool throwException_ = false;
 334     throwException_ = !throwException_;
 335     if (throwException_) {
 336       throw 1;
 337     }
 338     v_ = a.v_;
 339     return *this;
 340   }
 341
 342   bool operator==(const Integer& a) const { return v_ == a.v_; }
 343
 344  private:
 345   KeyT v_;
 346 };
 347
 348 TEST(Ahm, map_exception_safety) {
 349   typedef AtomicHashMap<KeyT,Integer> MyMapT;
 350
 351   int numEntries = 10000;
 352   float sizeFactor = 0.46f;
 353   std::unique_ptr<MyMapT> m(new MyMapT(int(numEntries * sizeFactor)));
 354
 355   bool success = true;
 356   int count = 0;
 357   for (int i = 0; i < numEntries; i++) {
 358     try {
 359       m->insert(i, Integer(genVal(i)));
 360       success &= (m->find(i)->second == Integer(genVal(i)));
 361       ++count;
 362     } catch (...) {
 363       success &= !m->count(i);
 364     }
 365   }
 366   EXPECT_EQ(count, m->size());
 367   EXPECT_TRUE(success);
 368 }
 369
 370 TEST(Ahm, basicErase) {
 371   size_t numEntries = 3000;
 372
 373   std::unique_ptr<AHMapT> s(new AHMapT(numEntries, config));
 374   // Iterate filling up the map and deleting all keys a few times
 375   // to test more than one subMap.
 376   for (int iterations = 0; iterations < 4; ++iterations) {
 377     // Testing insertion of keys
 378     bool success = true;
 379     for (size_t i = 0; i < numEntries; ++i) {
 380       success &= !(s->count(i));
 381       auto ret = s->insert(RecordT(i, i));
 382       success &= s->count(i);
 383       success &= ret.second;
 384     }
 385     EXPECT_TRUE(success);
 386     EXPECT_EQ(s->size(), numEntries);
 387
 388     // Delete every key in the map and verify that the key is gone and the the
 389     // size is correct.
 390     success = true;
 391     for (size_t i = 0; i < numEntries; ++i) {
 392       success &= s->erase(i);
 393       success &= (s->size() == numEntries - 1 - i);
 394       success &= !(s->count(i));
 395       success &= !(s->erase(i));
 396     }
 397     EXPECT_TRUE(success);
 398   }
 399   VLOG(1) << "Final number of subMaps = " << s->numSubMaps();
 400 }
 401
 402 namespace {
 403
 404 inline KeyT randomizeKey(int key) {
 405   // We deterministically randomize the key to more accurately simulate
 406   // real-world usage, and to avoid pathalogical performance patterns (e.g.
 407   // those related to std::hash<int64_t>()(1) == 1).
 408   //
 409   // Use a hash function we don't normally use for ints to avoid interactions.
 410   return folly::hash::jenkins_rev_mix32(key);
 411 }
 412
 413 int numOpsPerThread = 0;
 414
 415 void* insertThread(void* jj) {
 416   int64_t j = (int64_t) jj;
 417   for (int i = 0; i < numOpsPerThread; ++i) {
 418     KeyT key = randomizeKey(i + j * numOpsPerThread);
 419     globalAHM->insert(key, genVal(key));
 420   }
 421   return nullptr;
 422 }
 423
 424 void* qpInsertThread(void* jj) {
 425   int64_t j = (int64_t) jj;
 426   for (int i = 0; i < numOpsPerThread; ++i) {
 427     KeyT key = randomizeKey(i + j * numOpsPerThread);
 428     globalQPAHM->insert(key, genVal(key));
 429   }
 430   return nullptr;
 431 }
 432
 433 void* insertThreadArr(void* jj) {
 434   int64_t j = (int64_t) jj;
 435   for (int i = 0; i < numOpsPerThread; ++i) {
 436     KeyT key = randomizeKey(i + j * numOpsPerThread);
 437     globalAHA->insert(std::make_pair(key, genVal(key)));
 438   }
 439   return nullptr;
 440 }
 441
 442 std::atomic<bool> runThreadsCreatedAllThreads;
 443 void runThreads(void *(*mainFunc)(void*), int numThreads, void **statuses) {
 444   folly::BenchmarkSuspender susp;
 445   runThreadsCreatedAllThreads.store(false);
 446   vector<std::thread> threads;
 447   for (int64_t j = 0; j < numThreads; j++) {
 448     threads.emplace_back([statuses, mainFunc, j]() {
 449       auto ret = mainFunc((void*)j);
 450       if (statuses != nullptr) {
 451         statuses[j] = ret;
 452       }
 453     });
 454   }
 455   susp.dismiss();
 456
 457   runThreadsCreatedAllThreads.store(true);
 458   for (size_t i = 0; i < threads.size(); ++i) {
 459     threads[i].join();
 460   }
 461 }
 462
 463 void runThreads(void *(*mainFunc)(void*)) {
 464   runThreads(mainFunc, FLAGS_numThreads, nullptr);
 465 }
 466
 467 }
 468
 469 TEST(Ahm, collision_test) {
 470   const int numInserts = 1000000 / 4;
 471
 472   // Doing the same number on each thread so we collide.
 473   numOpsPerThread = numInserts;
 474
 475   float sizeFactor = 0.46f;
 476   int entrySize = sizeof(KeyT) + sizeof(ValueT);
 477   VLOG(1) << "Testing " << numInserts << " unique " << entrySize <<
 478     " Byte entries replicated in " << FLAGS_numThreads <<
 479     " threads with " << FLAGS_maxLoadFactor * 100.0 << "% max load factor.";
 480
 481   globalAHM.reset(new AHMapT(int(numInserts * sizeFactor), config));
 482
 483   size_t sizeInit = globalAHM->capacity();
 484   VLOG(1) << "  Initial capacity: " << sizeInit;
 485
 486   double start = nowInUsec();
 487   runThreads([](void*) -> void* { // collisionInsertThread
 488     for (int i = 0; i < numOpsPerThread; ++i) {
 489       KeyT key = randomizeKey(i);
 490       globalAHM->insert(key, genVal(key));
 491     }
 492     return nullptr;
 493   });
 494   double elapsed = nowInUsec() - start;
 495
 496   size_t finalCap = globalAHM->capacity();
 497   size_t sizeAHM = globalAHM->size();
 498   VLOG(1) << elapsed/sizeAHM << " usec per " << FLAGS_numThreads <<
 499     " duplicate inserts (atomic).";
 500   VLOG(1) << "  Final capacity: " << finalCap << " in " <<
 501     globalAHM->numSubMaps() << " sub maps (" <<
 502     sizeAHM * 100 / finalCap << "% load factor, " <<
 503     (finalCap - sizeInit) * 100 / sizeInit << "% growth).";
 504
 505   // check correctness
 506   EXPECT_EQ(sizeAHM, numInserts);
 507   bool success = true;
 508   for (int i = 0; i < numInserts; ++i) {
 509     KeyT key = randomizeKey(i);
 510     success &= (globalAHM->find(key)->second == genVal(key));
 511   }
 512   EXPECT_TRUE(success);
 513
 514   // check colliding finds
 515   start = nowInUsec();
 516   runThreads([](void*) -> void* { // collisionFindThread
 517     KeyT key(0);
 518     for (int i = 0; i < numOpsPerThread; ++i) {
 519       globalAHM->find(key);
 520     }
 521     return nullptr;
 522   });
 523
 524   elapsed = nowInUsec() - start;
 525
 526   VLOG(1) << elapsed/sizeAHM << " usec per " << FLAGS_numThreads <<
 527     " duplicate finds (atomic).";
 528 }
 529
 530 namespace {
 531
 532 const int kInsertPerThread = 100000;
 533 int raceFinalSizeEstimate;
 534
 535 void* raceIterateThread(void*) {
 536   int count = 0;
 537
 538   AHMapT::iterator it = globalAHM->begin();
 539   AHMapT::iterator end = globalAHM->end();
 540   for (; it != end; ++it) {
 541     ++count;
 542     if (count > raceFinalSizeEstimate) {
 543       EXPECT_FALSE("Infinite loop in iterator.");
 544       return nullptr;
 545     }
 546   }
 547   return nullptr;
 548 }
 549
 550 void* raceInsertRandomThread(void*) {
 551   for (int i = 0; i < kInsertPerThread; ++i) {
 552     KeyT key = rand();
 553     globalAHM->insert(key, genVal(key));
 554   }
 555   return nullptr;
 556 }
 557
 558 }
 559
 560 // Test for race conditions when inserting and iterating at the same time and
 561 // creating multiple submaps.
 562 TEST(Ahm, race_insert_iterate_thread_test) {
 563   const int kInsertThreads = 20;
 564   const int kIterateThreads = 20;
 565   raceFinalSizeEstimate = kInsertThreads * kInsertPerThread;
 566
 567   VLOG(1) << "Testing iteration and insertion with " << kInsertThreads
 568     << " threads inserting and " << kIterateThreads << " threads iterating.";
 569
 570   globalAHM.reset(new AHMapT(raceFinalSizeEstimate / 9, config));
 571
 572   vector<pthread_t> threadIds;
 573   for (int j = 0; j < kInsertThreads + kIterateThreads; j++) {
 574     pthread_t tid;
 575     void *(*thread)(void*) =
 576       (j < kInsertThreads ? raceInsertRandomThread : raceIterateThread);
 577     if (pthread_create(&tid, nullptr, thread, nullptr) != 0) {
 578       LOG(ERROR) << "Could not start thread";
 579     } else {
 580       threadIds.push_back(tid);
 581     }
 582   }
 583   for (size_t i = 0; i < threadIds.size(); ++i) {
 584     pthread_join(threadIds[i], nullptr);
 585   }
 586   VLOG(1) << "Ended up with " << globalAHM->numSubMaps() << " submaps";
 587   VLOG(1) << "Final size of map " << globalAHM->size();
 588 }
 589
 590 namespace {
 591
 592 const int kTestEraseInsertions = 200000;
 593 std::atomic<int32_t> insertedLevel;
 594
 595 void* testEraseInsertThread(void*) {
 596   for (int i = 0; i < kTestEraseInsertions; ++i) {
 597     KeyT key = randomizeKey(i);
 598     globalAHM->insert(key, genVal(key));
 599     insertedLevel.store(i, std::memory_order_release);
 600   }
 601   insertedLevel.store(kTestEraseInsertions, std::memory_order_release);
 602   return nullptr;
 603 }
 604
 605 void* testEraseEraseThread(void*) {
 606   for (int i = 0; i < kTestEraseInsertions; ++i) {
 607     /*
 608      * Make sure that we don't get ahead of the insert thread, because
 609      * part of the condition for this unit test succeeding is that the
 610      * map ends up empty.
 611      *
 612      * Note, there is a subtle case here when a new submap is
 613      * allocated: the erasing thread might get 0 from count(key)
 614      * because it hasn't seen numSubMaps_ update yet.  To avoid this
 615      * race causing problems for the test (it's ok for real usage), we
 616      * lag behind the inserter by more than just element.
 617      */
 618     const int lag = 10;
 619     int currentLevel;
 620     do {
 621       currentLevel = insertedLevel.load(std::memory_order_acquire);
 622       if (currentLevel == kTestEraseInsertions) currentLevel += lag + 1;
 623     } while (currentLevel - lag < i);
 624
 625     KeyT key = randomizeKey(i);
 626     while (globalAHM->count(key)) {
 627       if (globalAHM->erase(key)) {
 628         break;
 629       }
 630     }
 631   }
 632   return nullptr;
 633 }
 634
 635 }
 636
 637 // Here we have a single thread inserting some values, and several threads
 638 // racing to delete the values in the order they were inserted.
 639 TEST(Ahm, thread_erase_insert_race) {
 640   const int kInsertThreads = 1;
 641   const int kEraseThreads = 10;
 642
 643   VLOG(1) << "Testing insertion and erase with " << kInsertThreads
 644     << " thread inserting and " << kEraseThreads << " threads erasing.";
 645
 646   globalAHM.reset(new AHMapT(kTestEraseInsertions / 4, config));
 647
 648   vector<pthread_t> threadIds;
 649   for (int64_t j = 0; j < kInsertThreads + kEraseThreads; j++) {
 650     pthread_t tid;
 651     void *(*thread)(void*) =
 652       (j < kInsertThreads ? testEraseInsertThread : testEraseEraseThread);
 653     if (pthread_create(&tid, nullptr, thread, (void*) j) != 0) {
 654       LOG(ERROR) << "Could not start thread";
 655     } else {
 656       threadIds.push_back(tid);
 657     }
 658   }
 659   for (size_t i = 0; i < threadIds.size(); i++) {
 660     pthread_join(threadIds[i], nullptr);
 661   }
 662
 663   EXPECT_TRUE(globalAHM->empty());
 664   EXPECT_EQ(globalAHM->size(), 0);
 665
 666   VLOG(1) << "Ended up with " << globalAHM->numSubMaps() << " submaps";
 667 }
 668
 669 // Repro for T#483734: Duplicate AHM inserts due to incorrect AHA return value.
 670 typedef AtomicHashArray<int32_t, int32_t> AHA;
 671 AHA::Config configRace;
 672 auto atomicHashArrayInsertRaceArray = AHA::create(2, configRace);
 673 void* atomicHashArrayInsertRaceThread(void* /* j */) {
 674   AHA* arr = atomicHashArrayInsertRaceArray.get();
 675   uintptr_t numInserted = 0;
 676   while (!runThreadsCreatedAllThreads.load());
 677   for (int i = 0; i < 2; i++) {
 678     if (arr->insert(RecordT(randomizeKey(i), 0)).first != arr->end()) {
 679       numInserted++;
 680     }
 681   }
 682   return (void*)numInserted;
 683 }
 684 TEST(Ahm, atomic_hash_array_insert_race) {
 685   AHA* arr = atomicHashArrayInsertRaceArray.get();
 686   int numIterations = 5000;
 687   constexpr int numThreads = 4;
 688   void* statuses[numThreads];
 689   for (int i = 0; i < numIterations; i++) {
 690     arr->clear();
 691     runThreads(atomicHashArrayInsertRaceThread, numThreads, statuses);
 692     EXPECT_GE(arr->size(), 1);
 693     for (int j = 0; j < numThreads; j++) {
 694       EXPECT_EQ(arr->size(), uintptr_t(statuses[j]));
 695     }
 696   }
 697 }
 698
 699 // Repro for T#5841499. Race between erase() and find() on the same key.
 700 TEST(Ahm, erase_find_race) {
 701   const uint64_t limit = 10000;
 702   AtomicHashMap<uint64_t, uint64_t> map(limit + 10);
 703   std::atomic<uint64_t> key {1};
 704
 705   // Invariant: all values are equal to their keys.
 706   // At any moment there is one or two consecutive keys in the map.
 707
 708   std::thread write_thread([&]() {
 709     while (true) {
 710       uint64_t k = ++key;
 711       if (k > limit) {
 712         break;
 713       }
 714       map.insert(k + 1, k + 1);
 715       map.erase(k);
 716     }
 717   });
 718
 719   std::thread read_thread([&]() {
 720     while (true) {
 721       uint64_t k = key.load();
 722       if (k > limit) {
 723         break;
 724       }
 725
 726       auto it = map.find(k);
 727       if (it != map.end()) {
 728         ASSERT_EQ(k, it->second);
 729       }
 730     }
 731   });
 732
 733   read_thread.join();
 734   write_thread.join();
 735 }
 736
 737 // Erase right after insert race bug repro (t9130653)
 738 TEST(Ahm, erase_after_insert_race) {
 739   const uint64_t limit = 10000;
 740   const size_t num_threads = 100;
 741   const size_t num_iters = 500;
 742   AtomicHashMap<uint64_t, uint64_t> map(limit + 10);
 743
 744   std::atomic<bool> go{false};
 745   std::vector<std::thread> ts;
 746   for (size_t i = 0; i < num_threads; ++i) {
 747     ts.emplace_back([&]() {
 748         while (!go) {
 749           continue;
 750         }
 751         for (size_t n = 0; n < num_iters; ++n) {
 752           map.erase(1);
 753           map.insert(1, 1);
 754         }
 755       });
 756   }
 757
 758   go = true;
 759
 760   for (auto& t : ts) {
 761     t.join();
 762   }
 763 }
 764
 765 // Repro for a bug when iterator didn't skip empty submaps.
 766 TEST(Ahm, iterator_skips_empty_submaps) {
 767   AtomicHashMap<uint64_t, uint64_t>::Config config;
 768   config.growthFactor = 1;
 769
 770   AtomicHashMap<uint64_t, uint64_t> map(1, config);
 771
 772   map.insert(1, 1);
 773   map.insert(2, 2);
 774   map.insert(3, 3);
 775
 776   map.erase(2);
 777
 778   auto it = map.find(1);
 779
 780   ASSERT_NE(map.end(), it);
 781   ASSERT_EQ(1, it->first);
 782   ASSERT_EQ(1, it->second);
 783
 784   ++it;
 785
 786   ASSERT_NE(map.end(), it);
 787   ASSERT_EQ(3, it->first);
 788   ASSERT_EQ(3, it->second);
 789
 790   ++it;
 791   ASSERT_EQ(map.end(), it);
 792 }
 793
 794 namespace {
 795
 796 void loadGlobalAha() {
 797   std::cout << "loading global AHA with " << FLAGS_numThreads
 798             << " threads...\n";
 799   uint64_t start = nowInUsec();
 800   globalAHA = AHArrayT::create(maxBMElements, config);
 801   numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
 802   CHECK_EQ(0, FLAGS_numBMElements % FLAGS_numThreads) <<
 803     "kNumThreads must evenly divide kNumInserts.";
 804   runThreads(insertThreadArr);
 805   uint64_t elapsed = nowInUsec() - start;
 806   std::cout << "  took " << elapsed / 1000 << " ms (" <<
 807     (elapsed * 1000 / FLAGS_numBMElements) << " ns/insert).\n";
 808   EXPECT_EQ(globalAHA->size(), FLAGS_numBMElements);
 809 }
 810
 811 void loadGlobalAhm() {
 812   std::cout << "loading global AHM with " << FLAGS_numThreads
 813             << " threads...\n";
 814   uint64_t start = nowInUsec();
 815   globalAHM.reset(new AHMapT(maxBMElements, config));
 816   numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
 817   runThreads(insertThread);
 818   uint64_t elapsed = nowInUsec() - start;
 819   std::cout << "  took " << elapsed / 1000 << " ms (" <<
 820     (elapsed * 1000 / FLAGS_numBMElements) << " ns/insert).\n";
 821   EXPECT_EQ(globalAHM->size(), FLAGS_numBMElements);
 822 }
 823
 824 void loadGlobalQPAhm() {
 825   std::cout << "loading global QPAHM with " << FLAGS_numThreads
 826             << " threads...\n";
 827   uint64_t start = nowInUsec();
 828   globalQPAHM.reset(new QPAHMapT(maxBMElements, qpConfig));
 829   numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
 830   runThreads(qpInsertThread);
 831   uint64_t elapsed = nowInUsec() - start;
 832   std::cout << "  took " << elapsed / 1000 << " ms (" <<
 833     (elapsed * 1000 / FLAGS_numBMElements) << " ns/insert).\n";
 834   EXPECT_EQ(globalQPAHM->size(), FLAGS_numBMElements);
 835 }
 836
 837 }
 838
 839 BENCHMARK(st_aha_find, iters) {
 840   CHECK_LE(iters, FLAGS_numBMElements);
 841   for (size_t i = 0; i < iters; i++) {
 842     KeyT key = randomizeKey(i);
 843     folly::doNotOptimizeAway(globalAHA->find(key)->second);
 844   }
 845 }
 846
 847 BENCHMARK(st_ahm_find, iters) {
 848   CHECK_LE(iters, FLAGS_numBMElements);
 849   for (size_t i = 0; i < iters; i++) {
 850     KeyT key = randomizeKey(i);
 851     folly::doNotOptimizeAway(globalAHM->find(key)->second);
 852   }
 853 }
 854
 855 BENCHMARK(st_qpahm_find, iters) {
 856   CHECK_LE(iters, FLAGS_numBMElements);
 857   for (size_t i = 0; i < iters; i++) {
 858     KeyT key = randomizeKey(i);
 859     folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
 860   }
 861 }
 862
 863 BENCHMARK_DRAW_LINE()
 864
 865 BENCHMARK(mt_ahm_miss, iters) {
 866   CHECK_LE(iters, FLAGS_numBMElements);
 867   numOpsPerThread = iters / FLAGS_numThreads;
 868   runThreads([](void* jj) -> void* {
 869     int64_t j = (int64_t) jj;
 870     while (!runThreadsCreatedAllThreads.load());
 871     for (int i = 0; i < numOpsPerThread; ++i) {
 872       KeyT key = i + j * numOpsPerThread * 100;
 873       folly::doNotOptimizeAway(globalAHM->find(key) == globalAHM->end());
 874     }
 875     return nullptr;
 876   });
 877 }
 878
 879 BENCHMARK(mt_qpahm_miss, iters) {
 880   CHECK_LE(iters, FLAGS_numBMElements);
 881   numOpsPerThread = iters / FLAGS_numThreads;
 882   runThreads([](void* jj) -> void* {
 883     int64_t j = (int64_t) jj;
 884     while (!runThreadsCreatedAllThreads.load());
 885     for (int i = 0; i < numOpsPerThread; ++i) {
 886       KeyT key = i + j * numOpsPerThread * 100;
 887       folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
 888     }
 889     return nullptr;
 890   });
 891 }
 892
 893 BENCHMARK(st_ahm_miss, iters) {
 894   CHECK_LE(iters, FLAGS_numBMElements);
 895   for (size_t i = 0; i < iters; i++) {
 896     KeyT key = randomizeKey(i + iters * 100);
 897     folly::doNotOptimizeAway(globalAHM->find(key) == globalAHM->end());
 898   }
 899 }
 900
 901 BENCHMARK(st_qpahm_miss, iters) {
 902   CHECK_LE(iters, FLAGS_numBMElements);
 903   for (size_t i = 0; i < iters; i++) {
 904     KeyT key = randomizeKey(i + iters * 100);
 905     folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
 906   }
 907 }
 908
 909 BENCHMARK(mt_ahm_find_insert_mix, iters) {
 910   CHECK_LE(iters, FLAGS_numBMElements);
 911   numOpsPerThread = iters / FLAGS_numThreads;
 912   runThreads([](void* jj) -> void* {
 913     int64_t j = (int64_t) jj;
 914     while (!runThreadsCreatedAllThreads.load());
 915     for (int i = 0; i < numOpsPerThread; ++i) {
 916       if (i % 128) {  // ~1% insert mix
 917         KeyT key = randomizeKey(i + j * numOpsPerThread);
 918         folly::doNotOptimizeAway(globalAHM->find(key)->second);
 919       } else {
 920         KeyT key = randomizeKey(i + j * numOpsPerThread * 100);
 921         globalAHM->insert(key, genVal(key));
 922       }
 923     }
 924     return nullptr;
 925   });
 926 }
 927
 928
 929 BENCHMARK(mt_qpahm_find_insert_mix, iters) {
 930   CHECK_LE(iters, FLAGS_numBMElements);
 931   numOpsPerThread = iters / FLAGS_numThreads;
 932   runThreads([](void* jj) -> void* {
 933     int64_t j = (int64_t) jj;
 934     while (!runThreadsCreatedAllThreads.load());
 935     for (int i = 0; i < numOpsPerThread; ++i) {
 936       if (i % 128) {  // ~1% insert mix
 937         KeyT key = randomizeKey(i + j * numOpsPerThread);
 938         folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
 939       } else {
 940         KeyT key = randomizeKey(i + j * numOpsPerThread * 100);
 941         globalQPAHM->insert(key, genVal(key));
 942       }
 943     }
 944     return nullptr;
 945   });
 946 }
 947
 948 BENCHMARK(mt_aha_find, iters) {
 949   CHECK_LE(iters, FLAGS_numBMElements);
 950   numOpsPerThread = iters / FLAGS_numThreads;
 951   runThreads([](void* jj) -> void* {
 952       int64_t j = (int64_t) jj;
 953       while (!runThreadsCreatedAllThreads.load());
 954       for (int i = 0; i < numOpsPerThread; ++i) {
 955         KeyT key = randomizeKey(i + j * numOpsPerThread);
 956         folly::doNotOptimizeAway(globalAHA->find(key)->second);
 957       }
 958       return nullptr;
 959     });
 960 }
 961
 962 BENCHMARK(mt_ahm_find, iters) {
 963   CHECK_LE(iters, FLAGS_numBMElements);
 964   numOpsPerThread = iters / FLAGS_numThreads;
 965   runThreads([](void* jj) -> void* {
 966     int64_t j = (int64_t) jj;
 967     while (!runThreadsCreatedAllThreads.load());
 968     for (int i = 0; i < numOpsPerThread; ++i) {
 969       KeyT key = randomizeKey(i + j * numOpsPerThread);
 970       folly::doNotOptimizeAway(globalAHM->find(key)->second);
 971     }
 972     return nullptr;
 973   });
 974 }
 975
 976 BENCHMARK(mt_qpahm_find, iters) {
 977   CHECK_LE(iters, FLAGS_numBMElements);
 978   numOpsPerThread = iters / FLAGS_numThreads;
 979   runThreads([](void* jj) -> void* {
 980     int64_t j = (int64_t) jj;
 981     while (!runThreadsCreatedAllThreads.load());
 982     for (int i = 0; i < numOpsPerThread; ++i) {
 983       KeyT key = randomizeKey(i + j * numOpsPerThread);
 984       folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
 985     }
 986     return nullptr;
 987   });
 988 }
 989
 990 KeyT k;
 991 BENCHMARK(st_baseline_modulus_and_random, iters) {
 992   for (size_t i = 0; i < iters; ++i) {
 993     k = randomizeKey(i) % iters;
 994   }
 995 }
 996
 997 // insertions go last because they reset the map
 998
 999 BENCHMARK(mt_ahm_insert, iters) {
1000   BENCHMARK_SUSPEND {
1001     globalAHM.reset(new AHMapT(int(iters * LF), config));
1002     numOpsPerThread = iters / FLAGS_numThreads;
1003   }
1004   runThreads(insertThread);
1005 }
1006
1007 BENCHMARK(mt_qpahm_insert, iters) {
1008   BENCHMARK_SUSPEND {
1009     globalQPAHM.reset(new QPAHMapT(int(iters * LF), qpConfig));
1010     numOpsPerThread = iters / FLAGS_numThreads;
1011   }
1012   runThreads(qpInsertThread);
1013 }
1014
1015 BENCHMARK(st_ahm_insert, iters) {
1016   folly::BenchmarkSuspender susp;
1017   std::unique_ptr<AHMapT> ahm(new AHMapT(int(iters * LF), config));
1018   susp.dismiss();
1019
1020   for (size_t i = 0; i < iters; i++) {
1021     KeyT key = randomizeKey(i);
1022     ahm->insert(key, genVal(key));
1023   }
1024 }
1025
1026 BENCHMARK(st_qpahm_insert, iters) {
1027   folly::BenchmarkSuspender susp;
1028   std::unique_ptr<QPAHMapT> ahm(new QPAHMapT(int(iters * LF), qpConfig));
1029   susp.dismiss();
1030
1031   for (size_t i = 0; i < iters; i++) {
1032     KeyT key = randomizeKey(i);
1033     ahm->insert(key, genVal(key));
1034   }
1035 }
1036
1037 void benchmarkSetup() {
1038   config.maxLoadFactor = FLAGS_maxLoadFactor;
1039   qpConfig.maxLoadFactor = FLAGS_maxLoadFactor;
1040   configRace.maxLoadFactor = 0.5;
1041   int numCores = sysconf(_SC_NPROCESSORS_ONLN);
1042   loadGlobalAha();
1043   loadGlobalAhm();
1044   loadGlobalQPAhm();
1045   string numIters = folly::to<string>(
1046     std::min(1000000, int(FLAGS_numBMElements)));
1047
1048   gflags::SetCommandLineOptionWithMode(
1049     "bm_max_iters", numIters.c_str(), gflags::SET_FLAG_IF_DEFAULT
1050   );
1051   gflags::SetCommandLineOptionWithMode(
1052     "bm_min_iters", numIters.c_str(), gflags::SET_FLAG_IF_DEFAULT
1053   );
1054   string numCoresStr = folly::to<string>(numCores);
1055   gflags::SetCommandLineOptionWithMode(
1056     "numThreads", numCoresStr.c_str(), gflags::SET_FLAG_IF_DEFAULT
1057   );
1058
1059   std::cout << "\nRunning AHM benchmarks on machine with " << numCores
1060     << " logical cores.\n"
1061        "  num elements per map: " << FLAGS_numBMElements << "\n"
1062     << "  num threads for mt tests: " << FLAGS_numThreads << "\n"
1063     << "  AHM load factor: " << FLAGS_targetLoadFactor << "\n\n";
1064 }
1065
1066 int main(int argc, char** argv) {
1067   testing::InitGoogleTest(&argc, argv);
1068   gflags::ParseCommandLineFlags(&argc, &argv, true);
1069   auto ret = RUN_ALL_TESTS();
1070   if (!ret && FLAGS_benchmark) {
1071     benchmarkSetup();
1072     folly::runBenchmarks();
1073   }
1074   return ret;
1075 }
1076
1077 /*
1078 loading global AHA with 8 threads...
1079   took 487 ms (40 ns/insert).
1080 loading global AHM with 8 threads...
1081   took 478 ms (39 ns/insert).
1082 loading global QPAHM with 8 threads...
1083   took 478 ms (39 ns/insert).
1084
1085 Running AHM benchmarks on machine with 24 logical cores.
1086   num elements per map: 12000000
1087   num threads for mt tests: 24
1088   AHM load factor: 0.75
1089
1090 ============================================================================
1091 folly/test/AtomicHashMapTest.cpp                relative  time/iter  iters/s
1092 ============================================================================
1093 st_aha_find                                                 92.63ns   10.80M
1094 st_ahm_find                                                107.78ns    9.28M
1095 st_qpahm_find                                               90.69ns   11.03M
1096 ----------------------------------------------------------------------------
1097 mt_ahm_miss                                                  2.09ns  477.36M
1098 mt_qpahm_miss                                                1.37ns  728.82M
1099 st_ahm_miss                                                241.07ns    4.15M
1100 st_qpahm_miss                                              223.17ns    4.48M
1101 mt_ahm_find_insert_mix                                       8.05ns  124.24M
1102 mt_qpahm_find_insert_mix                                     9.10ns  109.85M
1103 mt_aha_find                                                  6.82ns  146.68M
1104 mt_ahm_find                                                  7.95ns  125.77M
1105 mt_qpahm_find                                                6.81ns  146.83M
1106 st_baseline_modulus_and_random                               6.02ns  166.03M
1107 mt_ahm_insert                                               14.29ns   69.97M
1108 mt_qpahm_insert                                             11.68ns   85.61M
1109 st_ahm_insert                                              125.39ns    7.98M
1110 st_qpahm_insert                                            128.76ns    7.77M
1111 ============================================================================
1112 */