From e48795a76ba22ef6cdd3621a8baa616188e9cc8b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 4 Nov 2021 11:35:57 +0100 Subject: Updated shootout2_cmap.cpp --- benchmarks/shootout2_cmap.cpp | 127 ++++++++++++++++++++++++------------------ 1 file changed, 72 insertions(+), 55 deletions(-) diff --git a/benchmarks/shootout2_cmap.cpp b/benchmarks/shootout2_cmap.cpp index 58a31009..a70b4f91 100644 --- a/benchmarks/shootout2_cmap.cpp +++ b/benchmarks/shootout2_cmap.cpp @@ -22,12 +22,13 @@ template inline void destroy_me(C& c) { C().swap(c); } #define i_tag ii #include -KHASH_MAP_INIT_INT64(ii, int64_t) - - size_t seed; static const float max_load_factor = 0.77f; +KHASH_MAP_INIT_INT64(ii, int64_t) +template using robin_hood_flat_map = robin_hood::unordered_flat_map< + K, V, robin_hood::hash, std::equal_to, 77>; + stc64_t rng; #define SEED(s) rng = stc64_init(seed) #define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1)) @@ -38,7 +39,7 @@ stc64_t rng; #define CMAP_PUT(X, key, val) cmap_##X##_emplace_or_assign(&map, key, val).ref->second #define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).ref->second #define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) -#define CMAP_FIND(X, key) cmap_##X##_contains(map, key) +#define CMAP_FIND(X, key) cmap_##X##_contains(&map, key) #define CMAP_FOR(X, i) c_foreach (i, cmap_##X, map) #define CMAP_ITEM(X, i) i.ref->second #define CMAP_SIZE(X) cmap_##X##_size(map) @@ -59,7 +60,7 @@ stc64_t rng; #define UMAP_SETUP(X, Key, Value) std::unordered_map map; map.max_load_factor(max_load_factor) #define UMAP_PUT(X, key, val) (map[key] = val) #define UMAP_EMPLACE(X, key, val) map.emplace(key, val).first->second -#define UMAP_FIND(X, key) (map.find(key) != map.end()) +#define UMAP_FIND(X, key) int(map.find(key) != map.end()) #define UMAP_ERASE(X, key) map.erase(key) #define UMAP_FOR(X, i) for (auto i: map) #define UMAP_ITEM(X, i) i.second @@ -68,18 +69,6 @@ stc64_t rng; #define UMAP_CLEAR(X) map.clear() #define UMAP_DTOR(X) destroy_me(map) -#define BMAP_SETUP(X, Key, Value) ska::bytell_hash_map map; map.max_load_factor(max_load_factor) -#define BMAP_PUT(X, key, val) UMAP_PUT(X, key, val) -#define BMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) -#define BMAP_FIND(X, key) UMAP_FIND(X, key) -#define BMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define BMAP_FOR(X, i) UMAP_FOR(X, i) -#define BMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define BMAP_SIZE(X) UMAP_SIZE(X) -#define BMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define BMAP_CLEAR(X) UMAP_CLEAR(X) -#define BMAP_DTOR(X) UMAP_DTOR(X) - #define FMAP_SETUP(X, Key, Value) ska::flat_hash_map map; map.max_load_factor(max_load_factor) #define FMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define FMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) @@ -104,7 +93,8 @@ stc64_t rng; #define HMAP_CLEAR(X) UMAP_CLEAR(X) #define HMAP_DTOR(X) UMAP_DTOR(X) -#define RMAP_SETUP(X, Key, Value) robin_hood::unordered_map map +//#define RMAP_SETUP(X, Key, Value) robin_hood::unordered_map map +#define RMAP_SETUP(X, Key, Value) robin_hood_flat_map map #define RMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define RMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) #define RMAP_FIND(X, key) UMAP_FIND(X, key) @@ -130,23 +120,24 @@ stc64_t rng; enum { RR = 27, - FAC = 3, - N0 = 10000000 * FAC, - N1 = 10000000 * FAC, - N2 = 10000000 * FAC, - N3 = 10000000 * FAC, - N4 = 10000000 * FAC, + N = 10000000, + N0 = N * 4, + N1 = N * 2, + N2 = N * 4, + N3 = N * 6, + N4 = N * 8, + N5 = N * 6, }; int rr = RR; -#define MAP_TEST0(M, X) \ +#define MAP_TEST0(M, X, n) \ { \ M##_SETUP(X, int64_t, int64_t); \ uint64_t checksum = 0; \ SEED(seed); \ clock_t difference, before = clock(); \ - for (size_t i = 0; i < N0; ++i) { \ + for (size_t i = 0; i < n; ++i) { \ checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ } \ difference = clock() - before; \ @@ -155,13 +146,13 @@ int rr = RR; M##_DTOR(X); \ } -#define MAP_TEST1(M, X) \ +#define MAP_TEST1(M, X, n) \ { \ M##_SETUP(X, int64_t, int64_t); \ uint64_t checksum = 0, erased = 0; \ SEED(seed); \ clock_t difference, before = clock(); \ - for (size_t i = 0; i < N1; ++i) { \ + for (size_t i = 0; i < n; ++i) { \ checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ erased += M##_ERASE(X, RAND(rr)); \ } \ @@ -171,14 +162,14 @@ int rr = RR; M##_DTOR(X); \ } -#define MAP_TEST2(M, X) \ +#define MAP_TEST2(M, X, n) \ { \ M##_SETUP(X, int64_t, int64_t); \ size_t erased = 0; \ clock_t difference, before = clock(); \ - for (size_t i = 0; i < N2; ++i) \ + for (size_t i = 0; i < n; ++i) \ M##_PUT(X, i, i); \ - for (size_t i = 0; i < N2; ++i) \ + for (size_t i = 0; i < n; ++i) \ erased += M##_ERASE(X, i); \ difference = clock() - before; \ printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ @@ -186,16 +177,17 @@ int rr = RR; M##_DTOR(X); \ } -#define MAP_TEST3(M, X) \ +#define MAP_TEST3(M, X, n) \ { \ M##_SETUP(X, int64_t, int64_t); \ size_t erased = 0; \ - clock_t difference, before = clock(); \ + clock_t difference, before; \ SEED(seed); \ - for (size_t i = 0; i < N3; ++i) \ + for (size_t i = 0; i < n; ++i) \ M##_PUT(X, RAND(rr), i); \ SEED(seed); \ - for (size_t i = 0; i < N3; ++i) \ + before = clock(); \ + for (size_t i = 0; i < n; ++i) \ erased += M##_ERASE(X, RAND(rr)); \ difference = clock() - before; \ printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ @@ -203,12 +195,12 @@ int rr = RR; M##_DTOR(X); \ } -#define MAP_TEST4(M, X) \ +#define MAP_TEST4(M, X, n) \ { \ M##_SETUP(X, int64_t, int64_t); \ size_t sum = 0; \ SEED(seed); \ - for (size_t i = 0; i < N4; ++i) \ + for (size_t i = 0; i < n; ++i) \ M##_PUT(X, RAND(rr), i); \ clock_t difference, before = clock(); \ for (int k=0; k<5; k++) M##_FOR (X, i) \ @@ -219,14 +211,35 @@ int rr = RR; M##_DTOR(X); \ } +#define MAP_TEST5(M, X, n) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + size_t found = 0; \ + clock_t difference, before; \ + SEED(seed); \ + for (size_t i = 0; i < n; ++i) \ + M##_PUT(X, RAND(rr), i); \ + before = clock(); \ + for (size_t i = 0; i < n/2; ++i) \ + found += M##_FIND(X, RAND(rr)); \ + SEED(seed); \ + for (size_t i = 0; i < n/2; ++i) \ + found += M##_FIND(X, RAND(rr)); \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, found %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, found, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ + M##_DTOR(X); \ +} + + #ifdef __cplusplus -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) MAP_TEST##n(UMAP, ii) MAP_TEST##n(PMAP, ii) \ - MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) MAP_TEST##n(RMAP, ii) /*MAP_TEST##n(HMAP, ii)*/ -#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii) /*MAP_TEST##n(KMAP, ii)*/ MAP_TEST##n(UMAP, ii) MAP_TEST##n(PMAP, ii) \ - MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) MAP_TEST##n(RMAP, ii) /*MAP_TEST##n(HMAP, ii)*/ +#define RUN_TEST(n) MAP_TEST##n(CMAP, ii, N##n) MAP_TEST##n(KMAP, ii, N##n) MAP_TEST##n(UMAP, ii, N##n) MAP_TEST##n(PMAP, ii, N##n) \ + MAP_TEST##n(FMAP, ii, N##n) MAP_TEST##n(RMAP, ii, N##n) +#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii, N##n) MAP_TEST##n(UMAP, ii, N##n) MAP_TEST##n(PMAP, ii, N##n) \ + MAP_TEST##n(FMAP, ii, N##n) MAP_TEST##n(RMAP, ii, N##n) #else -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) -#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii) +#define RUN_TEST(n) MAP_TEST##n(CMAP, ii, N##n) MAP_TEST##n(KMAP, ii, N##n) +#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii, N##n) #endif @@ -235,26 +248,30 @@ int main(int argc, char* argv[]) rr = argc == 2 ? atoi(argv[1]) : RR; seed = time(NULL); - printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); - printf("CMAP = STC cmap\n" - "KMAP = Klib khash\n" + printf("\nUnordered hash map shootout\n\n"); + printf("CMAP = https://github.com/tylov/STC\n" + "KMAP = https://github.com/attractivechaos/klib\n" "UMAP = std::unordered_map\n" - "PMAP = phmap::flat_hash_map\n" - "BMAP = ska::bytell_hash_map\n" - "FMAP = ska::flat_hash_map\n" - "RMAP = robin_hood::unordered_map\n"); - printf("\nUnordered maps: Insert %d random keys:\n", N0); + "PMAP = https://github.com/greg7mdp/parallel-hashmap\n" + "FMAP = https://github.com/skarupke/flat_hash_map\n" + "RMAP = https://github.com/martinus/robin-hood-hashing\n"); + + printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); + printf("\nN=%d. Insert random keys:\n", N0); RUN_TEST(0) - printf("\nUnordered maps: %d insert random key + try to remove another random key:\n", N1); + printf("\nN=%d. Insert random key + try to remove another random key:\n", N1); RUN_TEST(1) - printf("\nUnordered maps: Insert %d sequential keys, then remove them in same order:\n", N2); + printf("\nN=%d. Insert sequential keys, then remove them in same order:\n", N2); RUN_TEST(2) - printf("\nUnordered maps: Insert %d random keys, then remove them in same order:\n", N3); + printf("\nN=%d. Remove random keys:\n", N3); RUN_TEST(3) - printf("\nUnordered maps: Iterate %d random keys:\n", N4); + printf("\nN=%d. Iterate random keys:\n", N4); RUNX_TEST(4) + + printf("\nN=%d. Lookup random keys:\n", N5); + RUN_TEST(5) } -- cgit v1.2.3