diff options
| -rw-r--r-- | benchmarks/cdeq_benchmark.cpp | 173 | ||||
| -rw-r--r-- | benchmarks/cmap_benchmark.cpp | 336 | ||||
| -rw-r--r-- | benchmarks/cmap_benchmark3.cpp | 252 | ||||
| -rw-r--r-- | benchmarks/cvec_benchmark.cpp | 108 | ||||
| -rw-r--r-- | stc/cdeq.h | 13 | ||||
| -rw-r--r-- | stc/cvec.h | 8 |
6 files changed, 573 insertions, 317 deletions
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 <stdio.h>
#include <time.h>
-#include <deque>
-#include <vector>
-#include <stc/cdeq.h>
#include <stc/crandom.h>
+#include <stc/cdeq.h>
+
+#ifdef __cplusplus
+#include <deque>
+#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<size_t> container;
+ Sample s = {"std-deque"};
{
- std::deque<int> 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<int> 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<int> 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 <stdio.h>
#include <time.h>
#include <stc/crandom.h>
-#include <stc/cstr.h>
#include <stc/cmap.h>
-#include "others/khash.h"
#ifdef __cplusplus
#include <unordered_map>
-#include "others/bytell_hash_map.hpp"
-#include "others/robin_hood.hpp"
-#include "others/hopscotch_map.h"
-#include "others/sparsepp/spp.h"
-template<typename C> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<size_t, size_t> 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 <stdio.h>
+#include <time.h>
+#include <stc/crandom.h>
+#include <stc/cstr.h>
+#include <stc/cmap.h>
+#include "others/khash.h"
+
+#ifdef __cplusplus
+#include <unordered_map>
+#include "others/bytell_hash_map.hpp"
+#include "others/robin_hood.hpp"
+#include "others/hopscotch_map.h"
+#include "others/sparsepp/spp.h"
+template<typename C> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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<Key, Value> 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 <stdio.h>
+#include <time.h>
+#include <stc/crandom.h>
+#include <stc/cvec.h>
+
+#ifdef __cplusplus
+#include <vector>
+#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<size_t> 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);
+}
@@ -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 \
@@ -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 \
|