summaryrefslogtreecommitdiffhomepage
path: root/benchmarks
diff options
context:
space:
mode:
Diffstat (limited to 'benchmarks')
-rw-r--r--benchmarks/build_all.sh2
-rw-r--r--benchmarks/external/ankerl/robin_hood.h (renamed from benchmarks/external/robin_hood.h)0
-rw-r--r--benchmarks/external/tsl/robin_hash.h1
-rw-r--r--benchmarks/external/update.sh43
-rw-r--r--benchmarks/misc/rust_cmap.c6
-rw-r--r--benchmarks/misc/string_bench_STC.cpp16
-rw-r--r--benchmarks/picobench/picobench_cmap.cpp51
-rw-r--r--benchmarks/picobench/picobench_csmap.cpp10
-rw-r--r--benchmarks/plotbench/cdeq_benchmark.cpp6
-rw-r--r--benchmarks/plotbench/cmap_benchmark.cpp4
-rw-r--r--benchmarks/plotbench/csmap_benchmark.cpp4
-rw-r--r--benchmarks/plotbench/cvec_benchmark.cpp4
-rw-r--r--benchmarks/shootout_hashmaps.cpp78
13 files changed, 111 insertions, 114 deletions
diff --git a/benchmarks/build_all.sh b/benchmarks/build_all.sh
index 348a79dd..1093807c 100644
--- a/benchmarks/build_all.sh
+++ b/benchmarks/build_all.sh
@@ -1,5 +1,5 @@
#!/bin/bash
-cc='g++ -std=c++17'
+cc='g++ -std=c++20'
#cc='clang'
#cc='clang -c -DSTC_HEADER'
#cc='cl -nologo'
diff --git a/benchmarks/external/robin_hood.h b/benchmarks/external/ankerl/robin_hood.h
index 0af031f5..0af031f5 100644
--- a/benchmarks/external/robin_hood.h
+++ b/benchmarks/external/ankerl/robin_hood.h
diff --git a/benchmarks/external/tsl/robin_hash.h b/benchmarks/external/tsl/robin_hash.h
index f9fb9e76..89c7c96f 100644
--- a/benchmarks/external/tsl/robin_hash.h
+++ b/benchmarks/external/tsl/robin_hash.h
@@ -1589,6 +1589,7 @@ class robin_hash : private Hash, private KeyEqual, private GrowthPolicy {
*/
bucket_entry* static_empty_bucket_ptr() noexcept {
static bucket_entry empty_bucket(true);
+ tsl_rh_assert(empty_bucket.empty());
return &empty_bucket;
}
diff --git a/benchmarks/external/update.sh b/benchmarks/external/update.sh
index c0169fab..00b587cb 100644
--- a/benchmarks/external/update.sh
+++ b/benchmarks/external/update.sh
@@ -1,35 +1,32 @@
tsl_h="https://raw.github.com/Tessil/hopscotch-map/master/include/tsl/"
tsl_r="https://raw.github.com/Tessil/robin-map/master/include/tsl/"
-tsl_s="https://raw.github.com/Tessil/sparse-map/master/include/tsl/"
-greg="https://raw.github.com/greg7mdp/sparsepp/master/sparsepp/"
-martinus="https://raw.github.com/martinus/robin-hood-hashing/master/src/include/"
+smap="https://raw.github.com/greg7mdp/sparsepp/master/sparsepp/"
+pmap="https://raw.github.com/greg7mdp/parallel-hashmap/"
+martinus_r="https://raw.github.com/martinus/robin-hood-hashing/master/src/include/"
+martinus_d="https://raw.github.com/martinus/unordered_dense/master/include/ankerl/"
skarupke="https://raw.github.com/skarupke/flat_hash_map/master/"
-mkdir -p tsl sparsepp skarupke
+mkdir -p ankerl skarupke sparsepp tsl
-wget $martinus"robin_hood.h" -O "robin_hood.h"
+wget $martinus_r"robin_hood.h" -O "ankerl/robin_hood.h"
+wget $martinus_d"unordered_dense.h" -O "ankerl/unordered_dense.h"
-wget $skarupke"bytell_hash_map.hpp" -O "skarupke/bytell_hash_map.hpp"
+#wget $skarupke"bytell_hash_map.hpp" -O "skarupke/bytell_hash_map.hpp"
wget $skarupke"flat_hash_map.hpp" -O "skarupke/flat_hash_map.hpp"
-wget $greg"spp.h" -O "sparsepp/spp.h"
-wget $greg"spp_config.h" -O "sparsepp/spp_config.h"
-wget $greg"spp_dlalloc.h" -O "sparsepp/spp_dlalloc.h"
-wget $greg"spp_memory.h" -O "sparsepp/spp_memory.h"
-wget $greg"spp_smartptr.h" -O "sparsepp/spp_smartptr.h"
-wget $greg"spp_stdint.h" -O "sparsepp/spp_stdint.h"
-wget $greg"spp_timer.h" -O "sparsepp/spp_timer.h"
-wget $greg"spp_traits.h" -O "sparsepp/spp_traits.h"
-wget $greg"spp_utils.h" -O "sparsepp/spp_utils.h"
-
-wget $tsl_h"hopscotch_growth_policy.h" -O "tsl/hopscotch_growth_policy.h"
-wget $tsl_h"hopscotch_hash.h" -O "tsl/hopscotch_hash.h"
-wget $tsl_h"hopscotch_map.h" -O "tsl/hopscotch_map.h"
+#wget $smap"spp.h" -O "sparsepp/spp.h"
+#wget $smap"spp_config.h" -O "sparsepp/spp_config.h"
+#wget $smap"spp_dlalloc.h" -O "sparsepp/spp_dlalloc.h"
+#wget $smap"spp_memory.h" -O "sparsepp/spp_memory.h"
+#wget $smap"spp_smartptr.h" -O "sparsepp/spp_smartptr.h"
+#wget $smap"spp_stdint.h" -O "sparsepp/spp_stdint.h"
+#wget $smap"spp_timer.h" -O "sparsepp/spp_timer.h"
+#wget $smap"spp_traits.h" -O "sparsepp/spp_traits.h"
+#wget $smap"spp_utils.h" -O "sparsepp/spp_utils.h"
+#wget $tsl_h"hopscotch_growth_policy.h" -O "tsl/hopscotch_growth_policy.h"
+#wget $tsl_h"hopscotch_hash.h" -O "tsl/hopscotch_hash.h"
+#wget $tsl_h"hopscotch_map.h" -O "tsl/hopscotch_map.h"
wget $tsl_r"robin_growth_policy.h" -O "tsl/robin_growth_policy.h"
wget $tsl_r"robin_hash.h" -O "tsl/robin_hash.h"
wget $tsl_r"robin_map.h" -O "tsl/robin_map.h"
-
-#wget $tsl_s"sparse_growth_policy.h" -O "tsl/sparse_growth_policy.h"
-#wget $tsl_s"sparse_hash.h" -O "tsl/sparse_hash.h"
-#wget $tsl_s"sparse_map.h" -O "tsl/sparse_map.h"
diff --git a/benchmarks/misc/rust_cmap.c b/benchmarks/misc/rust_cmap.c
index 1e763bde..933910cb 100644
--- a/benchmarks/misc/rust_cmap.c
+++ b/benchmarks/misc/rust_cmap.c
@@ -37,7 +37,7 @@ int main()
uint64_t key = romu_trio(rng) & mask;
cmap_u64_insert(&m, key, 0).ref->second += 1;
}
- printf("insert : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(m));
+ printf("insert : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(&m));
now = clock();
sum = 0;
@@ -55,7 +55,7 @@ int main()
uint64_t key = romu_trio(rng2) & mask;
cmap_u64_erase(&m, key);
}
- printf("remove : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(m));
+ printf("remove : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(&m));
printf("press a key:\n"); getchar();
}
-} \ No newline at end of file
+}
diff --git a/benchmarks/misc/string_bench_STC.cpp b/benchmarks/misc/string_bench_STC.cpp
index 2e05dae3..9fc861ea 100644
--- a/benchmarks/misc/string_bench_STC.cpp
+++ b/benchmarks/misc/string_bench_STC.cpp
@@ -68,10 +68,10 @@ private:
void initShortStringVec(cvec_str* vs, cvec_sv* vsv)
{
- cvec_str_clear(vs);
+ cvec_str_drop(vs);
cvec_sv_clear(vsv);
- cvec_str_copy(vs, read_file("names.txt"));
+ *vs = read_file("names.txt");
/*
cvec_str_emplace_back(vs, "Susan");
cvec_str_emplace_back(vs, "Jason");
@@ -103,16 +103,16 @@ void initShortStringVec(cvec_str* vs, cvec_sv* vsv)
cvec_sv_push_back(vsv, csview_from_s(i.ref));
num += cstr_size(*i.ref);
}
- std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl;
- std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl;
+ std::cout << "num strings: " << cvec_sv_size(vsv) << std::endl;
+ std::cout << "avg str len: " << num / (float)cvec_sv_size(vsv) << std::endl;
}
void initLongStringVec(cvec_str* vs, cvec_sv* vsv)
{
- cvec_str_clear(vs);
+ cvec_str_drop(vs);
cvec_sv_clear(vsv);
- cvec_str_copy(vs, read_file("names.txt"));
+ *vs = read_file("names.txt");
c_foreach (i, cvec_str, *vs) {
cstr_append_s(i.ref, *i.ref);
cstr_append_s(i.ref, *i.ref);
@@ -149,8 +149,8 @@ void initLongStringVec(cvec_str* vs, cvec_sv* vsv)
cvec_sv_push_back(vsv, csview_from_s(i.ref));
num += cstr_size(*i.ref);
}
- std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl;
- std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl;
+ std::cout << "num strings: " << cvec_sv_size(vsv) << std::endl;
+ std::cout << "avg str len: " << num / (float)cvec_sv_size(vsv) << std::endl;
}
void initMaps(const cvec_str* vs, csmap_str* mapTrans, csmap_ssv* mapSview,
diff --git a/benchmarks/picobench/picobench_cmap.cpp b/benchmarks/picobench/picobench_cmap.cpp
index 4a330019..f4551aa1 100644
--- a/benchmarks/picobench/picobench_cmap.cpp
+++ b/benchmarks/picobench/picobench_cmap.cpp
@@ -6,10 +6,9 @@
#include <string>
#include <unordered_map>
#include <stdexcept>
-#include "../external/robin_hood.h"
-#include "../external/skarupke/bytell_hash_map.hpp"
-#include "../external/tsl/hopscotch_map.h"
-#include "../external/parallel_hashmap/phmap.h"
+#include "../external/ankerl/unordered_dense.h"
+#include "../external/skarupke/flat_hash_map.hpp"
+#include "../external/tsl/robin_map.h"
#define PICOBENCH_IMPLEMENT_WITH_MAIN
#include "picobench.hpp"
@@ -18,20 +17,14 @@ enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80};
uint64_t seed = time(NULL);
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 pmap = phmap::flat_hash_map<K, V>;
-template <class K, class V> using rmap = robin_hood::unordered_flat_map<K, V,
- robin_hood::hash<K>, std::equal_to<K>, MaxLoadFactor100>;
+template <class K, class V> using tmap = tsl::robin_map<K, V>;
+template <class K, class V> using dmap = ankerl::unordered_dense::map<K, V>;
#define DEFMAP(map, ...) \
using u##map = umap __VA_ARGS__; \
- using b##map = bmap __VA_ARGS__; \
using f##map = fmap __VA_ARGS__; \
- using h##map = hmap __VA_ARGS__; \
- using p##map = pmap __VA_ARGS__; \
- using r##map = rmap __VA_ARGS__
-
+ using t##map = tmap __VA_ARGS__; \
+ using d##map = dmap __VA_ARGS__
DEFMAP(map_i, <int32_t, int32_t>);
DEFMAP(map_x, <uint64_t, uint64_t>);
@@ -90,7 +83,7 @@ static void ins_and_erase_cmap_i(picobench::state& s)
csrandom(seed);
c_forrange (s.iterations())
cmap_i_erase(&map, crandom());
- s.set_result(cmap_i_size(map));
+ s.set_result(cmap_i_size(&map));
cmap_i_drop(&map);
}
@@ -110,17 +103,15 @@ static void ins_and_erase_cmap_x(picobench::state& s)
csrandom(seed);
c_forrange (s.iterations())
cmap_x_erase(&map, crandom());
- s.set_result(cmap_x_size(map));
+ s.set_result(cmap_x_size(&map));
cmap_x_drop(&map);
}
#define P samples(S1).iterations({N1/4})
PICOBENCH(ins_and_erase_i<umap_x>).P;
-PICOBENCH(ins_and_erase_i<bmap_x>).P;
+PICOBENCH(ins_and_erase_i<dmap_x>).P;
PICOBENCH(ins_and_erase_i<fmap_x>).P;
-PICOBENCH(ins_and_erase_i<hmap_x>).P;
-PICOBENCH(ins_and_erase_i<pmap_x>).P;
-PICOBENCH(ins_and_erase_i<rmap_x>).P;
+PICOBENCH(ins_and_erase_i<tmap_x>).P;
PICOBENCH(ins_and_erase_cmap_x).P;
#undef P
@@ -158,11 +149,9 @@ static void ins_and_access_cmap_i(picobench::state& s)
#define P samples(S1).iterations({N1, N1, N1, N1}).args({18, 23, 25, 31})
PICOBENCH(ins_and_access_i<umap_i>).P;
-PICOBENCH(ins_and_access_i<bmap_i>).P;
+PICOBENCH(ins_and_access_i<dmap_i>).P;
PICOBENCH(ins_and_access_i<fmap_i>).P;
-PICOBENCH(ins_and_access_i<hmap_i>).P;
-PICOBENCH(ins_and_access_i<pmap_i>).P;
-PICOBENCH(ins_and_access_i<rmap_i>).P;
+PICOBENCH(ins_and_access_i<tmap_i>).P;
PICOBENCH(ins_and_access_cmap_i).P;
#undef P
@@ -213,18 +202,16 @@ static void ins_and_access_cmap_s(picobench::state& s)
randomize(buf, s.arg());
result += cmap_str_erase(&map, buf);
}
- s.set_result(result + cmap_str_size(map));
+ s.set_result(result + cmap_str_size(&map));
cstr_drop(&str);
cmap_str_drop(&map);
}
#define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000})
PICOBENCH(ins_and_access_s<umap_s>).P;
-PICOBENCH(ins_and_access_s<bmap_s>).P;
+PICOBENCH(ins_and_access_s<dmap_s>).P;
PICOBENCH(ins_and_access_s<fmap_s>).P;
-PICOBENCH(ins_and_access_s<hmap_s>).P;
-PICOBENCH(ins_and_access_s<pmap_s>).P;
-PICOBENCH(ins_and_access_s<rmap_s>).P;
+PICOBENCH(ins_and_access_s<tmap_s>).P;
PICOBENCH(ins_and_access_cmap_s).P;
#undef P
@@ -293,10 +280,8 @@ static void iterate_cmap_x(picobench::state& s)
#define P samples(S1).iterations({N1/20}).args({12})
PICOBENCH(iterate_x<umap_x>).P;
-PICOBENCH(iterate_x<bmap_x>).P;
+PICOBENCH(iterate_x<dmap_x>).P;
PICOBENCH(iterate_x<fmap_x>).P;
-PICOBENCH(iterate_x<hmap_x>).P;
-PICOBENCH(iterate_x<pmap_x>).P;
-PICOBENCH(iterate_x<rmap_x>).P;
+PICOBENCH(iterate_x<tmap_x>).P;
PICOBENCH(iterate_cmap_x).P;
#undef P
diff --git a/benchmarks/picobench/picobench_csmap.cpp b/benchmarks/picobench/picobench_csmap.cpp
index ea2174fa..312b38c5 100644
--- a/benchmarks/picobench/picobench_csmap.cpp
+++ b/benchmarks/picobench/picobench_csmap.cpp
@@ -53,7 +53,7 @@ static void ctor_and_ins_one_csmap_i(picobench::state& s)
c_forrange (n, s.iterations()) {
csmap_i map = csmap_i_init();
csmap_i_insert(&map, n, 0);
- result += csmap_i_size(map);
+ result += csmap_i_size(&map);
csmap_i_drop(&map);
}
s.set_result(result);
@@ -87,7 +87,7 @@ static void insert_csmap_i(picobench::state& s)
picobench::scope scope(s);
c_forrange (n, s.iterations())
csmap_i_insert(&map, crandom() & 0xfffffff, n);
- s.set_result(csmap_i_size(map));
+ s.set_result(csmap_i_size(&map));
csmap_i_drop(&map);
}
@@ -133,7 +133,7 @@ static void ins_and_erase_csmap_i(picobench::state& s)
picobench::scope scope(s);
c_forrange (i, s.iterations())
csmap_i_insert(&map, crandom() & mask, i);
- result = csmap_i_size(map);
+ result = csmap_i_size(&map);
csmap_i_clear(&map);
csrandom(seed);
@@ -184,7 +184,7 @@ static void ins_and_access_csmap_i(picobench::state& s)
const csmap_i_value* val = csmap_i_get(&map, crandom() & mask);
if (val) csmap_i_erase(&map, val->first);
}
- s.set_result(result + csmap_i_size(map));
+ s.set_result(result + csmap_i_size(&map));
csmap_i_drop(&map);
}
@@ -245,7 +245,7 @@ static void ins_and_access_csmap_s(picobench::state& s)
csmap_str_erase(&map, cstr_str(&it.ref->first));
}*/
}
- s.set_result(result + csmap_str_size(map));
+ s.set_result(result + csmap_str_size(&map));
cstr_drop(&str);
csmap_str_drop(&map);
}
diff --git a/benchmarks/plotbench/cdeq_benchmark.cpp b/benchmarks/plotbench/cdeq_benchmark.cpp
index d938450a..72884e78 100644
--- a/benchmarks/plotbench/cdeq_benchmark.cpp
+++ b/benchmarks/plotbench/cdeq_benchmark.cpp
@@ -77,11 +77,11 @@ Sample test_stc_deque() {
c_forrange (N/3) {cdeq_x_push_back(&con, crandom() & mask1); cdeq_x_pop_front(&con);}
c_forrange (N/3) cdeq_x_push_back(&con, crandom() & mask1);
s.test[INSERT].t2 = clock();
- s.test[INSERT].sum = cdeq_x_size(con);
+ s.test[INSERT].sum = cdeq_x_size(&con);
s.test[ERASE].t1 = clock();
- c_forrange (cdeq_x_size(con)/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);
+ s.test[ERASE].sum = cdeq_x_size(&con);
cdeq_x_drop(&con);
}{
csrandom(seed);
diff --git a/benchmarks/plotbench/cmap_benchmark.cpp b/benchmarks/plotbench/cmap_benchmark.cpp
index 781ad720..4304db52 100644
--- a/benchmarks/plotbench/cmap_benchmark.cpp
+++ b/benchmarks/plotbench/cmap_benchmark.cpp
@@ -76,12 +76,12 @@ Sample test_stc_unordered_map() {
c_forrange (i, N/2) cmap_x_insert(&con, crandom() & mask1, i);
c_forrange (i, N/2) cmap_x_insert(&con, i, i);
s.test[INSERT].t2 = clock();
- s.test[INSERT].sum = cmap_x_size(con);
+ s.test[INSERT].sum = cmap_x_size(&con);
csrandom(seed);
s.test[ERASE].t1 = clock();
c_forrange (N) cmap_x_erase(&con, crandom() & mask1);
s.test[ERASE].t2 = clock();
- s.test[ERASE].sum = cmap_x_size(con);
+ s.test[ERASE].sum = cmap_x_size(&con);
cmap_x_drop(&con);
}{
container con = cmap_x_init();
diff --git a/benchmarks/plotbench/csmap_benchmark.cpp b/benchmarks/plotbench/csmap_benchmark.cpp
index 3fb8a0a4..b319006f 100644
--- a/benchmarks/plotbench/csmap_benchmark.cpp
+++ b/benchmarks/plotbench/csmap_benchmark.cpp
@@ -77,12 +77,12 @@ Sample test_stc_map() {
c_forrange (i, N/2) csmap_x_insert(&con, crandom() & mask1, i);
c_forrange (i, N/2) csmap_x_insert(&con, i, i);
s.test[INSERT].t2 = clock();
- s.test[INSERT].sum = csmap_x_size(con);
+ s.test[INSERT].sum = csmap_x_size(&con);
csrandom(seed);
s.test[ERASE].t1 = clock();
c_forrange (N) csmap_x_erase(&con, crandom() & mask1);
s.test[ERASE].t2 = clock();
- s.test[ERASE].sum = csmap_x_size(con);
+ s.test[ERASE].sum = csmap_x_size(&con);
csmap_x_drop(&con);
}{
container con = csmap_x_init();
diff --git a/benchmarks/plotbench/cvec_benchmark.cpp b/benchmarks/plotbench/cvec_benchmark.cpp
index 9ba95f31..44dcee2f 100644
--- a/benchmarks/plotbench/cvec_benchmark.cpp
+++ b/benchmarks/plotbench/cvec_benchmark.cpp
@@ -73,11 +73,11 @@ Sample test_stc_vector() {
csrandom(seed);
c_forrange (N) cvec_x_push_back(&con, crandom() & mask1);
s.test[INSERT].t2 = clock();
- s.test[INSERT].sum = cvec_x_size(con);
+ 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);
+ s.test[ERASE].sum = cvec_x_size(&con);
cvec_x_drop(&con);
}{
csrandom(seed);
diff --git a/benchmarks/shootout_hashmaps.cpp b/benchmarks/shootout_hashmaps.cpp
index 0cf29ab7..9f5315c0 100644
--- a/benchmarks/shootout_hashmaps.cpp
+++ b/benchmarks/shootout_hashmaps.cpp
@@ -5,47 +5,47 @@
#include <stc/cstr.h>
#include "external/khash.h"
-enum {max_load_factor = 77};
+#define MAX_LOAD_FACTOR 77
#ifdef __cplusplus
#include <limits>
#include <unordered_map>
-#include "external/robin_hood.h"
-#include "external/skarupke/bytell_hash_map.hpp"
-#include "external/parallel_hashmap/phmap.h"
-#include "external/tsl/hopscotch_map.h"
+#include "external/ankerl/robin_hood.h"
+#include "external/ankerl/unordered_dense.h"
+#include "external/skarupke/flat_hash_map.hpp"
+//#include "external/skarupke/bytell_hash_map.hpp"
+//#include "external/parallel_hashmap/phmap.h"
+//#include "external/tsl/hopscotch_map.h"
#include "external/tsl/robin_map.h"
template<typename C> inline void std_destroy(C& c) { C().swap(c); }
template <class K, class V> using robin_hood_flat_map = robin_hood::unordered_flat_map<
- K, V, robin_hood::hash<K>, std::equal_to<K>, max_load_factor>;
+ K, V, robin_hood::hash<K>, std::equal_to<K>, MAX_LOAD_FACTOR>;
#endif
+// khash template expansion
KHASH_MAP_INIT_INT64(ii, int64_t)
-// cmap and khash template expansion
+// cmap template expansion
#define i_key int64_t
#define i_val int64_t
#define i_tag ii
#include <stc/cmap.h>
-stc64_t rng;
-size_t seed;
-#define SEED(s) rng = stc64_new(seed)
+#define SEED(s) rng = stc64_new(s)
#define RAND(N) (stc64_rand(&rng) & (((uint64_t)1 << N) - 1))
-
#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \
- ; cmap_##X##_max_load_factor(&map, max_load_factor/100.0f)
+ ; cmap_##X##_max_load_factor(&map, MAX_LOAD_FACTOR/100.0f)
#define CMAP_PUT(X, key, val) cmap_##X##_insert_or_assign(&map, key, val).ref->second
#define CMAP_EMPLACE(X, key, val) cmap_##X##_insert(&map, key, val).ref->second
#define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key)
#define CMAP_FIND(X, key) cmap_##X##_contains(&map, key)
#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_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##_drop(&map)
@@ -61,7 +61,7 @@ size_t seed;
#define KMAP_CLEAR(X) kh_clear(X, map)
#define KMAP_DTOR(X) kh_destroy(X, map)
-#define UMAP_SETUP(X, Key, Value) std::unordered_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
+#define UMAP_SETUP(X, Key, Value) std::unordered_map<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
#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) int(map.find(key) != map.end())
@@ -73,7 +73,7 @@ size_t seed;
#define UMAP_CLEAR(X) map.clear()
#define UMAP_DTOR(X) std_destroy(map)
-#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
+#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
#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)
@@ -85,7 +85,7 @@ size_t seed;
#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/100.0f)
+#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
#define HMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define HMAP_EMPLACE(X, key, val) map.emplace(key, val).first.value()
#define HMAP_FIND(X, key) UMAP_FIND(X, key)
@@ -97,7 +97,7 @@ size_t seed;
#define HMAP_CLEAR(X) UMAP_CLEAR(X)
#define HMAP_DTOR(X) UMAP_DTOR(X)
-#define TMAP_SETUP(X, Key, Value) tsl::robin_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
+#define TMAP_SETUP(X, Key, Value) tsl::robin_map<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
#define TMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define TMAP_EMPLACE(X, key, val) map.emplace(key, val).first.value()
#define TMAP_FIND(X, key) UMAP_FIND(X, key)
@@ -122,7 +122,19 @@ size_t seed;
#define RMAP_CLEAR(X) UMAP_CLEAR(X)
#define RMAP_DTOR(X) UMAP_DTOR(X)
-#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor/100.0f)
+#define DMAP_SETUP(X, Key, Value) ankerl::unordered_dense::map<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
+#define DMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
+#define DMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
+#define DMAP_FIND(X, key) UMAP_FIND(X, key)
+#define DMAP_ERASE(X, key) UMAP_ERASE(X, key)
+#define DMAP_FOR(X, i) UMAP_FOR(X, i)
+#define DMAP_ITEM(X, i) UMAP_ITEM(X, i)
+#define DMAP_SIZE(X) UMAP_SIZE(X)
+#define DMAP_BUCKETS(X) UMAP_BUCKETS(X)
+#define DMAP_CLEAR(X) UMAP_CLEAR(X)
+#define DMAP_DTOR(X) UMAP_DTOR(X)
+
+#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
#define PMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define PMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
#define PMAP_FIND(X, key) UMAP_FIND(X, key)
@@ -191,7 +203,7 @@ size_t seed;
SEED(seed); \
for (size_t i = 0; i < m; ++i) \
M##_PUT(X, RAND(keybits), i); \
- size_t x = 200000000/M##_SIZE(X); \
+ size_t x = 100000000/M##_SIZE(X); \
clock_t difference, before = clock(); \
for (size_t k=0; k < x; k++) M##_FOR (X, it) \
sum += M##_ITEM(X, it); \
@@ -211,7 +223,7 @@ size_t seed;
for (size_t i = 0; i < m; ++i) \
M##_PUT(X, RAND(keybits), i); \
before = clock(); \
- size_t x = m * 10000000/M##_SIZE(X); \
+ size_t x = m * 8000000/M##_SIZE(X); \
for (size_t i = 0; i < x; ++i) \
found += M##_FIND(X, RAND(keybits)); \
SEED(seed); \
@@ -226,16 +238,16 @@ size_t seed;
#ifdef __cplusplus
#define RUN_TEST(n) MAP_TEST##n(KMAP, ii, N##n) MAP_TEST##n(CMAP, ii, N##n) \
- MAP_TEST##n(PMAP, ii, N##n) MAP_TEST##n(FMAP, ii, N##n) \
- MAP_TEST##n(RMAP, ii, N##n) MAP_TEST##n(HMAP, ii, N##n) \
- MAP_TEST##n(TMAP, ii, N##n) MAP_TEST##n(UMAP, ii, N##n)
+ MAP_TEST##n(FMAP, ii, N##n) MAP_TEST##n(TMAP, ii, N##n) \
+ MAP_TEST##n(RMAP, ii, N##n) MAP_TEST##n(DMAP, ii, N##n) \
+ MAP_TEST##n(UMAP, ii, N##n)
#else
#define RUN_TEST(n) MAP_TEST##n(KMAP, ii, N##n) MAP_TEST##n(CMAP, ii, N##n)
#endif
enum {
- DEFAULT_N_MILL = 40,
- DEFAULT_KEYBITS = 25,
+ DEFAULT_N_MILL = 10,
+ DEFAULT_KEYBITS = 22,
};
int main(int argc, char* argv[])
@@ -244,16 +256,18 @@ int main(int argc, char* argv[])
unsigned keybits = argc >= 3 ? atoi(argv[2]) : DEFAULT_KEYBITS;
unsigned n = n_mill * 1000000;
unsigned N0 = n, N1 = n/2, N2 = n/2, N3 = n, N4 = n, N5 = n;
- seed = time(NULL); // 1636306010;
+ stc64_t rng;
+ size_t seed = time(NULL);
printf("\nUnordered hash map shootout\n");
- printf("CMAP = https://github.com/tylov/STC\n"
- "KMAP = https://github.com/attractivechaos/klib\n"
- "PMAP = https://github.com/greg7mdp/parallel-hashmap\n"
+ printf("KMAP = https://github.com/attractivechaos/klib\n"
+ "CMAP = https://github.com/tylov/STC (**)\n"
+ //"PMAP = https://github.com/greg7mdp/parallel-hashmap\n"
"FMAP = https://github.com/skarupke/flat_hash_map\n"
- "RMAP = https://github.com/martinus/robin-hood-hashing\n"
- "HMAP = https://github.com/Tessil/hopscotch-map\n"
"TMAP = https://github.com/Tessil/robin-map\n"
+ //"HMAP = https://github.com/Tessil/hopscotch-map\n"
+ "RMAP = https://github.com/martinus/robin-hood-hashing\n"
+ "DMAP = https://github.com/martinus/unordered_dense\n"
"UMAP = std::unordered_map\n\n");
printf("Usage %s [n-million=%d key-bits=%d]\n", argv[0], DEFAULT_N_MILL, DEFAULT_KEYBITS);
generated by cgit v1.2.3 (git 2.39.1) at 2026-04-18 02:47:41 +0000