/*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2017 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 <folly/AtomicHashMap.h>
-#include <glog/logging.h>
-#include <gtest/gtest.h>
-#include <sys/time.h>
-#include <thread>
#include <atomic>
#include <memory>
+#include <thread>
+
+#include <glog/logging.h>
+
#include <folly/Benchmark.h>
#include <folly/Conv.h>
+#include <folly/portability/GTest.h>
+#include <folly/portability/SysTime.h>
using std::vector;
using std::string;
static int64_t nowInUsec() {
timeval tv;
- gettimeofday(&tv, 0);
+ gettimeofday(&tv, nullptr);
return int64_t(tv.tv_sec) * 1000 * 1000 + tv.tv_usec;
}
EXPECT_TRUE(myMap.begin() == myMap.end());
for (int i = 0; i < 50; ++i) {
- myMap.insert(make_pair(i, std::unique_ptr<int>(new int(i))));
+ myMap.insert(make_pair(i, std::make_unique<int>(i)));
}
for (int i = 50; i < 100; ++i) {
- myMap.insert(i, std::unique_ptr<int>(new int (i)));
+ myMap.insert(i, std::make_unique<int>(i));
}
for (int i = 100; i < 150; ++i) {
myMap.emplace(i, new int (i));
struct HashTraits {
size_t operator()(const char* a) {
size_t result = 0;
- while (a[0] != 0) result += static_cast<size_t>(*(a++));
+ while (a[0] != 0) {
+ result += static_cast<size_t>(*(a++));
+ }
return result;
}
size_t operator()(const char& a) {
}
size_t operator()(const StringPiece a) {
size_t result = 0;
- for (const auto& ch : a) result += static_cast<size_t>(ch);
+ for (const auto& ch : a) {
+ result += static_cast<size_t>(ch);
+ }
return result;
}
};
VLOG(1) << "Overhead: " << sizeof(AHArrayT) << " (array) " <<
sizeof(AHMapT) + sizeof(AHArrayT) << " (map/set) Bytes.";
uint64_t numEntries = 10000;
- float sizeFactor = 0.46;
+ float sizeFactor = 0.46f;
std::unique_ptr<AHMapT> m(new AHMapT(int(numEntries * sizeFactor), config));
TEST(Ahm, iterator) {
int numEntries = 10000;
- float sizeFactor = .46;
+ float sizeFactor = .46f;
std::unique_ptr<AHMapT> m(new AHMapT(int(numEntries * sizeFactor), config));
// load map - make sure we succeed and the index is accurate
}
class Counters {
-private:
+ private:
// Note: Unfortunately can't currently put a std::atomic<int64_t> in
// the value in ahm since it doesn't support types that are both non-copy
// and non-move constructible yet.
AtomicHashMap<int64_t,int64_t> ahm;
-public:
+ public:
explicit Counters(size_t numCounters) : ahm(numCounters) {}
void increment(int64_t obj_id) {
typedef AtomicHashMap<KeyT,Integer> MyMapT;
int numEntries = 10000;
- float sizeFactor = 0.46;
+ float sizeFactor = 0.46f;
std::unique_ptr<MyMapT> m(new MyMapT(int(numEntries * sizeFactor)));
bool success = true;
inline KeyT randomizeKey(int key) {
// We deterministically randomize the key to more accurately simulate
// real-world usage, and to avoid pathalogical performance patterns (e.g.
- // those related to __gnu_cxx::hash<int64_t>()(1) == 1).
+ // those related to std::hash<int64_t>()(1) == 1).
//
// Use a hash function we don't normally use for ints to avoid interactions.
return folly::hash::jenkins_rev_mix32(key);
}
std::atomic<bool> runThreadsCreatedAllThreads;
-void runThreads(void *(*thread)(void*), int numThreads, void **statuses) {
+void runThreads(void *(*mainFunc)(void*), int numThreads, void **statuses) {
folly::BenchmarkSuspender susp;
runThreadsCreatedAllThreads.store(false);
- vector<pthread_t> threadIds;
+ vector<std::thread> threads;
for (int64_t j = 0; j < numThreads; j++) {
- pthread_t tid;
- if (pthread_create(&tid, nullptr, thread, (void*) j) != 0) {
- LOG(ERROR) << "Could not start thread";
- } else {
- threadIds.push_back(tid);
- }
+ threads.emplace_back([statuses, mainFunc, j]() {
+ auto ret = mainFunc((void*)j);
+ if (statuses != nullptr) {
+ statuses[j] = ret;
+ }
+ });
}
susp.dismiss();
runThreadsCreatedAllThreads.store(true);
- for (size_t i = 0; i < threadIds.size(); ++i) {
- pthread_join(threadIds[i], statuses == nullptr ? nullptr : &statuses[i]);
+ for (size_t i = 0; i < threads.size(); ++i) {
+ threads[i].join();
}
}
-void runThreads(void *(*thread)(void*)) {
- runThreads(thread, FLAGS_numThreads, nullptr);
+void runThreads(void *(*mainFunc)(void*)) {
+ runThreads(mainFunc, FLAGS_numThreads, nullptr);
}
-}
+} // namespace
TEST(Ahm, collision_test) {
const int numInserts = 1000000 / 4;
// Doing the same number on each thread so we collide.
numOpsPerThread = numInserts;
- float sizeFactor = 0.46;
+ float sizeFactor = 0.46f;
int entrySize = sizeof(KeyT) + sizeof(ValueT);
VLOG(1) << "Testing " << numInserts << " unique " << entrySize <<
" Byte entries replicated in " << FLAGS_numThreads <<
" threads with " << FLAGS_maxLoadFactor * 100.0 << "% max load factor.";
- globalAHM.reset(new AHMapT(int(numInserts * sizeFactor), config));
+ globalAHM = std::make_unique<AHMapT>(int(numInserts * sizeFactor), config);
size_t sizeInit = globalAHM->capacity();
VLOG(1) << " Initial capacity: " << sizeInit;
return nullptr;
}
-}
+} // namespace
// Test for race conditions when inserting and iterating at the same time and
// creating multiple submaps.
VLOG(1) << "Testing iteration and insertion with " << kInsertThreads
<< " threads inserting and " << kIterateThreads << " threads iterating.";
- globalAHM.reset(new AHMapT(raceFinalSizeEstimate / 9, config));
+ globalAHM = std::make_unique<AHMapT>(raceFinalSizeEstimate / 9, config);
vector<pthread_t> threadIds;
for (int j = 0; j < kInsertThreads + kIterateThreads; j++) {
int currentLevel;
do {
currentLevel = insertedLevel.load(std::memory_order_acquire);
- if (currentLevel == kTestEraseInsertions) currentLevel += lag + 1;
+ if (currentLevel == kTestEraseInsertions) {
+ currentLevel += lag + 1;
+ }
} while (currentLevel - lag < i);
KeyT key = randomizeKey(i);
return nullptr;
}
-}
+} // namespace
// Here we have a single thread inserting some values, and several threads
// racing to delete the values in the order they were inserted.
VLOG(1) << "Testing insertion and erase with " << kInsertThreads
<< " thread inserting and " << kEraseThreads << " threads erasing.";
- globalAHM.reset(new AHMapT(kTestEraseInsertions / 4, config));
+ globalAHM = std::make_unique<AHMapT>(kTestEraseInsertions / 4, config);
vector<pthread_t> threadIds;
for (int64_t j = 0; j < kInsertThreads + kEraseThreads; j++) {
void* atomicHashArrayInsertRaceThread(void* /* j */) {
AHA* arr = atomicHashArrayInsertRaceArray.get();
uintptr_t numInserted = 0;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < 2; i++) {
if (arr->insert(RecordT(randomizeKey(i), 0)).first != arr->end()) {
numInserted++;
}
}
- pthread_exit((void *) numInserted);
+ return (void*)numInserted;
}
TEST(Ahm, atomic_hash_array_insert_race) {
AHA* arr = atomicHashArrayInsertRaceArray.get();
- int numIterations = 5000, FLAGS_numThreads = 4;
- void* statuses[FLAGS_numThreads];
+ int numIterations = 5000;
+ constexpr int numThreads = 4;
+ void* statuses[numThreads];
for (int i = 0; i < numIterations; i++) {
arr->clear();
- runThreads(atomicHashArrayInsertRaceThread, FLAGS_numThreads, statuses);
+ runThreads(atomicHashArrayInsertRaceThread, numThreads, statuses);
EXPECT_GE(arr->size(), 1);
- for (int j = 0; j < FLAGS_numThreads; j++) {
+ for (int j = 0; j < numThreads; j++) {
EXPECT_EQ(arr->size(), uintptr_t(statuses[j]));
}
}
std::cout << "loading global AHM with " << FLAGS_numThreads
<< " threads...\n";
uint64_t start = nowInUsec();
- globalAHM.reset(new AHMapT(maxBMElements, config));
+ globalAHM = std::make_unique<AHMapT>(maxBMElements, config);
numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
runThreads(insertThread);
uint64_t elapsed = nowInUsec() - start;
std::cout << "loading global QPAHM with " << FLAGS_numThreads
<< " threads...\n";
uint64_t start = nowInUsec();
- globalQPAHM.reset(new QPAHMapT(maxBMElements, qpConfig));
+ globalQPAHM = std::make_unique<QPAHMapT>(maxBMElements, qpConfig);
numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
runThreads(qpInsertThread);
uint64_t elapsed = nowInUsec() - start;
EXPECT_EQ(globalQPAHM->size(), FLAGS_numBMElements);
}
-}
+} // namespace
BENCHMARK(st_aha_find, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
KeyT key = i + j * numOpsPerThread * 100;
folly::doNotOptimizeAway(globalAHM->find(key) == globalAHM->end());
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
KeyT key = i + j * numOpsPerThread * 100;
folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
if (i % 128) { // ~1% insert mix
KeyT key = randomizeKey(i + j * numOpsPerThread);
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
if (i % 128) { // ~1% insert mix
KeyT key = randomizeKey(i + j * numOpsPerThread);
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
KeyT key = randomizeKey(i + j * numOpsPerThread);
folly::doNotOptimizeAway(globalAHA->find(key)->second);
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
KeyT key = randomizeKey(i + j * numOpsPerThread);
folly::doNotOptimizeAway(globalAHM->find(key)->second);
numOpsPerThread = iters / FLAGS_numThreads;
runThreads([](void* jj) -> void* {
int64_t j = (int64_t) jj;
- while (!runThreadsCreatedAllThreads.load());
+ while (!runThreadsCreatedAllThreads.load()) {
+ ;
+ }
for (int i = 0; i < numOpsPerThread; ++i) {
KeyT key = randomizeKey(i + j * numOpsPerThread);
folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
BENCHMARK(mt_ahm_insert, iters) {
BENCHMARK_SUSPEND {
- globalAHM.reset(new AHMapT(int(iters * LF), config));
+ globalAHM = std::make_unique<AHMapT>(int(iters * LF), config);
numOpsPerThread = iters / FLAGS_numThreads;
}
runThreads(insertThread);
BENCHMARK(mt_qpahm_insert, iters) {
BENCHMARK_SUSPEND {
- globalQPAHM.reset(new QPAHMapT(int(iters * LF), qpConfig));
+ globalQPAHM = std::make_unique<QPAHMapT>(int(iters * LF), qpConfig);
numOpsPerThread = iters / FLAGS_numThreads;
}
runThreads(qpInsertThread);