From a9ce3df5c59515c12d4fcdf3b7ad43cefdf122b6 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 21 Dec 2020 14:28:56 +0100 Subject: Added some benchmarks. Fix typo in cdeq.h --- examples/benchmark.cpp | 233 ------------------------------------------------- examples/birthday.c | 46 +++++----- examples/heap.c | 48 ---------- examples/rngtest.c | 40 --------- 4 files changed, 21 insertions(+), 346 deletions(-) delete mode 100644 examples/benchmark.cpp delete mode 100644 examples/heap.c delete mode 100644 examples/rngtest.c (limited to 'examples') diff --git a/examples/benchmark.cpp b/examples/benchmark.cpp deleted file mode 100644 index a159d24b..00000000 --- a/examples/benchmark.cpp +++ /dev/null @@ -1,233 +0,0 @@ -#include -#include -#include -#include -#include -#include "others/khash.h" - -#ifdef __cplusplus -#include -#include "others/bytell_hash_map.hpp" -#include "others/robin_hood.hpp" -#include "others/hopscotch_map.h" -#include "others/sparsepp/spp.h" -template inline void destroy_me(C& c) { C().swap(c); } -#endif - -// Visual Studio: compile with -TP to force C++: cl -TP -EHsc -O2 benchmark.c - -static inline uint32_t fibonacci_hash(const void* data, size_t len) { - return (uint32_t) (((*(const uint64_t *) data) * 11400714819323198485llu) >> 24); -} - -// cmap and khash template expansion -using_cmap(ii, int64_t, int64_t, c_default_del, c_default_equals, fibonacci_hash); // c_default_hash); -KHASH_MAP_INIT_INT64(ii, int64_t) - - -size_t seed; -static const float max_load_factor = 0.77f; - -crand_t rng; -#define SEED(s) rng = crand_init(seed) -#define RAND(N) (crand_next(&rng) & ((1 << N) - 1)) - - -#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_inits \ - ; cmap_##X##_set_load_factors(&map, max_load_factor, 0.0) -#define CMAP_PUT(X, key, val) cmap_##X##_put(&map, key, val).first->second -#define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val) -#define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) -#define CMAP_FIND(X, key) (cmap_##X##_find(map, key) != NULL) -#define CMAP_FOR(X, i) c_foreach (i, cmap_##X, map) -#define CMAP_ITEM(X, i) i.ref->second -#define CMAP_SIZE(X) cmap_size(map) -#define CMAP_BUCKETS(X) cmap_##X##_bucket_count(map) -#define CMAP_CLEAR(X) cmap_##X##_clear(&map) -#define CMAP_DTOR(X) cmap_##X##_del(&map) - -#define KMAP_SETUP(X, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret -#define KMAP_PUT(X, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) -#define KMAP_EMPLACE(X, key, val) (ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val) : val) -#define KMAP_ERASE(X, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) -#define KMAP_FIND(X, key) (kh_get(ii, map, key) != kh_end(map)) -#define KMAP_SIZE(X) kh_size(map) -#define KMAP_BUCKETS(X) kh_n_buckets(map) -#define KMAP_CLEAR(X) kh_clear(ii, map) -#define KMAP_DTOR(X) kh_destroy(ii, map) - -#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) -#define UMAP_FIND(X, key) (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 -#define UMAP_SIZE(X) map.size() -#define UMAP_BUCKETS(X) map.bucket_count() -#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) -#define FMAP_FIND(X, key) UMAP_FIND(X, key) -#define FMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define FMAP_FOR(X, i) UMAP_FOR(X, i) -#define FMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define FMAP_SIZE(X) UMAP_SIZE(X) -#define FMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define FMAP_CLEAR(X) UMAP_CLEAR(X) -#define FMAP_DTOR(X) UMAP_DTOR(X) - -#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map map; map.max_load_factor(max_load_factor) -#define HMAP_PUT(X, key, val) UMAP_PUT(X, key, val) -#define HMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) -#define HMAP_FIND(X, key) UMAP_FIND(X, key) -#define HMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define HMAP_FOR(X, i) UMAP_FOR(X, i) -#define HMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define HMAP_SIZE(X) UMAP_SIZE(X) -#define HMAP_BUCKETS(X) UMAP_BUCKETS(X) -#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_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) -#define RMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define RMAP_FOR(X, i) UMAP_FOR(X, i) -#define RMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define RMAP_SIZE(X) UMAP_SIZE(X) -#define RMAP_BUCKETS(X) map.mask() -#define RMAP_CLEAR(X) UMAP_CLEAR(X) -#define RMAP_DTOR(X) UMAP_DTOR(X) - -#define SMAP_SETUP(X, Key, Value) spp::sparse_hash_map map; map.max_load_factor(max_load_factor) -#define SMAP_PUT(X, key, val) UMAP_PUT(X, key, val) -#define SMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) -#define SMAP_FIND(X, key) UMAP_FIND(X, key) -#define SMAP_ERASE(X, key) UMAP_ERASE(X, key) -#define SMAP_FOR(X, i) UMAP_FOR(X, i) -#define SMAP_ITEM(X, i) UMAP_ITEM(X, i) -#define SMAP_SIZE(X) UMAP_SIZE(X) -#define SMAP_BUCKETS(X) UMAP_BUCKETS(X) -#define SMAP_CLEAR(X) UMAP_CLEAR(X) -#define SMAP_DTOR(X) UMAP_DTOR(X) - -enum { - FAC = 2, - N1 = 10000000 * FAC, - N2 = 10000000 * FAC, - N3 = 10000000 * FAC, - N4 = 10000000 * FAC, - RR = 24 -}; -int rr = RR; - - -#define MAP_TEST1(M, X) \ -{ \ - 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) { \ - checksum += ++ M##_PUT(X, RAND(rr), i); \ - erased += M##_ERASE(X, RAND(rr)); \ - } \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, sum: %zu, erased %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, checksum, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST2(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - size_t erased = 0; \ - clock_t difference, before = clock(); \ - for (size_t i = 0; i < N2; ++i) \ - M##_PUT(X, i, i); \ - for (size_t i = 0; i < N2; ++i) \ - erased += M##_ERASE(X, i); \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST3(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - size_t erased = 0; \ - clock_t difference, before = clock(); \ - SEED(seed); \ - for (size_t i = 0; i < N3; ++i) \ - M##_PUT(X, RAND(rr), i); \ - SEED(seed); \ - for (size_t i = 0; i < N3; ++i) \ - erased += M##_ERASE(X, RAND(rr)); \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(X); \ -} - -#define MAP_TEST4(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - size_t sum = 0; \ - SEED(seed); \ - for (size_t i = 0; i < N4; ++i) \ - M##_PUT(X, RAND(rr), i); \ - clock_t difference, before = clock(); \ - for (int k=0; k<5; k++) M##_FOR (X, i) \ - sum += M##_ITEM(X, i); \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, sum %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, sum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \ - M##_CLEAR(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(SMAP, 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(SMAP, ii) \ - MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) /*MAP_TEST##n(RMAP, ii)*/ MAP_TEST##n(HMAP, ii) -#else -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) -#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii) -#endif - - -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("\nUnordered maps: %d repeats of Insert random key + try to remove a random key:\n", N1); - RUN_TEST(1) - - printf("\nUnordered maps: Insert %d index 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); - RUN_TEST(3) - - printf("\nUnordered maps: Iterate %d random keys:\n", N4); - RUNX_TEST(4) -} diff --git a/examples/birthday.c b/examples/birthday.c index 7ed30bf1..a2856a3f 100644 --- a/examples/birthday.c +++ b/examples/birthday.c @@ -1,61 +1,57 @@ - +#include #include #include #include #include -#include using_cmap(ic, uint64_t, uint8_t); +static uint64_t seed = 12345; -const static uint64_t seed = 1234; -const static uint64_t N = 1ull << 27; -const static uint64_t mask = (1ull << 52) - 1; - -void repeats(void) +static void test_repeats(void) { + enum {BITS = 46, BITS_TEST = BITS/2 + 2}; + const static uint64_t N = 1ull << BITS_TEST; + const static uint64_t mask = (1ull << BITS) - 1; + + printf("birthday paradox: value range: 2^%d, testing repeats of 2^%d values\n", BITS, BITS_TEST); crand_t rng = crand_init(seed); cmap_ic m = cmap_ic_init(); cmap_ic_reserve(&m, N); - clock_t now = clock(); c_forrange (i, N) { uint64_t k = crand_next(&rng) & mask; int v = ++cmap_ic_emplace(&m, k, 0).first->second; - if (v > 1) printf("%zu: %llx - %d\n", i, k, v); + if (v > 1) printf("repeated value %llx (%d) at 2^%d\n", k, v, (int) log2(i)); } - float diff = (float) (clock() - now) / CLOCKS_PER_SEC; - printf("%.02f", diff); } using_cmap(x, uint32_t, uint64_t); -using_cvec(x, uint64_t); -void distribution(void) +void test_distribution(void) { - crand_t rng = crand_init(seed); // time(NULL), time(NULL)); - const size_t N = 1ull << 28, M = 1ull << 9; // 1ull << 10; - cmap_x map = cmap_x_with_capacity(M); - clock_t now = clock(); - crand_uniform_t dist = crand_uniform_init(0, M); + enum {BITS = 26}; + printf("distribution test: 2^%d values\n", BITS); + crand_t rng = crand_init(seed); + const size_t N = 1ull << BITS ; + cmap_x map = cmap_x_init(); c_forrange (N) { - ++cmap_x_emplace(&map, crand_uniform(&rng, &dist), 0).first->second; + uint64_t k = crand_next(&rng); + ++cmap_x_emplace(&map, k & 0xf, 0).first->second; } - float diff = (float) (clock() - now) / CLOCKS_PER_SEC; uint64_t sum = 0; c_foreach (i, cmap_x, map) sum += i.ref->second; sum /= map.size; c_foreach (i, cmap_x, map) - printf("%u: %zu - %zu\n", i.ref->first, i.ref->second, sum); - - printf("%.02f\n", diff); + printf("%4u: %zu - %zu: %11.8f\n", i.ref->first, i.ref->second, sum, (1 - (double) i.ref->second / sum)); } int main() { - repeats(); - //distribution(); + seed = time(NULL); + test_distribution(); + test_repeats(); } \ No newline at end of file diff --git a/examples/heap.c b/examples/heap.c deleted file mode 100644 index c7292d2e..00000000 --- a/examples/heap.c +++ /dev/null @@ -1,48 +0,0 @@ -#include -#include -#include -#include -#include - -using_cvec(f, float); -using_cpque(f, cvec_f, >); - -int main() -{ - uint32_t seed = time(NULL); - crand_t rng; - int N = 3000000, M = 100; - - cpque_f pq = cpque_f_init(); - - rng = crand_init(seed); - clock_t start = clock(); - c_forrange (i, int, N) - cvec_f_push_back(&pq, (float) crand_nextf(&rng)*100000); - - cpque_f_make_heap(&pq); - printf("Built priority queue: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC); - - c_forrange (i, int, M) { - printf("%g ", *cpque_f_top(&pq)); - cpque_f_pop(&pq); - } - - start = clock(); - c_forrange (i, int, M, N) - cpque_f_pop(&pq); - printf("\n\npopped PQ: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC); - - start = clock(); - c_forrange (i, int, N) - cpque_f_push(&pq, (float) crand_nextf(&rng)*100000); - printf("pushed PQ: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC); - - c_forrange (i, int, M) { - printf("%g ", *cpque_f_top(&pq)); - cpque_f_pop(&pq); - } - puts(""); - - cpque_f_del(&pq); -} diff --git a/examples/rngtest.c b/examples/rngtest.c deleted file mode 100644 index f52099c7..00000000 --- a/examples/rngtest.c +++ /dev/null @@ -1,40 +0,0 @@ -#include -#include -#include -#ifdef __cplusplus -#include -#endif - - -#define NN 1000000000 - -int main(void) -{ - clock_t diff, before; - uint64_t v; - - crand_t rng = crand_init(time(NULL)); - crand_uniform_t idist = crand_uniform_init(10, 20); - crand_uniformf_t fdist = crand_uniformf_init(10, 20); - - before = clock(); - v = 0; - c_forrange (NN) { - v += crand_next(&rng); - } - diff = clock() - before; - printf("stc64_rand: %.02f, %zu\n", (float) diff / CLOCKS_PER_SEC, v); - - before = clock(); - v = 0; - c_forrange (NN) { - v += crand_uniform(&rng, &idist); - } - diff = clock() - before; - printf("stc64_uniform: %.02f, %zu\n\n", (float) diff / CLOCKS_PER_SEC, v); - - c_forrange (30) printf("%02zd ", crand_uniform(&rng, &idist)); - puts(""); - c_forrange (8) printf("%f ", crand_uniformf(&rng, &fdist)); - puts(""); -} \ No newline at end of file -- cgit v1.2.3