From aa235b0080c563786e46fff1961277e2f84b379c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 10 Jan 2021 23:27:30 +0100 Subject: Updated benchmarks for maps. Switched args in cmap_X_set_load_factors(). --- benchmarks/cmap_benchmark.cpp | 2 +- benchmarks/cmap_benchmark2.cpp | 172 ++++++++++++++++++++++++++--------------- benchmarks/picobench.hpp | 5 +- docs/cmap_api.md | 2 +- docs/cset_api.md | 4 +- stc/cmap.h | 20 ++--- 6 files changed, 126 insertions(+), 79 deletions(-) diff --git a/benchmarks/cmap_benchmark.cpp b/benchmarks/cmap_benchmark.cpp index 9475ddc5..bdbcb9c9 100644 --- a/benchmarks/cmap_benchmark.cpp +++ b/benchmarks/cmap_benchmark.cpp @@ -34,7 +34,7 @@ stc64_t rng; #define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_inits \ - ; cmap_##X##_set_load_factors(&map, max_load_factor, 0.0) + ; 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) diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp index 7a0f43f2..7904effa 100644 --- a/benchmarks/cmap_benchmark2.cpp +++ b/benchmarks/cmap_benchmark2.cpp @@ -1,63 +1,90 @@ #include -#include #include +#include + +#include #include -#include +#include "others/bytell_hash_map.hpp" +#include "others/robin_hood.hpp" +#include "others/hopscotch_map.h" +#include "others/sparsepp/spp.h" #define PICOBENCH_IMPLEMENT_WITH_MAIN #include "picobench.hpp" - PICOBENCH_SUITE("Map"); -enum {N1 = 50000000, N2=20000000, N3=12000000, N4=6000000}; +enum {N1 = 5000000}; uint64_t seed = 123456; static inline uint32_t fibonacci_hash(const void* data, size_t len) { return (uint32_t) (((*(const uint32_t *) data) * 11400714819323198485llu) >> 24); } -using_cmap(ii, int, int, c_default_del, c_default_clone, c_default_equals, fibonacci_hash); -using_cmap_strkey(ss, cstr, cstr_del, cstr_clone); - -using Map = std::unordered_map; -using MapStr = std::unordered_map; - -static void stdmap_ctor_and_insert_one(picobench::state& s) +template using umap = std::unordered_map; +template using bmap = ska::bytell_hash_map; +template using fmap = ska::flat_hash_map; +template using hmap = tsl::hopscotch_map; +template using smap = spp::sparse_hash_map; +template using rmap = robin_hood::unordered_flat_map; + +using_cmap(i, int, int, c_default_del, c_default_clone, c_default_equals, fibonacci_hash); +using_cmap_strkey(s, cstr, cstr_del, cstr_clone); +using umap_i = umap; +using umap_s = umap; +using bmap_i = bmap; +using bmap_s = bmap; +using fmap_i = fmap; +using fmap_s = fmap; +using hmap_i = hmap; +using hmap_s = hmap; +using smap_i = smap; +using smap_s = smap; +using rmap_i = rmap; +using rmap_s = rmap; + +template +static void ctor_and_ins_one(picobench::state& s) { - printf("std::unordered_map: ctor_and_insert_one: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; c_forrange (n, s.iterations()) { - Map map; + MapInt map; map[n]; result += map.size(); } s.set_result(result); } -PICOBENCH(stdmap_ctor_and_insert_one).samples(1).iterations({N1}).baseline(); -static void cmap__ctor_and_insert_one(picobench::state& s) +static void ctor_and_ins_one_cmap_i_(picobench::state& s) { - printf("cmap: ctor_and_insert_one: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; c_forrange (n, s.iterations()) { - cmap_ii map = cmap_inits; - cmap_ii_emplace(&map, n, 0); - result += cmap_ii_size(map); - cmap_ii_del(&map); + cmap_i map = cmap_inits; + cmap_i_emplace(&map, n, 0); + result += cmap_i_size(map); + cmap_i_del(&map); } s.set_result(result); } -PICOBENCH(cmap__ctor_and_insert_one).samples(1).iterations({N1}); + +#define P samples(2).iterations({N1}) +PICOBENCH(ctor_and_ins_one).P.baseline(); +PICOBENCH(ctor_and_ins_one).P; +PICOBENCH(ctor_and_ins_one).P; +PICOBENCH(ctor_and_ins_one).P; +PICOBENCH(ctor_and_ins_one).P; +PICOBENCH(ctor_and_ins_one).P; +PICOBENCH(ctor_and_ins_one_cmap_i_).P; +#undef P -static void stdmap__insert_and_erase(picobench::state& s) +template +static void ins_and_erase(picobench::state& s) { stc64_srandom(seed); - printf("std::unordered_map: insert_and_erase: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; - Map map; + MapInt map; c_forrange (s.iterations()) map[stc64_random()]; map.clear(); @@ -69,61 +96,74 @@ static void stdmap__insert_and_erase(picobench::state& s) map.erase(stc64_random()); s.set_result(map.size()); } -PICOBENCH(stdmap__insert_and_erase).samples(1).iterations({N1}).baseline(); - -static void cmap__insert_and_erase(picobench::state& s) +static void ins_and_erase_cmap_i_(picobench::state& s) { stc64_srandom(seed); - printf("cmap: insert_and_erase: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); - cmap_ii map = cmap_inits; - cmap_ii_set_load_factors(&map, 0.80, 0); + cmap_i map = cmap_inits; + cmap_i_set_load_factors(&map, 0.0, 0.80); c_forrange (s.iterations()) - cmap_ii_emplace(&map, stc64_random(), 0); - cmap_ii_clear(&map); + cmap_i_emplace(&map, stc64_random(), 0); + cmap_i_clear(&map); stc64_srandom(seed); c_forrange (s.iterations()) - cmap_ii_emplace(&map, stc64_random(), 0); + cmap_i_emplace(&map, stc64_random(), 0); stc64_srandom(seed); c_forrange (s.iterations()) - cmap_ii_erase(&map, stc64_random()); - cmap_ii_del(&map); - s.set_result(cmap_ii_size(map)); + cmap_i_erase(&map, stc64_random()); + cmap_i_del(&map); + s.set_result(cmap_i_size(map)); } -PICOBENCH(cmap__insert_and_erase).samples(1).iterations({N1}); + +#define P samples(2).iterations({N1/4}) +PICOBENCH(ins_and_erase).P.baseline(); +PICOBENCH(ins_and_erase).P; +PICOBENCH(ins_and_erase).P; +PICOBENCH(ins_and_erase).P; +PICOBENCH(ins_and_erase).P; +PICOBENCH(ins_and_erase).P; +PICOBENCH(ins_and_erase_cmap_i_).P; +#undef P -static void stdmap__insert_and_access(picobench::state& s) +template +static void ins_and_access(picobench::state& s) { stc64_srandom(seed); uint64_t filter = (1ull << s.user_data()) - 1; - printf("std::unordered_map: insert_and_access: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; - Map map; + MapInt map; c_forrange (N1) result += ++map[stc64_random() & filter]; s.set_result(result); } -PICOBENCH(stdmap__insert_and_access).samples(1).iterations({N1, N1, N1, N1}).user_data({18, 23, 25, 31}).baseline(); - -static void cmap__insert_and_access(picobench::state& s) +static void ins_and_access_cmap_i_(picobench::state& s) { stc64_srandom(seed); uint64_t filter = (1ull << s.user_data()) - 1; - printf("cmap: insert_and_access: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; - cmap_ii map = cmap_inits; - cmap_ii_set_load_factors(&map, 0.80, 0); + cmap_i map = cmap_inits; + cmap_i_set_load_factors(&map, 0.0, 0.80); c_forrange (N1) - result += ++cmap_ii_emplace(&map, stc64_random() & filter, 0).first->second; + result += ++cmap_i_emplace(&map, stc64_random() & filter, 0).first->second; s.set_result(result); - cmap_ii_del(&map); + cmap_i_del(&map); } -PICOBENCH(cmap__insert_and_access).samples(1).iterations({N1, N1, N1, N1}).user_data({18, 23, 25, 31}); + +#define P samples(2).iterations({N1, N1, N1, N1}).user_data({18, 23, 25, 31}) +PICOBENCH(ins_and_access).P.baseline(); +PICOBENCH(ins_and_access).P; +PICOBENCH(ins_and_access).P; +PICOBENCH(ins_and_access).P; +PICOBENCH(ins_and_access).P; +PICOBENCH(ins_and_access).P; +PICOBENCH(ins_and_access_cmap_i_).P; +#undef P + static void randomize(char* str, size_t len) { union {uint64_t i; char c[8];} r = {.i = stc64_random()}; @@ -131,12 +171,12 @@ static void randomize(char* str, size_t len) { str[i] = (r.c[j] & 63) + 48; } -static void stdmap__ins_and_access_str(picobench::state& s) +template +static void ins_and_access_s(picobench::state& s) { stc64_srandom(seed); std::string str(s.user_data(), 'x'); randomize(&str[0], str.size()); - printf("std::unordered_map: insert_and_access string: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; MapStr map; @@ -152,33 +192,37 @@ static void stdmap__ins_and_access_str(picobench::state& s) } s.set_result(result); } -PICOBENCH(stdmap__ins_and_access_str).samples(1).iterations({N2, N2, N2, N3, N4}) - .user_data({7, 8, 13, 100, 1000}).baseline(); - -static void cmap__ins_and_access_str(picobench::state& s) +static void ins_and_access_s_cmap_s_(picobench::state& s) { stc64_srandom(seed); cstr str = cstr_with_size(s.user_data(), 'x'); randomize(str.str, cstr_size(str)); - printf("cmap: insert_and_access string: %zu: %zd\n", s.iterations(), s.user_data()); picobench::scope scope(s); size_t result = 0; - cmap_ss map = cmap_inits; - cmap_ss_set_load_factors(&map, 0.80, 0); + cmap_s map = cmap_inits; + cmap_s_set_load_factors(&map, 0.0, 0.80); c_forrange (s.iterations()) { randomize(str.str, cstr_size(str)); - cmap_ss_put(&map, str.str, cstr_clone(str)); + cmap_s_put(&map, str.str, cstr_clone(str)); randomize(str.str, cstr_size(str)); - cmap_ss_value_t* val = cmap_ss_find(&map, str.str); + cmap_s_value_t* val = cmap_s_find(&map, str.str); if (val) { ++result; - cmap_ss_erase_entry(&map, val); + cmap_s_erase_entry(&map, val); } } s.set_result(result); cstr_del(&str); - cmap_ss_del(&map); + cmap_s_del(&map); } -PICOBENCH(cmap__ins_and_access_str).samples(1).iterations({N2, N2, N2, N3, N4}) - .user_data({7, 8, 13, 100, 1000}); + +#define P samples(2).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).user_data({7, 8, 13, 100, 1000}) +PICOBENCH(ins_and_access_s).P.baseline(); +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s_cmap_s_).P; +#undef P \ No newline at end of file diff --git a/benchmarks/picobench.hpp b/benchmarks/picobench.hpp index 9a26e2e1..fc06709c 100644 --- a/benchmarks/picobench.hpp +++ b/benchmarks/picobench.hpp @@ -498,7 +498,7 @@ public: else { // no baseline to compare to - out << " ??? |"; + out << " ? |"; } auto ops_per_sec = ps.first.first * (1000000000.0 / double(bm.total_time_ns)); @@ -937,7 +937,8 @@ public: { auto i = benchmarks.begin() + long(rnd() % benchmarks.size()); auto& b = *i; - + std::cerr << "run: " << b->_name << ": " << b->_istate->iterations() + << " (" << b->_istate->user_data() << ")\n"; b->_proc(*b->_istate); ++b->_istate; diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 5e0a9fa3..e45c75c6 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -82,7 +82,7 @@ All cmap definitions and prototypes may be included in your C source file by inc ```c cmap_X cmap_X_init(void); cmap_X cmap_X_with_capacity(size_t cap); -void cmap_X_set_load_factors(cmap_X* self, float max, float shrink); +void cmap_X_set_load_factors(cmap_X* self, float min_load, float max_load); cmap_X cmap_X_clone(cmap_x map); void cmap_X_clear(cmap_X* self); diff --git a/docs/cset_api.md b/docs/cset_api.md index 6ab0fb00..f8629aa8 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -51,7 +51,7 @@ All cset definitions and prototypes may be included in your C source file by inc ```c cset_X cset_X_init(void); cset_X cset_X_with_capacity(size_t cap); -void cset_X_set_load_factors(cset_X* self, float max, float shrink); +void cset_X_set_load_factors(cset_X* self, float min_load, float max_load); cset_X cset_X_clone(cset_x set); void cset_X_clear(cset_X* self); @@ -109,7 +109,7 @@ int main () cset_str fifth = cset_str_clone(second); c_foreach (i, cset_str, third) - cset_str_insert(&fifth, cset_str_value_clone(*i.ref)); + cset_str_emplace(&fifth, i.ref->ref); c_foreach (i, cset_str, fourth) cset_str_emplace(&fifth, i.ref->str); diff --git a/stc/cmap.h b/stc/cmap.h index f3f24c1a..210c7282 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -54,7 +54,7 @@ int main(void) { #include #include -#define cmap_inits {NULL, NULL, 0, 0, 0.85f, 0.15f} +#define cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f} #define cset_inits cmap_inits #define c_try_emplace(self, ctype, key, val) do { \ @@ -184,8 +184,8 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; ctype##_##X##_value_t* table; \ uint8_t* _hashx; \ uint32_t size, bucket_count; \ + float min_load_factor; \ float max_load_factor; \ - float shrink_limit_factor; \ } ctype##_##X; \ \ typedef struct { \ @@ -217,8 +217,9 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; STC_INLINE void \ ctype##_##X##_swap(ctype##_##X* a, ctype##_##X* b) {c_swap(ctype##_##X, *a, *b);} \ STC_INLINE void \ - ctype##_##X##_set_load_factors(ctype##_##X* self, float max, float shrink) { \ - self->max_load_factor = max; self->shrink_limit_factor = shrink; \ + ctype##_##X##_set_load_factors(ctype##_##X* self, float min_load, float max_load) { \ + self->min_load_factor = min_load; \ + self->max_load_factor = max_load; \ } \ STC_API ctype##_##X \ ctype##_##X##_with_capacity(size_t cap); \ @@ -403,7 +404,7 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; ctype##_##X clone = { \ c_new_2(ctype##_##X##_value_t, m.bucket_count), \ (uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), \ - m.size, m.bucket_count, m.max_load_factor, m.shrink_limit_factor \ + m.size, m.bucket_count, m.min_load_factor, m.max_load_factor \ }; \ ctype##_##X##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \ @@ -413,14 +414,14 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; \ STC_DEF void \ ctype##_##X##_reserve(ctype##_##X* self, size_t newcap) { \ + if (newcap < self->size) return; \ size_t oldcap = self->bucket_count; \ - if (self->size > newcap) return; \ newcap = (size_t) (newcap / self->max_load_factor) | 1; \ ctype##_##X tmp = { \ c_new_2 (ctype##_##X##_value_t, newcap), \ (uint8_t *) c_calloc(newcap + 1, sizeof(uint8_t)), \ self->size, (uint32_t) newcap, \ - self->max_load_factor, self->shrink_limit_factor \ + self->min_load_factor, self->max_load_factor \ }; \ /* Rehash: */ \ tmp._hashx[newcap] = 0xff; c_swap(ctype##_##X, *self, tmp); \ @@ -452,8 +453,9 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ } while (true); \ - hashx[i] = 0; \ - --self->size; \ + hashx[i] = 0, k = --self->size; \ + if ((float) k / cap < self->min_load_factor && k > 512) \ + ctype##_##X##_reserve(self, k*1.2); \ } /* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ -- cgit v1.2.3