From 6427626639f37c142b225c998888dfbe9be1328c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 11 Feb 2021 23:13:19 +0100 Subject: Updated benchmarks, README, two minor API fixes. --- README.md | 14 ++++++++++---- benchmarks/cdeq_benchmark.cpp | 18 +++++++++--------- benchmarks/clist_benchmark.cpp | 6 +++--- benchmarks/cmap_benchmark.cpp | 6 +++--- benchmarks/csmap_benchmark.cpp | 6 +++--- benchmarks/cvec_benchmark.cpp | 6 +++--- benchmarks/pics/benchmark.png | Bin 54112 -> 56088 bytes stc/cdeq.h | 4 ++-- 8 files changed, 33 insertions(+), 27 deletions(-) diff --git a/README.md b/README.md index 4b991356..9eaeafff 100644 --- a/README.md +++ b/README.md @@ -32,18 +32,24 @@ Others: Performance ----------- -The chart uses average times from results of four compilers: Win-Clang++ v11, Mingw64 g++ 9.20, VC19, Linux-clang v10. CPU: Ryzen 7 2700X CPU @4Ghz. +The chart uses average times from results of three compilers: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. The black bars indicates performance variation between various platforms/compilers. ![Benchmark](benchmarks/pics/benchmark.png) -This shows that the STC containers performs either equal or better than the c++ std counterparts (which -have been optimized for decades). **cmap** with default hash key is almost 3 times faster than *std::unordered_map* -on insert and erase, and has orders of magnitude faster iteration and destruction. Additionally, **csmap** is notable +This shows that the STC containers performs either equal or better than the c++ std counterparts. +**cmap** with default hash key is almost 3 times faster than *std::unordered_map* in this test, +on insert and erase, and has orders of magnitude faster iteration and destruction! Additionally, **csmap** is noticable faster on lookup than *std::map*'s typical red-black tree implementation. *csmap* uses an AA-tree (Arne Andersson, 1993), which tends to create a flatter structure (more balanced) than red-black trees. Be aware of though, both *csmap* and *std::map* and are much slower than the unordered map implementations (`n` is half in the benchmarks). +Notes: +- Iteration/summing is repeated 4 times. +- Find is not executed for *forward list*, *deque*, and *vector* because they have no native find. +- **deque** - *insert*: 1/3 push_front(), 1/3 push_back()+push_front(), 1/3 push_back(). +- **map and unordered map** - *insert*: 1/2 random numbers, 1/2 sequential numbers. *erase*: 1/2 keys are in the map, 1/2 keys are random. + Highlights ---------- - **User friendly** - Super easy usage, just include the header and you are good to go. The API and functionality is very close to c++ STL, and is fully listed in the docs. The ***using_***-declaration instantiates the container type to use. You may pass *optional* arguments to it for customization of value- *comparison*, *destruction*, *cloning*, *convertion types*, and more. diff --git a/benchmarks/cdeq_benchmark.cpp b/benchmarks/cdeq_benchmark.cpp index 52e829ff..92a00940 100644 --- a/benchmarks/cdeq_benchmark.cpp +++ b/benchmarks/cdeq_benchmark.cpp @@ -12,7 +12,7 @@ enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; const char* operations[] = {"insert", "erase", "find", "iter", "destruct"}; typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; typedef struct { const char* name; Range test[N_TESTS]; } Sample; -enum {SAMPLES = 2, N = 100000000, S = 0x3ffc}; +enum {SAMPLES = 2, N = 100000000, S = 0x3ffc, R = 4}; uint64_t seed = 1, mask1 = 0xfffffff, mask2 = 0xffff; static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } @@ -27,13 +27,13 @@ Sample test_std_deque() { 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); + c_forrange (N/3) con.push_front(stc64_random() & mask1); + c_forrange (N/3) {con.push_back(stc64_random() & mask1); con.pop_front();} + c_forrange (N/3) 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(); } + c_forrange (con.size()/2) { con.pop_front(); con.pop_back(); } s.test[ERASE].t2 = clock(); s.test[ERASE].sum = con.size(); }{ @@ -49,7 +49,7 @@ Sample test_std_deque() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_forrange (i, N) sum += con[i]; + c_forrange (R) c_forrange (i, N) sum += con[i]; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); @@ -72,12 +72,12 @@ Sample test_stc_deque() { //cdeq_x_reserve(&con, N); stc64_srandom(seed); c_forrange (N/3) cdeq_x_push_front(&con, stc64_random() & mask1); - c_forrange (N/3) { cdeq_x_push_back(&con, stc64_random() & mask1); cdeq_x_pop_front(&con); } + c_forrange (N/3) {cdeq_x_push_back(&con, stc64_random() & mask1); cdeq_x_pop_front(&con);} c_forrange (N/3) 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); } + c_forrange (cdeq_x_size(con)/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); @@ -93,7 +93,7 @@ Sample test_stc_deque() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_forrange (i, N) sum += *cdeq_x_at(&con, i); + c_forrange (R) 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(); diff --git a/benchmarks/clist_benchmark.cpp b/benchmarks/clist_benchmark.cpp index 543cf099..3ed91e6c 100644 --- a/benchmarks/clist_benchmark.cpp +++ b/benchmarks/clist_benchmark.cpp @@ -12,7 +12,7 @@ enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; const char* operations[] = {"insert", "erase", "find", "iter", "destruct"}; typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; typedef struct { const char* name; Range test[N_TESTS]; } Sample; -enum {SAMPLES = 2, N = 50000000, S = 0x3ffc}; +enum {SAMPLES = 2, N = 50000000, S = 0x3ffc, R = 4}; uint64_t seed = 1, mask1 = 0xfffffff, mask2 = 0xffff; static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } @@ -48,7 +48,7 @@ Sample test_std_forward_list() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - for (auto i: con) sum += i; + c_forrange (R) for (auto i: con) sum += i; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); @@ -90,7 +90,7 @@ Sample test_stc_forward_list() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_foreach (i, clist_x, con) sum += *i.ref; + c_forrange (R) c_foreach (i, clist_x, con) sum += *i.ref; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); diff --git a/benchmarks/cmap_benchmark.cpp b/benchmarks/cmap_benchmark.cpp index d9cb1722..56c92264 100644 --- a/benchmarks/cmap_benchmark.cpp +++ b/benchmarks/cmap_benchmark.cpp @@ -11,7 +11,7 @@ enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; const char* operations[] = {"insert", "erase", "find", "iter", "destruct"}; typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; typedef struct { const char* name; Range test[N_TESTS]; } Sample; -enum {SAMPLES = 2, N = 8000000}; +enum {SAMPLES = 2, N = 8000000, R = 4}; uint64_t seed = 1, mask1 = 0xffffffff; static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } @@ -53,7 +53,7 @@ Sample test_std_unordered_map() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - for (auto i: con) sum += i.second; + c_forrange (R) for (auto i: con) sum += i.second; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); @@ -98,7 +98,7 @@ Sample test_stc_unordered_map() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_foreach (i, cmap_x, con) sum += i.ref->second; + c_forrange (R) 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(); diff --git a/benchmarks/csmap_benchmark.cpp b/benchmarks/csmap_benchmark.cpp index ec64d94c..0c73ca32 100644 --- a/benchmarks/csmap_benchmark.cpp +++ b/benchmarks/csmap_benchmark.cpp @@ -11,7 +11,7 @@ enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; const char* operations[] = {"insert", "erase", "find", "iter", "destruct"}; typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; typedef struct { const char* name; Range test[N_TESTS]; } Sample; -enum {SAMPLES = 2, N = 4000000}; +enum {SAMPLES = 2, N = 4000000, R = 4}; uint64_t seed = 1, mask1 = 0xfffffff; static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } @@ -49,7 +49,7 @@ Sample test_std_map() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - for (auto i: con) sum += i.second; + c_forrange (R) for (auto i: con) sum += i.second; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); @@ -95,7 +95,7 @@ Sample test_stc_map() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_foreach (i, csmap_x, con) sum += i.ref->second; + c_forrange (R) c_foreach (i, csmap_x, con) sum += i.ref->second; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); diff --git a/benchmarks/cvec_benchmark.cpp b/benchmarks/cvec_benchmark.cpp index c208b3a2..8a17902c 100644 --- a/benchmarks/cvec_benchmark.cpp +++ b/benchmarks/cvec_benchmark.cpp @@ -12,7 +12,7 @@ enum {INSERT, ERASE, FIND, ITER, DESTRUCT, N_TESTS}; const char* operations[] = {"insert", "erase", "find", "iter", "destruct"}; typedef struct { time_t t1, t2; uint64_t sum; float fac; } Range; typedef struct { const char* name; Range test[N_TESTS]; } Sample; -enum {SAMPLES = 2, N = 150000000, S = 0x3ffc}; +enum {SAMPLES = 2, N = 150000000, S = 0x3ffc, R = 4}; uint64_t seed = 1, mask1 = 0xfffffff, mask2 = 0xffff; static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } @@ -47,7 +47,7 @@ Sample test_std_vector() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_forrange (i, N) sum += con[i]; + c_forrange (R) c_forrange (i, N) sum += con[i]; s.test[ITER].t2 = clock(); s.test[ITER].sum = sum; s.test[DESTRUCT].t1 = clock(); @@ -89,7 +89,7 @@ Sample test_stc_vector() { s.test[FIND].sum = sum; s.test[ITER].t1 = clock(); sum = 0; - c_forrange (i, N) sum += *cvec_x_at(&con, i); + c_forrange (R) 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(); diff --git a/benchmarks/pics/benchmark.png b/benchmarks/pics/benchmark.png index 645c66d7..b07e31c9 100644 Binary files a/benchmarks/pics/benchmark.png and b/benchmarks/pics/benchmark.png differ diff --git a/stc/cdeq.h b/stc/cdeq.h index 7fddfcd2..d450f62d 100644 --- a/stc/cdeq.h +++ b/stc/cdeq.h @@ -63,7 +63,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; }; cdeq_##X##_value_from_raw(RawValue raw) {return valueFromRaw(raw);} \ STC_INLINE cdeq_##X##_value_t \ cdeq_##X##_value_clone(cdeq_##X##_value_t val) {return valueFromRaw(valueToRaw(&val));} \ - STC_INLINE void \ + STC_API void \ cdeq_##X##_clear(cdeq_##X* self); \ STC_API void \ cdeq_##X##_del(cdeq_##X* self); \ @@ -71,7 +71,7 @@ struct cdeq_rep { size_t size, cap; void* base[]; }; _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 \ + STC_INLINE void \ cdeq_##X##_reserve(cdeq_##X* self, size_t n) { \ _cdeq_##X##_expand(self, (n - _cdeq_rep(self)->size)*2/3, false); \ } \ -- cgit v1.2.3