/*
- * Copyright 2015 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;
using folly::AtomicHashMap;
using folly::AtomicHashArray;
+using folly::StringPiece;
// Tunables:
DEFINE_double(targetLoadFactor, 0.75, "Target memory utilization fraction.");
static int64_t nowInUsec() {
timeval tv;
- gettimeofday(&tv, 0);
+ gettimeofday(&tv, nullptr);
return int64_t(tv.tv_sec) * 1000 * 1000 + tv.tv_usec;
}
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.";
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);
}
}
// 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 <<
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);
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());
+ 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]));
}
}
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);
projects / folly.git / blobdiff