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