From: Peizhao Ou Date: Sat, 10 Feb 2018 03:59:25 +0000 (-0800) Subject: Refactors Folly map test cases to use cdsstress library X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=commitdiff_plain;h=aa07c23de77d0f7a6c34ee6c12ed9c644d1059b5 Refactors Folly map test cases to use cdsstress library --- diff --git a/folly/stress-test/CMakeLists.txt b/folly/stress-test/CMakeLists.txt index 147e645c..52a2323e 100644 --- a/folly/stress-test/CMakeLists.txt +++ b/folly/stress-test/CMakeLists.txt @@ -6,6 +6,8 @@ include_directories( /scratch/googletest/googletest/include /scratch/gflags/gflags/build/include /scratch/glog/glog/src + /scratch/benchmarks/libcds/test/include + /scratch/benchmarks/libcds ../.. ) @@ -14,29 +16,36 @@ link_directories( /scratch/glog/glog/glog-lib /scratch/gflags/gflags/build/gflags-lib /scratch/googletest/googletest + ~/benchmarks/orig-bin ) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++1y") -set(FOLLY_LIB folly pthread gflags glog gtest) +set(FOLLY_LIB folly pthread gflags glog gtest stress-framework) set(RCU_OBJ ../synchronization/.libs/Rcu.o) # Sequential driver -add_executable(stress-sequential-folly-map stress-sequential-folly-map.cpp ${RCU_OBJ}) +add_executable(stress-sequential-folly-map + stress-sequential-folly-map.cpp main.cpp ${RCU_OBJ}) target_link_libraries(stress-sequential-folly-map ${FOLLY_LIB}) -add_executable(stress-sequential-folly-queue stress-sequential-folly-queue.cpp ${RCU_OBJ}) +add_executable(stress-sequential-folly-queue + stress-sequential-folly-queue.cpp ${RCU_OBJ}) target_link_libraries(stress-sequential-folly-queue ${FOLLY_LIB}) -add_executable(stress-sequential-folly-sync stress-sequential-folly-sync.cpp ${RCU_OBJ}) +add_executable(stress-sequential-folly-sync + stress-sequential-folly-sync.cpp ${RCU_OBJ}) target_link_libraries(stress-sequential-folly-sync ${FOLLY_LIB}) # Parallel driver -add_executable(stress-parallel-folly-map stress-parallel-folly-map.cpp ${RCU_OBJ}) +add_executable(stress-parallel-folly-map + stress-parallel-folly-map.cpp main.cpp ${RCU_OBJ}) target_link_libraries(stress-parallel-folly-map ${FOLLY_LIB}) -add_executable(stress-parallel-folly-queue stress-parallel-folly-queue.cpp ${RCU_OBJ}) +add_executable(stress-parallel-folly-queue + stress-parallel-folly-queue.cpp ${RCU_OBJ}) target_link_libraries(stress-parallel-folly-queue ${FOLLY_LIB}) -add_executable(stress-parallel-folly-sync stress-parallel-folly-sync.cpp ${RCU_OBJ}) +add_executable(stress-parallel-folly-sync + stress-parallel-folly-sync.cpp ${RCU_OBJ}) target_link_libraries(stress-parallel-folly-sync ${FOLLY_LIB}) diff --git a/folly/stress-test/main.cpp b/folly/stress-test/main.cpp new file mode 100644 index 00000000..885d3f38 --- /dev/null +++ b/folly/stress-test/main.cpp @@ -0,0 +1,11 @@ +#include + +int main(int argc, char** argv) { + // Read test config file + cds_test::init_config(argc, argv); + + // Init Google test + ::testing::InitGoogleTest(&argc, argv); + int result = RUN_ALL_TESTS(); + return result; +} diff --git a/folly/stress-test/map_test.h b/folly/stress-test/map_test.h new file mode 100644 index 00000000..4d3d0fa4 --- /dev/null +++ b/folly/stress-test/map_test.h @@ -0,0 +1,94 @@ +#ifndef _FOLLY_MAP_TEST_H +#define _FOLLY_MAP_TEST_H + +#include +#include +#include + +#include +#include + +#include +#include +#include +#include +#include + +namespace folly_test { + +typedef folly::ConcurrentHashMap ConcurrentHashMap; +typedef folly::AtomicHashMap AtomicHashMap; +typedef folly::AtomicUnorderedInsertMap64 + AtomicUnorderedInsertMap; + +// AtomicUnorderedInsertMap +template +bool map_insert(AtomicUnorderedInsertMap* map, Key key, Value value) { + auto iter = map->find(key); + if (iter == map->cend() || iter->second != value) { + // Insert/update the pair + map->emplace(key, value); + return true; + } else { + return false; + } +} + +// AtomicHashMap +template +bool map_insert(AtomicHashMap* map, Key key, Value value) { + auto iter = map->find(key); + if (iter == map->end() || iter->second != value) { + // Insert/update the pair + map->insert({key, value}); + return true; + } else { + return false; + } +} + +// ConcurrentHashMap +template +bool map_insert(ConcurrentHashMap * map, Key key, Value value) { + auto iter = map->find(key); + if (iter == map->cend() || iter->second != value) { + // Insert/update the pair + map->insert({key, value}); + return true; + } else { + return false; + } +} + +template +bool map_find(const Map* map, Key key) { + return map->find(key) != map->cend(); +} + +// Specialization for AtomicHashMap +template +bool map_find(const AtomicHashMap* map, Key key) { + return map->find(key) != map->end(); +} + +// Doesn't erase for AtomicUnorderedInsertMap & AtomicHashMap, but returns +// whether the key exists in the map. +template +bool map_delete(Map* map, Key key) { + return map_find(map, key); +} + +// Specialization for ConcurrentHashMap +template +bool map_delete(ConcurrentHashMap* map, Key key) { + if (map_find(map, key)) { + map->erase(key); + return true; + } else { + return false; + } +} + +} // namespace folly_test + +#endif diff --git a/folly/stress-test/stress-parallel-folly-map.cpp b/folly/stress-test/stress-parallel-folly-map.cpp index 53b95290..ac8492c7 100644 --- a/folly/stress-test/stress-parallel-folly-map.cpp +++ b/folly/stress-test/stress-parallel-folly-map.cpp @@ -1,168 +1,148 @@ -#include -#include -#include - -#include - -#include - -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 ConcurrentHashMap; -typedef folly::AtomicHashMap AtomicHashMap; -typedef folly::AtomicUnorderedInsertMap64 - AtomicUnorderedInsertMap; -} - -template -bool map_contains(const AtomicUnorderedInsertMap* map, Key key) { - return map->find(key) != map->cend(); -} - -template -bool map_contains(const ConcurrentHashMap* map, Key key) { - return map->find(key) != map->cend(); -} - -template -bool map_contains(const Map* map, Key key) { - return map->find(key) != map->end(); -} - -template -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(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 -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 + 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 dis(2, s_nMapKeyRange); + + unsigned action_index = 0; size_t nInsertedNum = 0; + size_t nDeletedNum = 0; size_t nFindSuccess = 0; - std::unique_ptr 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 -void run_concurrent_hashmap(size_t map_size, size_t pass_count) { - size_t nInsertedNum = 0; - size_t nFindSuccess = 0; - std::unique_ptr 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( - 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 threads(new std::thread[s_nThreadCount]); \ + std::unique_ptr inserted_nums(new size_t[s_nThreadCount]); \ + std::unique_ptr deleted_nums(new size_t[s_nThreadCount]); \ + for (size_t i = 0; i < s_nThreadCount; i++) { \ + threads[i] = std::thread(run_test, 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 map( + new ConcurrentHashMap(s_nInitialMapSize)); + FollyMapThreading(ConcurrentHashMap, s_nConcurrentHashMapPassCount); } -TEST_F(FollyMapInsDelFindTest, FollyAtomicHashMap) { - run_atomic_hashmap( - kAtomicHashMapSize, - kAtomicHashMapPassCount); +TEST_F(FollyMapInsDelFindTest_Parallel, FollyAtomicHashMap) { + std::unique_ptr map( + new AtomicHashMap(s_nInitialMapSize)); + FollyMapThreading(AtomicHashMap, s_nAtomicHashMapPassCount); } -TEST_F(FollyMapInsDelFindTest, FollyAtomicUnorderedInsertMap) { - run_atomic_unordered_insert_map( - kAtomicUnorderedInsertMapSize, - kAtomicUnorderedInsertMapPassCount); +TEST_F(FollyMapInsDelFindTest_Parallel, FollyAtomicUnorderedInsertMap) { + std::unique_ptr 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 diff --git a/folly/stress-test/stress-sequential-folly-map.cpp b/folly/stress-test/stress-sequential-folly-map.cpp index 53b95290..61ce5f9e 100644 --- a/folly/stress-test/stress-sequential-folly-map.cpp +++ b/folly/stress-test/stress-sequential-folly-map.cpp @@ -1,168 +1,100 @@ -#include -#include -#include +#include "map_test.h" -#include +namespace folly_test { -#include +class FollyMapInsDelFindTest_Sequential : public cds_test::stress_fixture { +protected: + static unsigned s_nInsertDeletePercentage; + static size_t s_nMapSize; -namespace { + enum actions { do_find, do_insert, do_delete }; + static const unsigned int kShuffleSize = 100; + static actions s_arrShuffle[kShuffleSize]; -const unsigned s_nInsertPercentage = 10; + static size_t s_nConcurrentHashMapPassCount; + static size_t s_nAtomicHashMapPassCount; + static size_t s_nAtomicUnorderedInsertMapPassCount; -const size_t kConcurrentHashMapSize = 10000; -const size_t kConcurrentHashMapPassCount = 36000; + static void SetUpTestCase() { + const cds_test::config& cfg = get_config("SequentialFollyMap"); + GetConfigNonZeroExpected(InsertDeletePercentage, 5); + GetConfigNonZeroExpected(MapSize, 10000); + GetConfigNonZeroExpected(ConcurrentHashMapPassCount, 1000); + GetConfigNonZeroExpected(AtomicHashMapPassCount, 1000); + GetConfigNonZeroExpected(AtomicUnorderedInsertMapPassCount, 1000); + } -const size_t kAtomicHashMapSize = 10000; -const size_t kAtomicHashMapPassCount = 250000; - -const size_t kAtomicUnorderedInsertMapSize = 10000; -const size_t kAtomicUnorderedInsertMapPassCount = 500000; - -typedef folly::ConcurrentHashMap ConcurrentHashMap; -typedef folly::AtomicHashMap AtomicHashMap; -typedef folly::AtomicUnorderedInsertMap64 - AtomicUnorderedInsertMap; -} - -template -bool map_contains(const AtomicUnorderedInsertMap* map, Key key) { - return map->find(key) != map->cend(); -} - -template -bool map_contains(const ConcurrentHashMap* map, Key key) { - return map->find(key) != map->cend(); -} - -template -bool map_contains(const Map* map, Key key) { - return map->find(key) != map->end(); -} - -template -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(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; - } - } - } - } - EXPECT_EQ(nFindSuccess, nInsertedNum); -} - -template -void run_atomic_hashmap(size_t map_size, size_t pass_count) { + template static void run_test(Map* map, size_t pass_count) { size_t nInsertedNum = 0; + size_t nNotInsertedNum = 0; size_t nFindSuccess = 0; - std::unique_ptr 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 nFindFailed = 0; + size_t nDeletedNum = 0; + size_t nOperations = 0; -template -void run_concurrent_hashmap(size_t map_size, size_t pass_count) { - size_t nInsertedNum = 0; - size_t nFindSuccess = 0; - std::unique_ptr map(new Map(map_size)); + // The number to operate on the map. + size_t n = s_nMapSize; 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); - } - } + // Insert + unsigned mod = count % kShuffleSize; + if (mod < s_nInsertDeletePercentage) { + if (map_insert(map, n, n)) { + nInsertedNum++; + } else if (map_insert(map, n, n + 1)) { + nInsertedNum++; + } else { + nNotInsertedNum++; } + } else { + nNotInsertedNum++; + } + // Find + if (map_find(map, n)) { + ++nFindSuccess; + } else { + ++nFindFailed; + } + // Delete + if (mod < s_nInsertDeletePercentage && map_delete(map, n)) { + nDeletedNum++; + } + if (++n == 2 * s_nMapSize) { + n = s_nMapSize; + } } - EXPECT_EQ(nFindSuccess, nInsertedNum); -} - -class FollyMapInsDelFindTest: public ::testing::Test { + EXPECT_EQ(nInsertedNum, nDeletedNum); + EXPECT_EQ(nInsertedNum, nFindSuccess); + EXPECT_EQ(nFindFailed, nNotInsertedNum); + } }; -TEST_F(FollyMapInsDelFindTest, FollyConcurrentHashMap) { - run_concurrent_hashmap( - kConcurrentHashMapSize, - kConcurrentHashMapPassCount); +size_t FollyMapInsDelFindTest_Sequential::s_nMapSize; +unsigned FollyMapInsDelFindTest_Sequential::s_nInsertDeletePercentage; +const unsigned int FollyMapInsDelFindTest_Sequential::kShuffleSize; +FollyMapInsDelFindTest_Sequential::actions + FollyMapInsDelFindTest_Sequential::s_arrShuffle + [FollyMapInsDelFindTest_Sequential::kShuffleSize]; + +size_t FollyMapInsDelFindTest_Sequential::s_nConcurrentHashMapPassCount; +size_t FollyMapInsDelFindTest_Sequential::s_nAtomicHashMapPassCount; +size_t FollyMapInsDelFindTest_Sequential::s_nAtomicUnorderedInsertMapPassCount; + +TEST_F(FollyMapInsDelFindTest_Sequential, FollyConcurrentHashMap) { + std::unique_ptr map( + new ConcurrentHashMap(s_nMapSize)); + run_test(map.get(), s_nConcurrentHashMapPassCount); } -TEST_F(FollyMapInsDelFindTest, FollyAtomicHashMap) { - run_atomic_hashmap( - kAtomicHashMapSize, - kAtomicHashMapPassCount); +TEST_F(FollyMapInsDelFindTest_Sequential, FollyAtomicHashMap) { + std::unique_ptr map( + new AtomicHashMap(s_nMapSize)); + run_test(map.get(), s_nAtomicHashMapPassCount); } -TEST_F(FollyMapInsDelFindTest, FollyAtomicUnorderedInsertMap) { - run_atomic_unordered_insert_map( - kAtomicUnorderedInsertMapSize, - kAtomicUnorderedInsertMapPassCount); +TEST_F(FollyMapInsDelFindTest_Sequential, FollyAtomicUnorderedInsertMap) { + std::unique_ptr map( + new AtomicUnorderedInsertMap(s_nMapSize)); + run_test(map.get(), 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