From b9485b4410d2cb3d81766c487dd0edd0e92868d4 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 9 Feb 2021 15:26:21 +0100 Subject: added more benchmark code. --- benchmarks/cdeq_benchmark.cpp | 173 +++++++++++---------- benchmarks/cmap_benchmark.cpp | 336 +++++++++++++---------------------------- benchmarks/cmap_benchmark3.cpp | 252 +++++++++++++++++++++++++++++++ benchmarks/cvec_benchmark.cpp | 108 +++++++++++++ stc/cdeq.h | 13 +- stc/cvec.h | 8 +- 6 files changed, 573 insertions(+), 317 deletions(-) create mode 100644 benchmarks/cmap_benchmark3.cpp create mode 100644 benchmarks/cvec_benchmark.cpp diff --git a/benchmarks/cdeq_benchmark.cpp b/benchmarks/cdeq_benchmark.cpp index 6211afa5..2f49e1b6 100644 --- a/benchmarks/cdeq_benchmark.cpp +++ b/benchmarks/cdeq_benchmark.cpp @@ -1,98 +1,113 @@ #include #include -#include -#include -#include #include +#include + +#ifdef __cplusplus +#include +#endif -static float secs(time_t t1, time_t t2) { return (float)(t2 - t1) / CLOCKS_PER_SEC; } +enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; +typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; +typedef struct { const char* name; Range test[N_TESTS]; } Sample; +enum {SAMPLES = 3, N = 100000000}; +uint64_t seed = 1, mask1 = 0xfffffff; -enum {N = 1000000000, M = 12345, P = 5000, R = 2000}; -using_cdeq(i, int); +static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } -void test1() { - clock_t t1 = clock(), t2, t3; - stc64_t rng = stc64_init(0); +using_cdeq(x, size_t); + +#ifdef __cplusplus +Sample test_std_deque() { + typedef std::deque container; + Sample s = {"std-deque"}; { - std::deque deq; - for (size_t i = 1; i < N; i++) { - deq.push_front(stc64_rand(&rng)); - if (i % M == 0) - for (int j = 5; j < M; j++) - deq.pop_back(); - } - size_t n = deq.size(); - t2 = clock(); - printf("std pushf/popb : %5.2f sec, sz=%zu\n", (float)(t2 - t1) / CLOCKS_PER_SEC, n); - fflush(stdout); - size_t sum = 0; - c_forrange (R) c_forrange (i, n) - sum += deq[i]; - t3 = clock(); - printf("std access : %5.2f sec, sum=%zu\n", (float)(t3 - t2) / CLOCKS_PER_SEC, sum); + s.test[INSERT].t1 = clock(); + container con; + stc64_srandom(seed); + c_forrange (N/2) con.push_front(stc64_random() & mask1); + c_forrange (N/2) { con.push_back(stc64_random() & mask1); con.pop_front(); } + c_forrange (N/2) con.push_back(stc64_random() & mask1); + s.test[INSERT].t2 = clock(); + s.test[INSERT].sum = con.size(); + s.test[ERASE].t1 = clock(); + c_forrange (N/2) { con.pop_front(); con.pop_back(); } + s.test[ERASE].t2 = clock(); + s.test[ERASE].sum = con.size(); }{ - std::deque deq; - for (size_t i = 1; i < N/10; i++) { - if (i & 1) deq.push_front(stc64_rand(&rng)); - else deq.push_back(stc64_rand(&rng)); - } - t2 = clock(); - printf("std pushf/pushb : %5.2f sec\n", (float)(t2 - t3) / CLOCKS_PER_SEC); - }{ - std::deque deq; - for (size_t i = 1; i < N/2; i++) { - deq.push_back(stc64_rand(&rng)); - } - t3 = clock(); - printf("std pushb : %5.2f sec\n", (float)(t3 - t2) / CLOCKS_PER_SEC); - } + container con; + stc64_srandom(seed); + c_forrange (N) con.push_back(stc64_random() & mask1); + s.test[ITER].t1 = clock(); + size_t sum = 0; + c_forrange (i, N) sum += con[i]; + s.test[ITER].t2 = clock(); + s.test[ITER].sum = sum; + s.test[DESTRUCT].t1 = clock(); + } + s.test[DESTRUCT].t2 = clock(); + s.test[DESTRUCT].sum = 0; + return s; } +#endif -void test2() { - clock_t t1 = clock(), t2, t3; - stc64_t rng = stc64_init(0); +Sample test_stc_deque() { + typedef cdeq_x container; + Sample s = {"stc-deque"}; { - cdeq_i deq = cdeq_i_init(); - for (size_t i = 1; i < N; i++) { - cdeq_i_push_front(&deq, stc64_rand(&rng)); - if (i % M == 0) - for (int j = 5; j < M; j++) - cdeq_i_pop_back(&deq); - } - size_t n = cdeq_i_size(deq); - t2 = clock(); - printf("stc pushf/popb : %5.2f sec, sz=%zu\n", (float)(t2 - t1) / CLOCKS_PER_SEC, n); + s.test[INSERT].t1 = clock(); + container con = cdeq_x_init(); + cdeq_x_reserve(&con, N); + stc64_srandom(seed); + c_forrange (N/2) cdeq_x_push_front(&con, stc64_random() & mask1); + c_forrange (N/2) { cdeq_x_push_back(&con, stc64_random() & mask1); cdeq_x_pop_front(&con); } + c_forrange (N/2) cdeq_x_push_back(&con, stc64_random() & mask1); + s.test[INSERT].t2 = clock(); + s.test[INSERT].sum = cdeq_x_size(con); + s.test[ERASE].t1 = clock(); + c_forrange (N/2) { cdeq_x_pop_front(&con); cdeq_x_pop_back(&con); } + s.test[ERASE].t2 = clock(); + s.test[ERASE].sum = cdeq_x_size(con); + cdeq_x_del(&con); + }{ + stc64_srandom(seed); + container con = cdeq_x_init(); + c_forrange (N) cdeq_x_push_back(&con, stc64_random() & mask1); + s.test[ITER].t1 = clock(); size_t sum = 0; - c_forrange (R) c_forrange (i, n) - sum += deq.data[i]; - t3 = clock(); - printf("stc access : %5.2f sec, sum=%zu\n", (float)(t3 - t2) / CLOCKS_PER_SEC, sum); - cdeq_i_del(&deq); - }{ - cdeq_i deq = cdeq_i_init(); - for (size_t i = 1; i < N/10; i++) { - if (i & 1) cdeq_i_push_front(&deq, stc64_rand(&rng)); - else cdeq_i_push_back(&deq, stc64_rand(&rng)); - } - t2 = clock(); - printf("stc pushf/pushb : %5.2f sec\n", (float)(t2 - t3) / CLOCKS_PER_SEC); - cdeq_i_del(&deq); - }{ - cdeq_i deq = cdeq_i_init(); - for (size_t i = 1; i < N/2; i++) { - cdeq_i_push_back(&deq, stc64_rand(&rng)); - } - t3 = clock(); - printf("stc pushb : %5.2f sec\n", (float)(t3 - t2) / CLOCKS_PER_SEC); - cdeq_i_del(&deq); - } + c_forrange (i, N) sum += *cdeq_x_at(&con, i); + s.test[ITER].t2 = clock(); + s.test[ITER].sum = sum; + s.test[DESTRUCT].t1 = clock(); + cdeq_x_del(&con); + } + s.test[DESTRUCT].t2 = clock(); + s.test[DESTRUCT].sum = 0; + return s; } int main() { - test1(); - puts(""); - test2(); + Sample std_s[SAMPLES + 1], stc_s[SAMPLES + 1]; + c_forrange (i, int, SAMPLES) { + printf("deque benchmark sample %d\n", i); + std_s[i] = test_std_deque(); + stc_s[i] = test_stc_deque(); + if (i > 0) c_forrange (j, int, N_TESTS) { + if (secs(std_s[i].test[j]) < secs(std_s[0].test[j])) std_s[0].test[j] = std_s[i].test[j]; + if (secs(stc_s[i].test[j]) < secs(stc_s[0].test[j])) stc_s[0].test[j] = stc_s[i].test[j]; + if (stc_s[i].test[j].sum != stc_s[0].test[j].sum) printf("Error in sum: test %d, sample %d\n", i, j); + } + } + float std_sum = 0, stc_sum = 0; + c_forrange (j, N_TESTS) { std_sum += secs(std_s[0].test[j]); stc_sum += secs(stc_s[0].test[j]); } + printf("Test-name, Insert, Erase, Find, Iter, Destruct, Total, Ratio\n"); + + printf("%s", std_s[0].name); c_forrange (j, N_TESTS) printf(", %.3f", secs(std_s[0].test[j])); + printf(", %.3f, 1.000\n", std_sum); + + printf("%s", stc_s[0].name); c_forrange (j, N_TESTS) printf(", %.3f", secs(stc_s[0].test[j])); + printf(", %.3f, %.3f\n", stc_sum, std_sum/stc_sum); } diff --git a/benchmarks/cmap_benchmark.cpp b/benchmarks/cmap_benchmark.cpp index 1f5c6fa1..c81561e3 100644 --- a/benchmarks/cmap_benchmark.cpp +++ b/benchmarks/cmap_benchmark.cpp @@ -1,252 +1,126 @@ #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 +enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; +typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; +typedef struct { const char* name; Range test[N_TESTS]; } Sample; +enum {SAMPLES = 3, N = 10000000}; -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_equals, fibonacci_hash); // c_default_hash); -KHASH_MAP_INIT_INT64(ii, int64_t) - - -size_t seed; -static const float max_load_factor = 0.77f; - -stc64_t rng; -#define SEED(s) rng = stc64_init(seed) -#define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1)) - - -#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \ - ; cmap_##X##_set_load_factors(&map, 0.0, max_load_factor) -#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).first->second -#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_##X##_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, 0) : 0, map->vals[ki]) -#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).first).second -#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 = 3, - N1 = 10000000 * FAC, - N2 = 10000000 * FAC, - N3 = 10000000 * FAC, - N4 = 10000000 * FAC, - RR = 24 -}; -int rr = RR; +uint64_t seed = 1, mask1 = 0xffffffff; +static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } -#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##_EMPLACE(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); \ +static inline uint32_t hash64(const void* data, size_t len) { + uint64_t x = *(const uint64_t *)data * 11400714819323198485ull; + return x ^ (x >> 24); } +using_cmap(x, size_t, size_t, c_default_equals, c_default_hash32); -#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); \ +#ifdef __cplusplus +Sample test_std_map() { + typedef std::unordered_map container; + Sample s = {"std-unordered_map"}; + { + stc64_srandom(seed); + s.test[INSERT].t1 = clock(); + container con; + c_forrange (i, N) con.emplace(stc64_random() & mask1, i); + s.test[INSERT].t2 = clock(); + s.test[INSERT].sum = con.size(); + stc64_srandom(seed); + s.test[ERASE].t1 = clock(); + c_forrange (N) con.erase(stc64_random() & mask1); + s.test[ERASE].t2 = clock(); + s.test[ERASE].sum = con.size(); + }{ + container con; + stc64_srandom(seed); + c_forrange (i, N) con.emplace(stc64_random() & mask1, i); + stc64_srandom(seed); + s.test[FIND].t1 = clock(); + size_t sum = 0; + c_forrange (N) sum += con.find(stc64_random() & mask1)->second; + s.test[FIND].t2 = clock(); + s.test[FIND].sum = sum; + s.test[ITER].t1 = clock(); + sum = 0; + for (auto i: con) sum += i.second; + s.test[ITER].t2 = clock(); + s.test[ITER].sum = sum; + s.test[DESTRUCT].t1 = clock(); + } + s.test[DESTRUCT].t2 = clock(); + s.test[DESTRUCT].sum = 0; + return s; } +#endif -#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); \ +Sample test_stc_map() { + typedef cmap_x container; + Sample s = {"stc-unordered_map"}; + { + stc64_srandom(seed); + s.test[INSERT].t1 = clock(); + container con = cmap_x_init(); + c_forrange (i, N) cmap_x_emplace(&con, stc64_random() & mask1, i); + s.test[INSERT].t2 = clock(); + s.test[INSERT].sum = cmap_x_size(con); + stc64_srandom(seed); + s.test[ERASE].t1 = clock(); + c_forrange (N) cmap_x_erase(&con, stc64_random() & mask1); + s.test[ERASE].t2 = clock(); + s.test[ERASE].sum = cmap_x_size(con); + cmap_x_del(&con); + }{ + container con = cmap_x_init(); + stc64_srandom(seed); + c_forrange (i, N) cmap_x_emplace(&con, stc64_random() & mask1, i); + stc64_srandom(seed); + s.test[FIND].t1 = clock(); + size_t sum = 0; + c_forrange (N) sum += cmap_x_find(&con, stc64_random() & mask1).ref->second; + s.test[FIND].t2 = clock(); + s.test[FIND].sum = sum; + s.test[ITER].t1 = clock(); + sum = 0; + c_foreach (i, cmap_x, con) sum += i.ref->second; + s.test[ITER].t2 = clock(); + s.test[ITER].sum = sum; + s.test[DESTRUCT].t1 = clock(); + cmap_x_del(&con); + } + s.test[DESTRUCT].t2 = clock(); + s.test[DESTRUCT].sum = 0; + return s; } -#define MAP_TEST5(M, X) \ -{ \ - M##_SETUP(X, int64_t, int64_t); \ - uint64_t checksum = 0; \ - SEED(seed); \ - clock_t difference, before = clock(); \ - for (size_t i = 0; i < N1; ++i) { \ - checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ - } \ - difference = clock() - before; \ - printf(#M ": time: %5.02f, sum: %zu, size: %zu, buckets: %8zu\n", \ - (float) difference / CLOCKS_PER_SEC, checksum, (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[]) +int main() { - rr = argc == 2 ? atoi(argv[1]) : RR; - seed = time(NULL); - - printf("\nUnordered maps: Insert %d random keys:\n", N3); - RUN_TEST(5) - - 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) + Sample std_s[SAMPLES + 1], stc_s[SAMPLES + 1]; + c_forrange (i, int, SAMPLES) { + printf("unordered_map benchmark sample %d\n", i); + std_s[i] = test_std_map(); + stc_s[i] = test_stc_map(); + if (i > 0) c_forrange (j, int, N_TESTS) { + if (secs(std_s[i].test[j]) < secs(std_s[0].test[j])) std_s[0].test[j] = std_s[i].test[j]; + if (secs(stc_s[i].test[j]) < secs(stc_s[0].test[j])) stc_s[0].test[j] = stc_s[i].test[j]; + if (stc_s[i].test[j].sum != stc_s[0].test[j].sum) printf("Error in sum: test %d, sample %d\n", i, j); + } + } + float std_sum = 0, stc_sum = 0; + c_forrange (j, N_TESTS) { std_sum += secs(std_s[0].test[j]); stc_sum += secs(stc_s[0].test[j]); } + printf("Test-name, Insert, Erase, Find, Iter, Destruct, Total, Ratio\n"); + + printf("%s", std_s[0].name); c_forrange (j, N_TESTS) printf(", %.3f", secs(std_s[0].test[j])); + printf(", %.3f, 1.000\n", std_sum); + + printf("%s", stc_s[0].name); c_forrange (j, N_TESTS) printf(", %.3f", secs(stc_s[0].test[j])); + printf(", %.3f, %.3f\n", stc_sum, std_sum/stc_sum); } diff --git a/benchmarks/cmap_benchmark3.cpp b/benchmarks/cmap_benchmark3.cpp new file mode 100644 index 00000000..1f5c6fa1 --- /dev/null +++ b/benchmarks/cmap_benchmark3.cpp @@ -0,0 +1,252 @@ +#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_equals, fibonacci_hash); // c_default_hash); +KHASH_MAP_INIT_INT64(ii, int64_t) + + +size_t seed; +static const float max_load_factor = 0.77f; + +stc64_t rng; +#define SEED(s) rng = stc64_init(seed) +#define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1)) + + +#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \ + ; cmap_##X##_set_load_factors(&map, 0.0, max_load_factor) +#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).first->second +#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_##X##_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, 0) : 0, map->vals[ki]) +#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).first).second +#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 = 3, + 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##_EMPLACE(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); \ +} + +#define MAP_TEST5(M, X) \ +{ \ + M##_SETUP(X, int64_t, int64_t); \ + uint64_t checksum = 0; \ + SEED(seed); \ + clock_t difference, before = clock(); \ + for (size_t i = 0; i < N1; ++i) { \ + checksum += ++ M##_EMPLACE(X, RAND(rr), i); \ + } \ + difference = clock() - before; \ + printf(#M ": time: %5.02f, sum: %zu, size: %zu, buckets: %8zu\n", \ + (float) difference / CLOCKS_PER_SEC, checksum, (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("\nUnordered maps: Insert %d random keys:\n", N3); + RUN_TEST(5) + + 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/cvec_benchmark.cpp b/benchmarks/cvec_benchmark.cpp new file mode 100644 index 00000000..24931273 --- /dev/null +++ b/benchmarks/cvec_benchmark.cpp @@ -0,0 +1,108 @@ +#include +#include +#include +#include + +#ifdef __cplusplus +#include +#endif + +enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; +typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; +typedef struct { const char* name; Range test[N_TESTS]; } Sample; +enum {SAMPLES = 3, N = 100000000}; + +uint64_t seed = 1, mask1 = 0xfffffff; + +static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } + +using_cvec(x, size_t); + +#ifdef __cplusplus +Sample test_std_vector() { + typedef std::vector container; + Sample s = {"std-vector"}; + { + s.test[INSERT].t1 = clock(); + container con; + stc64_srandom(seed); + c_forrange (N) con.push_back(stc64_random() & mask1); + s.test[INSERT].t2 = clock(); + s.test[INSERT].sum = con.size(); + s.test[ERASE].t1 = clock(); + c_forrange (N) con.pop_back(); + s.test[ERASE].t2 = clock(); + s.test[ERASE].sum = con.size(); + }{ + container con; + stc64_srandom(seed); + c_forrange (N) con.push_back(stc64_random() & mask1); + s.test[ITER].t1 = clock(); + size_t sum = 0; + c_forrange (i, N) sum += con[i]; + s.test[ITER].t2 = clock(); + s.test[ITER].sum = sum; + s.test[DESTRUCT].t1 = clock(); + } + s.test[DESTRUCT].t2 = clock(); + s.test[DESTRUCT].sum = 0; + return s; +} +#endif + + +Sample test_stc_vector() { + typedef cvec_x container; + Sample s = {"stc-vector"}; + { + s.test[INSERT].t1 = clock(); + container con = cvec_x_init(); + stc64_srandom(seed); + c_forrange (N) cvec_x_push_back(&con, stc64_random() & mask1); + s.test[INSERT].t2 = clock(); + s.test[INSERT].sum = cvec_x_size(con); + s.test[ERASE].t1 = clock(); + c_forrange (N) { cvec_x_pop_back(&con); } + s.test[ERASE].t2 = clock(); + s.test[ERASE].sum = cvec_x_size(con); + cvec_x_del(&con); + }{ + stc64_srandom(seed); + container con = cvec_x_init(); + c_forrange (N) cvec_x_push_back(&con, stc64_random() & mask1); + s.test[ITER].t1 = clock(); + size_t sum = 0; + c_forrange (i, N) sum += *cvec_x_at(&con, i); + s.test[ITER].t2 = clock(); + s.test[ITER].sum = sum; + s.test[DESTRUCT].t1 = clock(); + cvec_x_del(&con); + } + s.test[DESTRUCT].t2 = clock(); + s.test[DESTRUCT].sum = 0; + return s; +} + +int main() +{ + Sample std_s[SAMPLES + 1] = {0}, stc_s[SAMPLES + 1] = {0}; + c_forrange (i, int, SAMPLES) { + printf("vector benchmark sample %d\n", i); + std_s[i] = test_std_vector(); + stc_s[i] = test_stc_vector(); + if (i > 0) c_forrange (j, int, N_TESTS) { + if (secs(std_s[i].test[j]) < secs(std_s[0].test[j])) std_s[0].test[j] = std_s[i].test[j]; + if (secs(stc_s[i].test[j]) < secs(stc_s[0].test[j])) stc_s[0].test[j] = stc_s[i].test[j]; + if (stc_s[i].test[j].sum != stc_s[0].test[j].sum) printf("Error in sum: test %d, sample %d\n", i, j); + } + } + float std_sum = 0, stc_sum = 0; + c_forrange (j, N_TESTS) { std_sum += secs(std_s[0].test[j]); stc_sum += secs(stc_s[0].test[j]); } + printf("Test-name, Insert, Erase, Find, Iter, Destruct, Total, Ratio\n"); + + printf("%s", std_s[0].name); c_forrange (j, N_TESTS) printf(", %.3f", secs(std_s[0].test[j])); + printf(", %.3f, 1.000\n", std_sum); + + printf("%s", stc_s[0].name); c_forrange (j, N_TESTS) printf(", %.3f", secs(stc_s[0].test[j])); + printf(", %.3f, %.3f\n", stc_sum, std_sum/stc_sum); +} diff --git a/stc/cdeq.h b/stc/cdeq.h index 8cce8188..7fddfcd2 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -68,9 +68,13 @@ struct cdeq_rep { size_t size, cap; void* base[]; }; STC_API void \ cdeq_##X##_del(cdeq_##X* self); \ STC_API void \ + _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool at_front); \ + STC_API void \ cdeq_##X##_resize(cdeq_##X* self, size_t size, Value fill_val); \ STC_API void \ - _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool at_front); \ + cdeq_##X##_reserve(cdeq_##X* self, size_t n) { \ + _cdeq_##X##_expand(self, (n - _cdeq_rep(self)->size)*2/3, false); \ + } \ STC_INLINE void \ cdeq_##X##_swap(cdeq_##X* a, cdeq_##X* b) {c_swap(cdeq_##X, *a, *b);} \ \ @@ -223,6 +227,7 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;} \ STC_DEF void \ cdeq_##X##_push_n(cdeq_##X *self, const cdeq_##X##_rawvalue_t arr[], size_t n) { \ + if (!n) return; \ _cdeq_##X##_expand(self, n, false); \ cdeq_##X##_value_t* p = self->data + _cdeq_rep(self)->size; \ for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \ @@ -231,10 +236,10 @@ static inline double _maxf(double x, double y) {return x > y ? x : y;} \ STC_DEF void \ cdeq_##X##_clear(cdeq_##X* self) { \ - cdeq_##X##_value_t* p = self->data; if (p) { \ - for (cdeq_##X##_value_t* q = p + _cdeq_rep(self)->size; p != q; ++p) \ + struct cdeq_rep* rep = _cdeq_rep(self); if (rep->cap) { \ + for (cdeq_##X##_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \ valueDestroy(p); \ - _cdeq_rep(self)->size = 0; \ + rep->size = 0; \ } \ } \ STC_DEF void \ diff --git a/stc/cvec.h b/stc/cvec.h index 77ed6c09..cf0bb7f9 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -205,6 +205,7 @@ static struct cvec_rep _cvec_inits = {0, 0}; \ STC_DEF void \ cvec_##X##_push_n(cvec_##X *self, const cvec_##X##_rawvalue_t arr[], size_t n) { \ + if (!n) return; \ cvec_##X##_reserve(self, _cvec_rep(self)->size + n); \ cvec_##X##_value_t* p = self->data + _cvec_rep(self)->size; \ for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \ @@ -213,9 +214,10 @@ static struct cvec_rep _cvec_inits = {0, 0}; \ STC_DEF void \ cvec_##X##_clear(cvec_##X* self) { \ - cvec_##X##_value_t* p = self->data; if (p) { \ - for (cvec_##X##_value_t* q = p + _cvec_rep(self)->size; p != q; ++p) valueDestroy(p); \ - _cvec_rep(self)->size = 0; \ + struct cvec_rep* rep = _cvec_rep(self); if (rep->cap) { \ + for (cvec_##X##_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \ + valueDestroy(p); \ + rep->size = 0; \ } \ } \ STC_DEF void \ -- cgit v1.2.3