From 8efecc5d6b8d4dcd6a7bdf9540a11355b4631782 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 29 Aug 2020 22:46:05 +0200 Subject: Updated crandom.h API! update to benchmark.c . Optimized cmap iter. --- examples/benchmark.c | 64 +++++++++++++++++++++++++++++++++++++++++----------- examples/birthday.c | 10 ++++---- examples/heap.c | 8 +++---- examples/list.c | 6 ++--- examples/priority.c | 8 +++---- examples/rngtest.c | 32 +++++++++++++------------- 6 files changed, 83 insertions(+), 45 deletions(-) (limited to 'examples') diff --git a/examples/benchmark.c b/examples/benchmark.c index 0b9c4f10..d4e1e82c 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -29,9 +29,9 @@ KHASH_MAP_INIT_INT64(ii, int64_t) size_t seed; static const float max_load_factor = 0.77f; -crandom_eng64_t rng; -#define SEED(s) rng = crandom_eng64_init(seed) -#define RAND(N) (crandom_i64(&rng) & ((1 << N) - 1)) +crand_rng64_t rng; +#define SEED(s) rng = crand_rng64_init(seed) +#define RAND(N) (crand_i64(&rng) & ((1 << N) - 1)) #define CMAP_SETUP(tt, Key, Value) cmap_##tt map = cmap_init \ @@ -41,6 +41,8 @@ crandom_eng64_t rng; #define CMAP_EMPLACE(tt, key, val) cmap_try_emplace(tt, &map, key, val) #define CMAP_ERASE(tt, key) cmap_##tt##_erase(&map, key) #define CMAP_FIND(tt, key) (cmap_##tt##_find(map, key) != NULL) +#define CMAP_FOR(tt, i) c_foreach (i, cmap_##tt, map) +#define CMAP_ITEM(tt, i) i.item->value #define CMAP_SIZE(tt) cmap_size(map) #define CMAP_BUCKETS(tt) cmap_bucket_count(map) #define CMAP_CLEAR(tt) cmap_##tt##_clear(&map) @@ -62,6 +64,8 @@ crandom_eng64_t rng; #define UMAP_EMPLACE(tt, key, val) map.emplace(key, val) #define UMAP_FIND(tt, key) (map.find(key) != map.end()) #define UMAP_ERASE(tt, key) map.erase(key) +#define UMAP_FOR(tt, i) for (auto i: map) +#define UMAP_ITEM(tt, i) i.second #define UMAP_SIZE(tt) map.size() #define UMAP_BUCKETS(tt) map.bucket_count() #define UMAP_CLEAR(tt) map.clear() @@ -73,6 +77,8 @@ crandom_eng64_t rng; #define BMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define BMAP_FIND(tt, key) UMAP_FIND(tt, key) #define BMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define BMAP_FOR(tt, i) UMAP_FOR(tt, i) +#define BMAP_ITEM(tt, i) UMAP_ITEM(tt, i) #define BMAP_SIZE(tt) UMAP_SIZE(tt) #define BMAP_BUCKETS(tt) UMAP_BUCKETS(tt) #define BMAP_CLEAR(tt) UMAP_CLEAR(tt) @@ -84,6 +90,8 @@ crandom_eng64_t rng; #define FMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define FMAP_FIND(tt, key) UMAP_FIND(tt, key) #define FMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define FMAP_FOR(tt, i) UMAP_FOR(tt, i) +#define FMAP_ITEM(tt, i) UMAP_ITEM(tt, i) #define FMAP_SIZE(tt) UMAP_SIZE(tt) #define FMAP_BUCKETS(tt) UMAP_BUCKETS(tt) #define FMAP_CLEAR(tt) UMAP_CLEAR(tt) @@ -95,6 +103,8 @@ crandom_eng64_t rng; #define HMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define HMAP_FIND(tt, key) UMAP_FIND(tt, key) #define HMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define HMAP_FOR(tt, i) UMAP_FOR(tt, i) +#define HMAP_ITEM(tt, i) UMAP_ITEM(tt, i) #define HMAP_SIZE(tt) UMAP_SIZE(tt) #define HMAP_BUCKETS(tt) UMAP_BUCKETS(tt) #define HMAP_CLEAR(tt) UMAP_CLEAR(tt) @@ -106,6 +116,8 @@ crandom_eng64_t rng; #define RMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define RMAP_FIND(tt, key) UMAP_FIND(tt, key) #define RMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define RMAP_FOR(tt, i) UMAP_FOR(tt, i) +#define RMAP_ITEM(tt, i) UMAP_ITEM(tt, i) #define RMAP_SIZE(tt) UMAP_SIZE(tt) #define RMAP_BUCKETS(tt) map.mask() #define RMAP_CLEAR(tt) UMAP_CLEAR(tt) @@ -117,15 +129,21 @@ crandom_eng64_t rng; #define SMAP_EMPLACE(tt, key, val) UMAP_EMPLACE(tt, key, val) #define SMAP_FIND(tt, key) UMAP_FIND(tt, key) #define SMAP_ERASE(tt, key) UMAP_ERASE(tt, key) +#define SMAP_FOR(tt, i) UMAP_FOR(tt, i) +#define SMAP_ITEM(tt, i) UMAP_ITEM(tt, i) #define SMAP_SIZE(tt) UMAP_SIZE(tt) #define SMAP_BUCKETS(tt) UMAP_BUCKETS(tt) #define SMAP_CLEAR(tt) UMAP_CLEAR(tt) #define SMAP_DTOR(tt) UMAP_DTOR(tt) -const size_t N1 = 10000000 * 5; -const size_t N2 = 10000000 * 5; -const size_t N3 = 10000000 * 5; -#define RR 20 +enum { + FAC = 5, + N1 = 10000000 * FAC, + N2 = 10000000 * FAC, + N3 = 10000000 * FAC, + N4 = 10000000 * FAC, + RR = 24 +}; int rr = RR; @@ -177,11 +195,28 @@ int rr = RR; M##_CLEAR(tt); \ } +#define MAP_TEST4(M, tt) \ +{ \ + M##_SETUP(tt, int64_t, int64_t); \ + size_t sum = 0; \ + SEED(seed); \ + for (size_t i = 0; i < N4; ++i) \ + M##_PUT(tt, RAND(rr), i); \ + clock_t difference, before = clock(); \ + for (int k=0; k<5; k++) M##_FOR (tt, i) \ + sum += M##_ITEM(tt, i); \ + difference = clock() - before; \ + printf(#M ": size: %zu, buckets: %8zu, time: %5.02f, sum %zu\n", \ + (size_t) M##_SIZE(tt), (size_t) M##_BUCKETS(tt), (float) difference / CLOCKS_PER_SEC, sum); \ + M##_CLEAR(tt); \ +} + + #ifndef __cplusplus -#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) +#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) /*MAP_TEST##n(KMAP, ii)*/ #else -#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 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) #endif int main(int argc, char* argv[]) @@ -189,12 +224,15 @@ 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: %zu repeats of Insert random key + try to remove a random key:\n", N1); + printf("\nUnordered maps: %d repeats of Insert random key + try to remove a random key:\n", N1); RUN_TEST(1) - printf("\nUnordered maps: Insert %zu index keys, then remove them in same order:\n", N2); + printf("\nUnordered maps: Insert %d index keys, then remove them in same order:\n", N2); RUN_TEST(2) - printf("\nUnordered maps: Insert %zu random keys, then remove them in same order:\n", N3); + 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, then remove them in same order:\n", N4); + RUN_TEST(4) } diff --git a/examples/birthday.c b/examples/birthday.c index 22ecdfae..4f6e7a8b 100644 --- a/examples/birthday.c +++ b/examples/birthday.c @@ -15,12 +15,12 @@ const static uint64_t mask = (1ull << 52) - 1; void repeats(void) { - crandom_eng64_t rng = crandom_eng64_init(seed); + crand_rng64_t rng = crand_rng64_init(seed); cmap_ic m = cmap_init; cmap_ic_reserve(&m, N); clock_t now = clock(); for (size_t i = 0; i < N; ++i) { - uint64_t k = crandom_i64(&rng) & mask; + uint64_t k = crand_i64(&rng) & mask; int v = ++cmap_ic_insert(&m, k, 0)->value; if (v > 1) printf("%zu: %llx - %d\n", i, k, v); } @@ -34,13 +34,13 @@ declare_cvec(x, uint64_t); void distribution(void) { - crandom_eng32_t rng = crandom_eng32_init(seed); // time(NULL), time(NULL)); + crand_rng32_t rng = crand_rng32_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(); - crandom_distrib_i32_t dist = crandom_uniform_i32_init(0, M); + crand_uniform_i32_t dist = crand_uniform_i32_init(rng, 0, M); for (size_t i = 0; i < N; ++i) { - ++cmap_x_insert(&map, crandom_uniform_i32(&rng, dist), 0)->value; + ++cmap_x_insert(&map, crand_uniform_i32(&dist), 0)->value; } float diff = (float) (clock() - now) / CLOCKS_PER_SEC; diff --git a/examples/heap.c b/examples/heap.c index e966451b..c6624819 100644 --- a/examples/heap.c +++ b/examples/heap.c @@ -9,12 +9,12 @@ declare_cvec_pqueue(f, >); int main() { uint32_t seed = time(NULL); - crandom_eng32_t pcg = crandom_eng32_init(seed); + crand_rng32_t pcg = crand_rng32_init(seed); int N = 30000000, M = 100; cvec_f vec = cvec_init; clock_t start = clock(); for (int i=0; ivalue); else break; diff --git a/examples/priority.c b/examples/priority.c index 2d5c23bd..598f448a 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -9,19 +9,19 @@ declare_cvec(i, int64_t); declare_cvec_pqueue(i, >); // min-heap (increasing values) int main() { - crandom_eng32_t pcg = crandom_eng32_init(time(NULL)); - crandom_distrib_i32_t dist = crandom_uniform_i32_init(0, 100000000); + crand_rng32_t pcg = crand_rng32_init(time(NULL)); + crand_uniform_i32_t dist = crand_uniform_i32_init(pcg, 0, 100000000); cvec_i heap = cvec_init; // Push ten million random numbers to priority queue for (int i=0; i<10000000; ++i) - cvec_i_pqueue_push(&heap, crandom_uniform_i32(&pcg, dist)); + cvec_i_pqueue_push(&heap, crand_uniform_i32(&dist)); // push some negative numbers too. c_push(&heap, cvec_i_pqueue, c_items(-231, -32, -873, -4, -343)); for (int i=0; i<10000000; ++i) - cvec_i_pqueue_push(&heap, crandom_uniform_i32(&pcg, dist)); + cvec_i_pqueue_push(&heap, crand_uniform_i32(&dist)); // Extract the hundred smallest. diff --git a/examples/rngtest.c b/examples/rngtest.c index 657e002d..6aa783e2 100644 --- a/examples/rngtest.c +++ b/examples/rngtest.c @@ -13,22 +13,22 @@ int main(void) clock_t difference, before; uint64_t v; - crandom_eng64_t sfc = crandom_eng64_init(time(NULL)); - crandom_distrib_i32_t i32dist = crandom_uniform_i32_init(10, 20); - crandom_distrib_f32_t f32dist = crandom_uniform_f32_init(10, 20); + crand_rng64_t stc = crand_rng64_init(time(NULL)); + crand_uniform_i64_t idist = crand_uniform_i64_init(stc, 10, 20); + crand_uniform_f64_t fdist = crand_uniform_f64_init(stc, 10, 20); - crandom_distrib_i64_t idist = crandom_uniform_i64_init(10, 20); - crandom_distrib_f64_t fdist = crandom_uniform_f64_init(10, 20); - - for (int i=0; i<30; ++i) printf("%02zd ", crandom_uniform_i64(&sfc, idist)); + for (int i=0; i<30; ++i) printf("%02zd ", crand_uniform_i64(&idist)); puts(""); - crandom_eng32_t pcg = crandom_eng32_init(time(NULL)); + crand_rng32_t pcg = crand_rng32_init(time(NULL)); + crand_uniform_i32_t i32dist = crand_uniform_i32_init(pcg, 10, 20); + crand_uniform_f32_t f32dist = crand_uniform_f32_init(pcg, 10, 20); + before = clock(); \ v = 0; for (size_t i=0; i