/*
- * Copyright 2015 Facebook, Inc.
+ * Copyright 2016 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include <glog/logging.h>
#include <gtest/gtest.h>
-#include <sys/time.h>
#include <thread>
#include <atomic>
#include <memory>
#include <folly/Benchmark.h>
#include <folly/Conv.h>
+#include <folly/portability/SysTime.h>
using std::vector;
using std::string;
using folly::AtomicHashMap;
using folly::AtomicHashArray;
+using folly::StringPiece;
// Tunables:
DEFINE_double(targetLoadFactor, 0.75, "Target memory utilization fraction.");
typedef AtomicHashMap<KeyT,ValueT> AHMapT;
typedef AHMapT::value_type RecordT;
typedef AtomicHashArray<KeyT,ValueT> AHArrayT;
-
AHArrayT::Config config;
+typedef folly::QuadraticProbingAtomicHashMap<KeyT,ValueT> QPAHMapT;
+QPAHMapT::Config qpConfig;
static AHArrayT::SmartPtr globalAHA(nullptr);
static std::unique_ptr<AHMapT> globalAHM;
+static std::unique_ptr<QPAHMapT> globalQPAHM;
// Generate a deterministic value based on an input key
static int genVal(int key) {
return key / 3;
}
+static bool legalKey(const char* a);
+
+struct EqTraits {
+ bool operator()(const char* a, const char* b) {
+ return legalKey(a) && (strcmp(a, b) == 0);
+ }
+ bool operator()(const char* a, const char& b) {
+ return legalKey(a) && (a[0] != '\0') && (a[0] == b);
+ }
+ bool operator()(const char* a, const StringPiece b) {
+ return legalKey(a) &&
+ (strlen(a) == b.size()) && (strcmp(a, b.begin()) == 0);
+ }
+};
+
+struct HashTraits {
+ size_t operator()(const char* a) {
+ size_t result = 0;
+ while (a[0] != 0) result += static_cast<size_t>(*(a++));
+ return result;
+ }
+ size_t operator()(const char& a) {
+ return static_cast<size_t>(a);
+ }
+ size_t operator()(const StringPiece a) {
+ size_t result = 0;
+ for (const auto& ch : a) result += static_cast<size_t>(ch);
+ return result;
+ }
+};
+
+typedef AtomicHashMap<const char*, int64_t, HashTraits, EqTraits> AHMCstrInt;
+AHMCstrInt::Config cstrIntCfg;
+
+static bool legalKey(const char* a) {
+ return a != cstrIntCfg.emptyKey &&
+ a != cstrIntCfg.lockedKey &&
+ a != cstrIntCfg.erasedKey;
+}
+
+TEST(Ahm, BasicLookup) {
+ AHMCstrInt myMap(1024, cstrIntCfg);
+ EXPECT_TRUE(myMap.begin() == myMap.end());
+ myMap.insert(std::make_pair("f", 42));
+ EXPECT_EQ(42, myMap.find("f")->second);
+ {
+ // Look up a single char, successfully.
+ auto it = myMap.find<char>('f');
+ EXPECT_EQ(42, it->second);
+ }
+ {
+ // Look up a single char, unsuccessfully.
+ auto it = myMap.find<char>('g');
+ EXPECT_TRUE(it == myMap.end());
+ }
+ {
+ // Look up a string piece, successfully.
+ const StringPiece piece("f");
+ auto it = myMap.find(piece);
+ EXPECT_EQ(42, it->second);
+ }
+}
+
TEST(Ahm, grow) {
VLOG(1) << "Overhead: " << sizeof(AHArrayT) << " (array) " <<
sizeof(AHMapT) + sizeof(AHArrayT) << " (map/set) Bytes.";
return nullptr;
}
+void* qpInsertThread(void* jj) {
+ int64_t j = (int64_t) jj;
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ KeyT key = randomizeKey(i + j * numOpsPerThread);
+ globalQPAHM->insert(key, genVal(key));
+ }
+ return nullptr;
+}
+
void* insertThreadArr(void* jj) {
int64_t j = (int64_t) jj;
for (int i = 0; i < numOpsPerThread; ++i) {
typedef AtomicHashArray<int32_t, int32_t> AHA;
AHA::Config configRace;
auto atomicHashArrayInsertRaceArray = AHA::create(2, configRace);
-void* atomicHashArrayInsertRaceThread(void* j) {
+void* atomicHashArrayInsertRaceThread(void* /* j */) {
AHA* arr = atomicHashArrayInsertRaceArray.get();
uintptr_t numInserted = 0;
while (!runThreadsCreatedAllThreads.load());
write_thread.join();
}
+// Erase right after insert race bug repro (t9130653)
+TEST(Ahm, erase_after_insert_race) {
+ const uint64_t limit = 10000;
+ const size_t num_threads = 100;
+ const size_t num_iters = 500;
+ AtomicHashMap<uint64_t, uint64_t> map(limit + 10);
+
+ std::atomic<bool> go{false};
+ std::vector<std::thread> ts;
+ for (size_t i = 0; i < num_threads; ++i) {
+ ts.emplace_back([&]() {
+ while (!go) {
+ continue;
+ }
+ for (size_t n = 0; n < num_iters; ++n) {
+ map.erase(1);
+ map.insert(1, 1);
+ }
+ });
+ }
+
+ go = true;
+
+ for (auto& t : ts) {
+ t.join();
+ }
+}
+
// Repro for a bug when iterator didn't skip empty submaps.
TEST(Ahm, iterator_skips_empty_submaps) {
AtomicHashMap<uint64_t, uint64_t>::Config config;
EXPECT_EQ(globalAHM->size(), FLAGS_numBMElements);
}
+void loadGlobalQPAhm() {
+ std::cout << "loading global QPAHM with " << FLAGS_numThreads
+ << " threads...\n";
+ uint64_t start = nowInUsec();
+ globalQPAHM.reset(new QPAHMapT(maxBMElements, qpConfig));
+ numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
+ runThreads(qpInsertThread);
+ uint64_t elapsed = nowInUsec() - start;
+ std::cout << " took " << elapsed / 1000 << " ms (" <<
+ (elapsed * 1000 / FLAGS_numBMElements) << " ns/insert).\n";
+ EXPECT_EQ(globalQPAHM->size(), FLAGS_numBMElements);
+}
+
}
BENCHMARK(st_aha_find, iters) {
}
}
+BENCHMARK(st_qpahm_find, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ for (size_t i = 0; i < iters; i++) {
+ KeyT key = randomizeKey(i);
+ folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
+ }
+}
+
BENCHMARK_DRAW_LINE()
BENCHMARK(mt_ahm_miss, iters) {
});
}
+BENCHMARK(mt_qpahm_miss, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ numOpsPerThread = iters / FLAGS_numThreads;
+ runThreads([](void* jj) -> void* {
+ int64_t j = (int64_t) jj;
+ while (!runThreadsCreatedAllThreads.load());
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ KeyT key = i + j * numOpsPerThread * 100;
+ folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
+ }
+ return nullptr;
+ });
+}
+
BENCHMARK(st_ahm_miss, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
for (size_t i = 0; i < iters; i++) {
}
}
+BENCHMARK(st_qpahm_miss, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ for (size_t i = 0; i < iters; i++) {
+ KeyT key = randomizeKey(i + iters * 100);
+ folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
+ }
+}
+
BENCHMARK(mt_ahm_find_insert_mix, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
numOpsPerThread = iters / FLAGS_numThreads;
});
}
+
+BENCHMARK(mt_qpahm_find_insert_mix, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ numOpsPerThread = iters / FLAGS_numThreads;
+ runThreads([](void* jj) -> void* {
+ int64_t j = (int64_t) jj;
+ while (!runThreadsCreatedAllThreads.load());
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ if (i % 128) { // ~1% insert mix
+ KeyT key = randomizeKey(i + j * numOpsPerThread);
+ folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
+ } else {
+ KeyT key = randomizeKey(i + j * numOpsPerThread * 100);
+ globalQPAHM->insert(key, genVal(key));
+ }
+ }
+ return nullptr;
+ });
+}
+
BENCHMARK(mt_aha_find, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
numOpsPerThread = iters / FLAGS_numThreads;
});
}
+BENCHMARK(mt_qpahm_find, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ numOpsPerThread = iters / FLAGS_numThreads;
+ runThreads([](void* jj) -> void* {
+ int64_t j = (int64_t) jj;
+ while (!runThreadsCreatedAllThreads.load());
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ KeyT key = randomizeKey(i + j * numOpsPerThread);
+ folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
+ }
+ return nullptr;
+ });
+}
+
KeyT k;
BENCHMARK(st_baseline_modulus_and_random, iters) {
for (size_t i = 0; i < iters; ++i) {
runThreads(insertThread);
}
+BENCHMARK(mt_qpahm_insert, iters) {
+ BENCHMARK_SUSPEND {
+ globalQPAHM.reset(new QPAHMapT(int(iters * LF), qpConfig));
+ numOpsPerThread = iters / FLAGS_numThreads;
+ }
+ runThreads(qpInsertThread);
+}
+
BENCHMARK(st_ahm_insert, iters) {
folly::BenchmarkSuspender susp;
std::unique_ptr<AHMapT> ahm(new AHMapT(int(iters * LF), config));
}
}
+BENCHMARK(st_qpahm_insert, iters) {
+ folly::BenchmarkSuspender susp;
+ std::unique_ptr<QPAHMapT> ahm(new QPAHMapT(int(iters * LF), qpConfig));
+ susp.dismiss();
+
+ for (size_t i = 0; i < iters; i++) {
+ KeyT key = randomizeKey(i);
+ ahm->insert(key, genVal(key));
+ }
+}
+
void benchmarkSetup() {
config.maxLoadFactor = FLAGS_maxLoadFactor;
+ qpConfig.maxLoadFactor = FLAGS_maxLoadFactor;
configRace.maxLoadFactor = 0.5;
int numCores = sysconf(_SC_NPROCESSORS_ONLN);
loadGlobalAha();
loadGlobalAhm();
+ loadGlobalQPAhm();
string numIters = folly::to<string>(
std::min(1000000, int(FLAGS_numBMElements)));
}
/*
-Benchmarks run on dual Xeon X5650's @ 2.67GHz w/hyperthreading enabled
- (12 physical cores, 12 MB cache, 72 GB RAM)
+loading global AHA with 8 threads...
+ took 487 ms (40 ns/insert).
+loading global AHM with 8 threads...
+ took 478 ms (39 ns/insert).
+loading global QPAHM with 8 threads...
+ took 478 ms (39 ns/insert).
Running AHM benchmarks on machine with 24 logical cores.
num elements per map: 12000000
num threads for mt tests: 24
AHM load factor: 0.75
-Benchmark Iters Total t t/iter iter/sec
-------------------------------------------------------------------------------
-Comparing benchmarks: BM_mt_aha_find,BM_mt_ahm_find
-* BM_mt_aha_find 1000000 7.767 ms 7.767 ns 122.8 M
- +0.81% BM_mt_ahm_find 1000000 7.83 ms 7.83 ns 121.8 M
-------------------------------------------------------------------------------
-Comparing benchmarks: BM_st_aha_find,BM_st_ahm_find
-* BM_st_aha_find 1000000 57.83 ms 57.83 ns 16.49 M
- +77.9% BM_st_ahm_find 1000000 102.9 ms 102.9 ns 9.27 M
-------------------------------------------------------------------------------
-BM_mt_ahm_miss 1000000 2.937 ms 2.937 ns 324.7 M
-BM_st_ahm_miss 1000000 164.2 ms 164.2 ns 5.807 M
-BM_mt_ahm_find_insert_mix 1000000 8.797 ms 8.797 ns 108.4 M
-BM_mt_ahm_insert 1000000 17.39 ms 17.39 ns 54.83 M
-BM_st_ahm_insert 1000000 106.8 ms 106.8 ns 8.93 M
-BM_st_baseline_modulus_and_rando 1000000 6.223 ms 6.223 ns 153.2 M
+============================================================================
+folly/test/AtomicHashMapTest.cpp relative time/iter iters/s
+============================================================================
+st_aha_find 92.63ns 10.80M
+st_ahm_find 107.78ns 9.28M
+st_qpahm_find 90.69ns 11.03M
+----------------------------------------------------------------------------
+mt_ahm_miss 2.09ns 477.36M
+mt_qpahm_miss 1.37ns 728.82M
+st_ahm_miss 241.07ns 4.15M
+st_qpahm_miss 223.17ns 4.48M
+mt_ahm_find_insert_mix 8.05ns 124.24M
+mt_qpahm_find_insert_mix 9.10ns 109.85M
+mt_aha_find 6.82ns 146.68M
+mt_ahm_find 7.95ns 125.77M
+mt_qpahm_find 6.81ns 146.83M
+st_baseline_modulus_and_random 6.02ns 166.03M
+mt_ahm_insert 14.29ns 69.97M
+mt_qpahm_insert 11.68ns 85.61M
+st_ahm_insert 125.39ns 7.98M
+st_qpahm_insert 128.76ns 7.77M
+============================================================================
*/
projects / folly.git / blobdiff