-#include <folly/concurrency/ConcurrentHashMap.h>
-#include <folly/AtomicHashMap.h>
-#include <folly/AtomicUnorderedMap.h>
-
-#include <gtest/gtest.h>
-
-#include <memory>
-
-namespace {
-
-const unsigned s_nInsertPercentage = 10;
-
-const size_t kConcurrentHashMapSize = 10000;
-const size_t kConcurrentHashMapPassCount = 36000;
-
-const size_t kAtomicHashMapSize = 10000;
-const size_t kAtomicHashMapPassCount = 250000;
-
-const size_t kAtomicUnorderedInsertMapSize = 10000;
-const size_t kAtomicUnorderedInsertMapPassCount = 500000;
-
-typedef folly::ConcurrentHashMap<size_t, size_t> ConcurrentHashMap;
-typedef folly::AtomicHashMap<size_t, size_t> AtomicHashMap;
-typedef folly::AtomicUnorderedInsertMap64<size_t, size_t>
- AtomicUnorderedInsertMap;
-}
-
-template <typename Key>
-bool map_contains(const AtomicUnorderedInsertMap* map, Key key) {
- return map->find(key) != map->cend();
-}
-
-template <typename Key>
-bool map_contains(const ConcurrentHashMap* map, Key key) {
- return map->find(key) != map->cend();
-}
-
-template <typename Map, typename Key>
-bool map_contains(const Map* map, Key key) {
- return map->find(key) != map->end();
-}
-
-template <typename Map>
-void run_atomic_unordered_insert_map(size_t map_size, size_t pass_count) {
- size_t nInsertedNum = 0;
- size_t nFindSuccess = 0;
- std::unique_ptr<Map> map(new Map(map_size));
- for (size_t count = 0; count < pass_count; count++) {
- for (size_t i = 0; i < map_size; ++i) {
- // The number to operate on the map.
- size_t n = map_size + i;
- // Insert
- if (i % s_nInsertPercentage == 1) {
- auto iter = map->find(i);
- if (iter != map->cend()) {
- if (iter->second == n) {
- map->emplace(i, n / 2);
- } else {
- map->emplace(i, n);
- }
- } else {
- map->emplace(i, n);
- }
- nInsertedNum++;
- }
- // Find
- {
- if (map_contains(map.get(), i)) {
- ++nFindSuccess;
- }
- }
- }
+#include "map_test.h"
+
+namespace folly_test {
+
+class FollyMapInsDelFindTest_Parallel : public cds_test::stress_fixture {
+protected:
+ static unsigned s_nInsertPercentage;
+ static unsigned s_nDeletePercentage;
+ static size_t s_nThreadCount;
+ static size_t s_nMapKeyRange;
+ static size_t s_nInitialMapSize;
+
+ enum actions { do_find, do_insert, do_delete };
+ static const unsigned int kShuffleSize = 100;
+ static actions s_arrShuffle[kShuffleSize];
+
+ static size_t s_nConcurrentHashMapPassCount;
+ static size_t s_nAtomicHashMapPassCount;
+ static size_t s_nAtomicUnorderedInsertMapPassCount;
+
+ static void InitShuffleArray() {
+ // Build an array of shuffled actions.
+ EXPECT_LE(s_nInsertPercentage + s_nDeletePercentage, 100);
+ actions* pFirst = s_arrShuffle;
+ actions* pLast = s_arrShuffle + s_nInsertPercentage;
+ std::fill(pFirst, pLast, do_insert);
+ pFirst = pLast;
+ pLast += s_nDeletePercentage;
+ std::fill(pFirst, pLast, do_delete);
+ pFirst = pLast;
+ pLast = s_arrShuffle + sizeof(s_arrShuffle) / sizeof(s_arrShuffle[0]);
+ if (pFirst < pLast) {
+ std::fill(pFirst, pLast, do_find);
}
- EXPECT_EQ(nFindSuccess, nInsertedNum);
-}
-
-template <typename Map>
-void run_atomic_hashmap(size_t map_size, size_t pass_count) {
+ std::random_device rd;
+ std::mt19937 g(rd());
+ std::shuffle(s_arrShuffle, pLast, g);
+ }
+
+ static void SetUpTestCase() {
+ InitShuffleArray();
+ const cds_test::config& cfg = get_config("ParallelFollyMap");
+ GetConfigNonZeroExpected(InsertPercentage, 5);
+ GetConfigNonZeroExpected(DeletePercentage, 5);
+ GetConfigNonZeroExpected(ThreadCount, 4);
+ GetConfigNonZeroExpected(MapKeyRange, 20000);
+ GetConfigNonZeroExpected(InitialMapSize, 20000);
+ GetConfigNonZeroExpected(ConcurrentHashMapPassCount, 1000);
+ GetConfigNonZeroExpected(AtomicHashMapPassCount, 1000);
+ GetConfigNonZeroExpected(AtomicUnorderedInsertMapPassCount, 1000);
+ }
+
+ template <typename Map>
+ static void run_test(Map* map, size_t pass_count, size_t* inserted_num,
+ size_t* deleted_num) {
+ std::random_device rd;
+ std::mt19937 gen(rd());
+ std::uniform_int_distribution<size_t> dis(2, s_nMapKeyRange);
+
+ unsigned action_index = 0;
size_t nInsertedNum = 0;
+ size_t nDeletedNum = 0;
size_t nFindSuccess = 0;
- std::unique_ptr<Map> map(new Map(map_size));
- for (size_t count = 0; count < pass_count; count++) {
- for (size_t i = 0; i < map_size; ++i) {
- // The number to operate on the map.
- size_t n = map_size + i;
- // Insert
- if (i % s_nInsertPercentage == 1) {
- auto iter = map->find(i);
- if (iter != map->end()) {
- if (iter->second == n) {
- iter->second = n / 2;
- } else {
- iter->second = n;
- }
- } else {
- map->insert({i, n});
- }
- nInsertedNum++;
- }
- // Find
- {
- if (map_contains(map.get(), i)) {
- ++nFindSuccess;
- }
- }
- }
- }
- EXPECT_EQ(nFindSuccess, nInsertedNum);
-}
+ size_t nOperations = 0;
-template <typename Map>
-void run_concurrent_hashmap(size_t map_size, size_t pass_count) {
- size_t nInsertedNum = 0;
- size_t nFindSuccess = 0;
- std::unique_ptr<Map> map(new Map(map_size));
for (size_t count = 0; count < pass_count; count++) {
- for (size_t i = 0; i < map_size; ++i) {
- // The number to operate on the map.
- size_t n = map_size + i;
- // Insert
- if (i % s_nInsertPercentage == 1) {
- auto iter = map->insert({i, n});
- nInsertedNum++;
- }
- // Find
- {
- if (map_contains(map.get(), i)) {
- ++nFindSuccess;
- }
- }
- // Delete
- if (i % s_nInsertPercentage == 1) {
- if (map_contains(map.get(), i)) {
- map->erase(i);
- }
- }
+ // The number to operate on the map.
+ size_t key = dis(gen);
+ switch (s_arrShuffle[action_index]) {
+ case do_insert: {
+ size_t val = dis(gen);
+ if (map_insert(map, key, val)) {
+ nInsertedNum++;
+ }
+ break;
+ }
+ case do_delete: {
+ if (map_delete(map, key)) {
+ nDeletedNum++;
+ }
+ break;
}
+ case do_find: {
+ if (map_find(map, key)) {
+ ++nFindSuccess;
+ }
+ break;
+ }
+ default: { break; }
+ }
+ if (++action_index >= kShuffleSize) {
+ action_index = 0;
+ }
}
- EXPECT_EQ(nFindSuccess, nInsertedNum);
-}
-
-class FollyMapInsDelFindTest: public ::testing::Test {
+ *inserted_num = nInsertedNum;
+ *deleted_num = nDeletedNum;
+ }
};
-TEST_F(FollyMapInsDelFindTest, FollyConcurrentHashMap) {
- run_concurrent_hashmap<ConcurrentHashMap>(
- kConcurrentHashMapSize,
- kConcurrentHashMapPassCount);
+size_t FollyMapInsDelFindTest_Parallel::s_nThreadCount;
+size_t FollyMapInsDelFindTest_Parallel::s_nMapKeyRange;
+size_t FollyMapInsDelFindTest_Parallel::s_nInitialMapSize;
+unsigned FollyMapInsDelFindTest_Parallel::s_nInsertPercentage;
+unsigned FollyMapInsDelFindTest_Parallel::s_nDeletePercentage;
+const unsigned int FollyMapInsDelFindTest_Parallel::kShuffleSize;
+FollyMapInsDelFindTest_Parallel::actions FollyMapInsDelFindTest_Parallel::
+ s_arrShuffle[FollyMapInsDelFindTest_Parallel::kShuffleSize];
+size_t FollyMapInsDelFindTest_Parallel::s_nConcurrentHashMapPassCount;
+size_t FollyMapInsDelFindTest_Parallel::s_nAtomicHashMapPassCount;
+size_t FollyMapInsDelFindTest_Parallel::s_nAtomicUnorderedInsertMapPassCount;
+
+#define FollyMapThreading(map_type, pass_count) \
+ std::unique_ptr<std::thread[]> threads(new std::thread[s_nThreadCount]); \
+ std::unique_ptr<size_t[]> inserted_nums(new size_t[s_nThreadCount]); \
+ std::unique_ptr<size_t[]> deleted_nums(new size_t[s_nThreadCount]); \
+ for (size_t i = 0; i < s_nThreadCount; i++) { \
+ threads[i] = std::thread(run_test<map_type>, map.get(), pass_count, \
+ &inserted_nums[i], &deleted_nums[i]); \
+ } \
+ size_t inserted_sum = 0; \
+ size_t deleted_sum = 0; \
+ for (size_t i = 0; i < s_nThreadCount; i++) { \
+ threads[i].join(); \
+ inserted_sum += inserted_nums[i]; \
+ deleted_sum += deleted_nums[i]; \
+ } \
+ EXPECT_LE(deleted_sum, inserted_sum);
+
+TEST_F(FollyMapInsDelFindTest_Parallel, FollyConcurrentHashMap) {
+ std::unique_ptr<ConcurrentHashMap> map(
+ new ConcurrentHashMap(s_nInitialMapSize));
+ FollyMapThreading(ConcurrentHashMap, s_nConcurrentHashMapPassCount);
}
-TEST_F(FollyMapInsDelFindTest, FollyAtomicHashMap) {
- run_atomic_hashmap<AtomicHashMap>(
- kAtomicHashMapSize,
- kAtomicHashMapPassCount);
+TEST_F(FollyMapInsDelFindTest_Parallel, FollyAtomicHashMap) {
+ std::unique_ptr<AtomicHashMap> map(
+ new AtomicHashMap(s_nInitialMapSize));
+ FollyMapThreading(AtomicHashMap, s_nAtomicHashMapPassCount);
}
-TEST_F(FollyMapInsDelFindTest, FollyAtomicUnorderedInsertMap) {
- run_atomic_unordered_insert_map<AtomicUnorderedInsertMap>(
- kAtomicUnorderedInsertMapSize,
- kAtomicUnorderedInsertMapPassCount);
+TEST_F(FollyMapInsDelFindTest_Parallel, FollyAtomicUnorderedInsertMap) {
+ std::unique_ptr<AtomicUnorderedInsertMap> map(
+ new AtomicUnorderedInsertMap(s_nInitialMapSize));
+ FollyMapThreading(AtomicUnorderedInsertMap,
+ s_nAtomicUnorderedInsertMapPassCount);
}
-int main(int argc, char** argv) {
- // Init Google test
- ::testing::InitGoogleTest(&argc, argv);
- int result = RUN_ALL_TESTS();
- return result;
-}
+} // namespace folly_test