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 --- benchmarks/cmap_benchmark.cpp | 233 ++++++++++++++++++++++++++++++++++++++++ benchmarks/cpque_benchmark.cpp | 48 +++++++++ benchmarks/crand_benchmark.cpp | 155 ++++++++++++++++++++++++++ benchmarks/crand_benchmark2.cpp | 75 +++++++++++++ examples/benchmark.cpp | 233 ---------------------------------------- examples/birthday.c | 46 ++++---- examples/heap.c | 48 --------- examples/rngtest.c | 40 ------- stc/cdeq.h | 2 +- stc/crand.h | 31 ++---- 10 files changed, 544 insertions(+), 367 deletions(-) create mode 100644 benchmarks/cmap_benchmark.cpp create mode 100644 benchmarks/cpque_benchmark.cpp create mode 100644 benchmarks/crand_benchmark.cpp create mode 100644 benchmarks/crand_benchmark2.cpp delete mode 100644 examples/benchmark.cpp delete mode 100644 examples/heap.c delete mode 100644 examples/rngtest.c diff --git a/benchmarks/cmap_benchmark.cpp b/benchmarks/cmap_benchmark.cpp new file mode 100644 index 00000000..a159d24b --- /dev/null +++ b/benchmarks/cmap_benchmark.cpp @@ -0,0 +1,233 @@ +#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/benchmarks/cpque_benchmark.cpp b/benchmarks/cpque_benchmark.cpp new file mode 100644 index 00000000..625bb056 --- /dev/null +++ b/benchmarks/cpque_benchmark.cpp @@ -0,0 +1,48 @@ +#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 = 10000000, M = 10; + + 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/benchmarks/crand_benchmark.cpp b/benchmarks/crand_benchmark.cpp new file mode 100644 index 00000000..78099905 --- /dev/null +++ b/benchmarks/crand_benchmark.cpp @@ -0,0 +1,155 @@ +#include +#include +#include +#include + +static inline uint64_t rotl64(const uint64_t x, const int k) + { return (x << k) | (x >> (64 - k)); } + +static uint64_t splitmix64_x = 87213627321ull; /* The state can be seeded with any value. */ + +uint64_t splitmix64(void) { + uint64_t z = (splitmix64_x += 0x9e3779b97f4a7c15); + z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; + z = (z ^ (z >> 27)) * 0x94d049bb133111eb; + return z ^ (z >> 31); +} + +static void init_state(uint64_t *rng, uint64_t seed) { + splitmix64_x = seed; + for (int i=0; i<4; ++i) rng[i] = splitmix64(); +} + +/* jsf64 */ + +static inline uint64_t jsf64(uint64_t *s) { + uint64_t e = s[0] - rotl64(s[1], 7); + s[0] = s[1] ^ rotl64(s[2], 13); + s[1] = s[2] + rotl64(s[3], 37); + s[2] = s[3] + e; + s[3] = e + s[0]; + return s[3]; +} + +/* xoshiro256** */ + +static inline uint64_t xoshiro256starstar(uint64_t* s) { + const uint64_t result = rotl64(s[1] * 5, 7) * 9; + const uint64_t t = s[1] << 17; + s[2] ^= s[0]; + s[3] ^= s[1]; + s[1] ^= s[2]; + s[0] ^= s[3]; + s[2] ^= t; + s[3] = rotl64(s[3], 45); + return result; +} + + +inline unsigned long long wyhash64(uint64_t* s) { + *s += 0x60bee2bee120fc15ull; + __uint128_t tmp = (__uint128_t) *s * 0xa3b195354a39b70dull; + unsigned long long m1 = (tmp >> 64) ^ tmp; + tmp = (__uint128_t)m1 * 0x1b03738712fad5c9ull; + return (tmp >> 64) ^ tmp; +} + +inline unsigned long long lehmer64(uint64_t* s) { + *(__uint128_t *)s *= 0xda942042e4dd58b5ull; + return *(__uint128_t *)s >> 64; +} + +using namespace std; + +int main(void) +{ + enum {N = 524288000}; + uint64_t* recipient = new uint64_t[N]; + static crand_t rng; + init_state(rng.state, 12345123); + + clock_t beg, end; + for (size_t ti = 0; ti < 4; ti++) { + beg = clock(); + for (size_t i = 0; i < N; i++) + recipient[i] = wyhash64(rng.state); + end = clock(); + cerr << "ROUND " << ti+1 << endl + << "wyhash64:\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << " s" << endl; + cout << "bogus:" << recipient[312] << endl; + beg = clock(); + for (size_t i = 0; i < N; i++) + recipient[i] = crand_next(&rng); + end = clock(); + cerr << "stc crand:\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << " s" << endl; + cout << "bogus:" << recipient[312] << endl; + + beg = clock(); + for (size_t i = 0; i < N; i++) + recipient[i] = xoshiro256starstar(rng.state); + end = clock(); + cerr << "xoshiro256**:\t" + << (float(end - beg) / CLOCKS_PER_SEC) + << " s" << endl; + cout << "bogus:" << recipient[312] << endl; + + beg = clock(); + for (size_t i = 0; i < N; i++) + recipient[i] = lehmer64(rng.state); + end = clock(); + cerr << "lehmer64:\t" + << ((float) end - beg) / CLOCKS_PER_SEC + << " s" << endl; + cout << "bogus:" << recipient[312] << endl; + + + + cout << endl + << "Next we do random number computations only, doing no work." + << endl; + uint64_t s = 0; + beg = clock(); + for (size_t i = 0; i < N; i++) + s += wyhash64(rng.state); + end = clock(); + cerr << "wyhash64:\t" + << ((float) end - beg) / CLOCKS_PER_SEC + << " s" << endl; + cout << "bogus:" << s << endl; + + s = 0; + beg = clock(); + for (size_t i = 0; i < N; i++) + s += crand_next(&rng); + end = clock(); + cerr << "stc crand:\t" + << ((float) end - beg) / CLOCKS_PER_SEC + << " s" << endl; + cout << "bogus:" << s << endl; + + s = 0; + beg = clock(); + for (size_t i = 0; i < N; i++) + s += xoshiro256starstar(rng.state); + end = clock(); + cerr << "xoshiro256**:\t" + << ((float) end - beg) / CLOCKS_PER_SEC + << " s" << endl; + cout << "bogus:" << s << endl; + + beg = clock(); + for (size_t i = 0; i < N; i++) + s += lehmer64(rng.state); + end = clock(); + cerr << "lehmer64:\t" + << ((float) end - beg) / CLOCKS_PER_SEC + << " s" << endl; + cout << "bogus:" << s << endl << endl; + } + delete[] recipient; + return 0; +} diff --git a/benchmarks/crand_benchmark2.cpp b/benchmarks/crand_benchmark2.cpp new file mode 100644 index 00000000..3ae6f8ab --- /dev/null +++ b/benchmarks/crand_benchmark2.cpp @@ -0,0 +1,75 @@ +#include +#include +#include +#include + +void test1(void) +{ + enum {N = 1000000000}; + clock_t diff, before; + uint64_t sum; + + std::random_device device; + std::mt19937 rng(device()); + std::uniform_int_distribution idist(1, 10); + std::uniform_real_distribution fdist(1, 10); + + before = clock(); + sum = 0; + c_forrange (N) { + sum += rng(); + } + diff = clock() - before; + printf("std::random:\t\t%.02f, %zu\n", (float) diff / CLOCKS_PER_SEC, sum); + + before = clock(); + sum = 0; + c_forrange (N) { + sum += idist(rng); + } + diff = clock() - before; + printf("std::uniform:\t\t%.02f, %zu\n\n", (float) diff / CLOCKS_PER_SEC, sum); + + c_forrange (30) printf("%02zd ", idist(rng)); + puts(""); + c_forrange (8) printf("%f ", fdist(rng)); + puts("\n"); +} + +void test2(void) +{ + enum {N = 1000000000}; + clock_t diff, before; + uint64_t sum; + + crand_t rng = crand_init(time(NULL)); + crand_uniform_t idist = crand_uniform_init(1, 10); + crand_uniformf_t fdist = crand_uniformf_init(1, 10); + + before = clock(); + sum = 0; + c_forrange (N) { + sum += crand_next(&rng); + } + diff = clock() - before; + printf("crand_next:\t\t%.02f, %zu\n", (float) diff / CLOCKS_PER_SEC, sum); + + before = clock(); + sum = 0; + c_forrange (N) { + sum += crand_uniform(&rng, &idist); + } + diff = clock() - before; + printf("crand_uniform:\t\t%.02f, %zu\n\n", (float) diff / CLOCKS_PER_SEC, sum); + + c_forrange (30) printf("%02zd ", crand_uniform(&rng, &idist)); + puts(""); + c_forrange (8) printf("%f ", crand_uniformf(&rng, &fdist)); + puts("\n"); +} + +int main() +{ + test1(); + test2(); +} \ No newline at end of file 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 diff --git a/stc/cdeq.h b/stc/cdeq.h index 09537a38..b95bb45f 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -242,7 +242,7 @@ rep[0] = len, rep[1] = cap; \ self->base = (cdeq_##X##_value_t *) (rep + 2); \ self->data = self->base + nfront; \ - return _deq_##X##_expand(self, n, at_front); \ + return _cdeq_##X##_expand(self, n, at_front); \ } \ size_t unused = cap - (len + n); \ size_t pos = at_front ? c_maxf(unused*0.9, (float) unused - nback) + n \ diff --git a/stc/crand.h b/stc/crand.h index 3652851c..ad477ea4 100644 --- a/stc/crand.h +++ b/stc/crand.h @@ -52,7 +52,15 @@ typedef struct {double mean, stddev, next; bool has_next;} crand_normalf_t; /* int random number generator, range [0, 2^64). PRNG copyright Tyge Løvset, NORCE Research, 2020 */ STC_API crand_t crand_init(uint64_t seed); STC_API crand_t crand_with_seq(uint64_t seed, uint64_t seq); -STC_API uint64_t crand_next(crand_t* rng); + +STC_INLINE uint64_t crand_next(crand_t* rng) { + enum {LROT = 24, RSHIFT = 11, LSHIFT = 3}; + uint64_t *s = rng->state; + const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); + s[0] = (b + (b << LSHIFT)) ^ (b >> RSHIFT); + s[1] = ((b << LROT) | (b >> (64 - LROT))) + result; + return result; +} /* double random number in range [low, high). */ STC_INLINE double crand_nextf(crand_t* rng) { @@ -62,7 +70,6 @@ STC_INLINE double crand_nextf(crand_t* rng) { /* integer uniform distributed RNG, range [low, high]. */ STC_API crand_uniform_t crand_uniform_init(int64_t low, int64_t high); -STC_API int64_t crand_uniform(crand_t* rng, crand_uniform_t* dist); /* double uniform distributed RNG, range [low, high). */ STC_INLINE crand_uniformf_t crand_uniformf_init(double low, double high) { @@ -85,9 +92,9 @@ STC_INLINE double crand_uniformf(crand_t* rng, crand_uniformf_t* dist) { : [lhs] "0" (a), [rhs] "rm" (b)) #endif -STC_INLINE int64_t crand_uniform_fast(crand_t* rng, crand_uniform_t* d) { +STC_INLINE int64_t crand_uniform(crand_t* rng, crand_uniform_t* d) { uint64_t lo, hi; - cmul128(crand_next(rng), d->range, &lo, &hi); + do { cmul128(crand_next(rng), d->range, &lo, &hi); } while (lo < d->threshold); return d->lower + hi; } @@ -118,14 +125,6 @@ STC_DEF crand_t crand_with_seq(uint64_t seed, uint64_t seq) { for (int i = 0; i < 8; ++i) crand_next(&rng); return rng; } -STC_DEF uint64_t crand_next(crand_t* rng) { - enum {LROT = 24, RSHIFT = 11, LSHIFT = 3}; - uint64_t *s = rng->state; - const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); - s[0] = (b + (b << LSHIFT)) ^ (b >> RSHIFT); - s[1] = ((b << LROT) | (b >> (64 - LROT))) + result; - return result; -} /* Very fast unbiased uniform int RNG with bounds [low, high] */ STC_DEF crand_uniform_t crand_uniform_init(int64_t low, int64_t high) { @@ -134,14 +133,6 @@ STC_DEF crand_uniform_t crand_uniform_init(int64_t low, int64_t high) { return dist; } -STC_DEF int64_t crand_uniform(crand_t* rng, crand_uniform_t* d) { - uint64_t lo, hi; - do { - cmul128(crand_next(rng), d->range, &lo, &hi); - } while (lo < d->threshold); - return d->lower + hi; -} - /* Marsaglia polar method for gaussian/normal distribution. */ STC_DEF double crand_normalf(crand_t* rng, crand_normalf_t* dist) { double u1, u2, s, m; -- cgit v1.2.3