summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--benchmarks/cmap_benchmark.cpp2
-rw-r--r--benchmarks/cmap_benchmark2.cpp172
-rw-r--r--benchmarks/picobench.hpp5
-rw-r--r--docs/cmap_api.md2
-rw-r--r--docs/cset_api.md4
-rw-r--r--stc/cmap.h20
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 <stc/crand.h>
-#include <stc/cmap.h>
#include <stc/cstr.h>
+#include <stc/cmap.h>
+
+#include <string>
#include <unordered_map>
-#include <stdio.h>
+#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<int, int>;
-using MapStr = std::unordered_map<std::string, std::string>;
-
-static void stdmap_ctor_and_insert_one(picobench::state& s)
+template <class K, class V> using umap = std::unordered_map<K, V>;
+template <class K, class V> using bmap = ska::bytell_hash_map<K, V>;
+template <class K, class V> using fmap = ska::flat_hash_map<K, V>;
+template <class K, class V> using hmap = tsl::hopscotch_map<K, V>;
+template <class K, class V> using smap = spp::sparse_hash_map<K, V>;
+template <class K, class V> using rmap = robin_hood::unordered_flat_map<K, V>;
+
+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<int, int>;
+using umap_s = umap<std::string, std::string>;
+using bmap_i = bmap<int, int>;
+using bmap_s = bmap<std::string, std::string>;
+using fmap_i = fmap<int, int>;
+using fmap_s = fmap<std::string, std::string>;
+using hmap_i = hmap<int, int>;
+using hmap_s = hmap<std::string, std::string>;
+using smap_i = smap<int, int>;
+using smap_s = smap<std::string, std::string>;
+using rmap_i = rmap<int, int>;
+using rmap_s = rmap<std::string, std::string>;
+
+template <class MapInt>
+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<umap_i>).P.baseline();
+PICOBENCH(ctor_and_ins_one<bmap_i>).P;
+PICOBENCH(ctor_and_ins_one<fmap_i>).P;
+PICOBENCH(ctor_and_ins_one<hmap_i>).P;
+PICOBENCH(ctor_and_ins_one<smap_i>).P;
+PICOBENCH(ctor_and_ins_one<rmap_i>).P;
+PICOBENCH(ctor_and_ins_one_cmap_i_).P;
+#undef P
-static void stdmap__insert_and_erase(picobench::state& s)
+template <class MapInt>
+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<umap_i>).P.baseline();
+PICOBENCH(ins_and_erase<bmap_i>).P;
+PICOBENCH(ins_and_erase<fmap_i>).P;
+PICOBENCH(ins_and_erase<hmap_i>).P;
+PICOBENCH(ins_and_erase<smap_i>).P;
+PICOBENCH(ins_and_erase<rmap_i>).P;
+PICOBENCH(ins_and_erase_cmap_i_).P;
+#undef P
-static void stdmap__insert_and_access(picobench::state& s)
+template <class MapInt>
+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<umap_i>).P.baseline();
+PICOBENCH(ins_and_access<bmap_i>).P;
+PICOBENCH(ins_and_access<fmap_i>).P;
+PICOBENCH(ins_and_access<hmap_i>).P;
+PICOBENCH(ins_and_access<smap_i>).P;
+PICOBENCH(ins_and_access<rmap_i>).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 <class MapStr>
+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<umap_s>).P.baseline();
+PICOBENCH(ins_and_access_s<bmap_s>).P;
+PICOBENCH(ins_and_access_s<fmap_s>).P;
+PICOBENCH(ins_and_access_s<hmap_s>).P;
+PICOBENCH(ins_and_access_s<smap_s>).P;
+PICOBENCH(ins_and_access_s<rmap_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 <stdlib.h>
#include <string.h>
-#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/ */
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-11 12:47:15 +0000