Tuned benchmark shootout_hashmaps.cpp and updated two external c++ hash tables to newest. Updated benchmarks/build_all.sh

1 files changed, 47 insertions, 33 deletions

diff --git a/benchmarks/shootout_hashmaps.cpp b/benchmarks/shootout_hashmaps.cpp
index b2827333..ec3852f1 100644
--- a/benchmarks/shootout_hashmaps.cpp
+++ b/benchmarks/shootout_hashmaps.cpp
@@ -13,11 +13,11 @@
 #include "external/ankerl/robin_hood.h"
 #include "external/ankerl/unordered_dense.h"
 #include "external/skarupke/flat_hash_map.hpp"
+#include "external/tsl/robin_map.h"
+#include "external/emhash/hash_table7.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"
-#include "external/emhash/hash_table7.hpp"
 
 template<typename C> inline void std_destroy(C& c) { C().swap(c); }
 
@@ -25,12 +25,15 @@ template <class K, class V> using robin_hood_flat_map = robin_hood::unordered_fl
                                   K, V, robin_hood::hash<K>, std::equal_to<K>, MAX_LOAD_FACTOR>;
 #endif
 
+typedef int64_t IKey;
+typedef int64_t IValue;
+
 // khash template expansion
-KHASH_MAP_INIT_INT64(ii, int64_t)
+KHASH_MAP_INIT_INT64(ii, IValue)
 
 // cmap template expansion
-#define i_key int64_t
-#define i_val int64_t
+#define i_key IKey
+#define i_val IValue
 #define i_size uint32_t // optional, enables 2x expand
 #define i_hash(x) (*x * 0xc6a4a7935bd1e99d) // optional
 #define i_tag ii
@@ -39,8 +42,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #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)
+#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init(); \
+                                  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)
@@ -53,10 +56,14 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #define CMAP_DTOR(X)              cmap_##X##_drop(&map)
 
 #define KMAP_SETUP(X, Key, Value) khash_t(X)* map = kh_init(X); khiter_t ki; int ret
-#define KMAP_PUT(X, key, val)     (ki = kh_put(X, map, key, &ret), map->vals[ki] = val, map->vals[ki])
-#define KMAP_EMPLACE(X, key, val) (ki = kh_put(X, map, key, &ret), ret ? (map->vals[ki] = val, 0) : 1, map->vals[ki])
-#define KMAP_ERASE(X, key)        ((ki = kh_get(X, map, key)) != kh_end(map) ? kh_del(X, map, ki), 1 : 0)
-#define KMAP_FOR(X, i)            for (khint_t i = kh_begin(map); i != kh_end(map); ++i) if (kh_exist(map, i))
+#define KMAP_PUT(X, key, val)     (ki = kh_put(X, map, key, &ret), \
+                                   map->vals[ki] = val, map->vals[ki])
+#define KMAP_EMPLACE(X, key, val) (ki = kh_put(X, map, key, &ret), \
+                                   (ret ? map->vals[ki] = val, 1 : 0), map->vals[ki])
+#define KMAP_ERASE(X, key)        (ki = kh_get(X, map, key), \
+                                   ki != kh_end(map) ? (kh_del(X, map, ki), 1) : 0)
+#define KMAP_FOR(X, i)            for (khint_t i = kh_begin(map); i != kh_end(map); ++i) \
+                                      if (kh_exist(map, i))
 #define KMAP_ITEM(X, i)           map->vals[i]
 #define KMAP_FIND(X, key)         (kh_get(X, map, key) != kh_end(map))
 #define KMAP_SIZE(X)              kh_size(map)
@@ -64,7 +71,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #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())
@@ -76,7 +84,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #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)
@@ -88,7 +97,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #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)
@@ -100,7 +110,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #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)
@@ -124,7 +135,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #define RMAP_CLEAR(X)             UMAP_CLEAR(X)
 #define RMAP_DTOR(X)              UMAP_DTOR(X)
 
-#define DMAP_SETUP(X, Key, Value) ankerl::unordered_dense::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)
@@ -136,7 +148,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #define DMAP_CLEAR(X)             UMAP_CLEAR(X)
 #define DMAP_DTOR(X)              UMAP_DTOR(X)
 
-#define EMAP_SETUP(X, Key, Value) emhash7::HashMap<Key, Value> map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
+#define EMAP_SETUP(X, Key, Value) emhash7::HashMap<Key, Value> map; \
+                                  map.max_load_factor(MAX_LOAD_FACTOR/100.0f)
 #define EMAP_PUT(X, key, val)     UMAP_PUT(X, key, val)
 #define EMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
 #define EMAP_FIND(X, key)         UMAP_FIND(X, key)
@@ -148,7 +161,8 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 #define EMAP_CLEAR(X)             UMAP_CLEAR(X)
 #define EMAP_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_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)
@@ -163,12 +177,12 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 
 #define MAP_TEST1(M, X, n) \
 {   /* Insert, update */ \
-    M##_SETUP(X, int64_t, int64_t); \
+    M##_SETUP(X, IKey, IValue); \
     uint64_t sum = 0; \
     SEED(seed); \
     clock_t difference, before = clock(); \
     for (size_t i = 0; i < n; ++i) { \
-        sum += ++ M##_EMPLACE(X, RAND(keybits), i); \
+        sum += ++ M##_PUT(X, RAND(keybits), i); \
     } \
     difference = clock() - before; \
     printf(#M ": time: %5.03f, size: %" PRIuMAX ", buckets: %8" PRIuMAX ", sum: %" PRIuMAX "\n", \
@@ -178,11 +192,11 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 
 #define MAP_TEST2(M, X, n) \
 {   /* Insert sequential keys, then erase them */ \
-    M##_SETUP(X, int64_t, int64_t); \
+    M##_SETUP(X, IKey, IValue); \
     size_t erased = 0; \
     clock_t difference, before = clock(); \
     for (size_t i = 0; i < n; ++i) \
-        M##_PUT(X, i, i); \
+        M##_EMPLACE(X, i, i); \
     for (size_t i = 0; i < n; ++i) \
         erased += M##_ERASE(X, i); \
     difference = clock() - before; \
@@ -193,12 +207,12 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 
 #define MAP_TEST3(M, X, n) \
 {   /* Erase elements */ \
-    M##_SETUP(X, int64_t, int64_t); \
+    M##_SETUP(X, IKey, IValue); \
     size_t erased = 0; \
     clock_t difference, before; \
     SEED(seed); \
     for (size_t i = 0; i < n; ++i) \
-        M##_PUT(X, RAND(keybits), i); \
+        M##_EMPLACE(X, RAND(keybits), i); \
     SEED(seed); \
     before = clock(); \
     for (size_t i = 0; i < n; ++i) \
@@ -211,33 +225,33 @@ KHASH_MAP_INIT_INT64(ii, int64_t)
 
 #define MAP_TEST4(M, X, n) \
 {   /* Iterate */ \
-    M##_SETUP(X, int64_t, int64_t); \
+    M##_SETUP(X, IKey, IValue); \
     size_t sum = 0, m = 1ull << (keybits + 1), nn = n; \
     if (nn < m) m = nn; \
     SEED(seed); \
     for (size_t i = 0; i < m; ++i) \
-        M##_PUT(X, RAND(keybits), i); \
-    size_t x = 100000000/M##_SIZE(X); \
+        M##_EMPLACE(X, RAND(keybits), i); \
+    size_t rep = 70000000/M##_SIZE(X); \
     clock_t difference, before = clock(); \
-    for (size_t k=0; k < x; k++) M##_FOR (X, it) \
+    for (size_t k=0; k < rep; k++) M##_FOR (X, it) \
         sum += M##_ITEM(X, it); \
     difference = clock() - before; \
     printf(#M ": time: %5.03f, size: %" PRIuMAX ", buckets: %8" PRIuMAX ", repeats: %" PRIuMAX ", sum: %" PRIuMAX "\n", \
-           (float) difference / CLOCKS_PER_SEC, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X), x, sum); \
+           (float) difference / CLOCKS_PER_SEC, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X), rep, sum); \
     M##_DTOR(X); \
 }
 
 #define MAP_TEST5(M, X, n) \
 {   /* Lookup */ \
-    M##_SETUP(X, int64_t, int64_t); \
+    M##_SETUP(X, IKey, IValue); \
     size_t found = 0, m = 1ull << (keybits + 1), nn = n; \
     clock_t difference, before; \
     if (nn < m) m = nn; \
     SEED(seed); \
     for (size_t i = 0; i < m; ++i) \
-        M##_PUT(X, RAND(keybits), i); \
+        M##_EMPLACE(X, RAND(keybits), i); \
     before = clock(); \
-    size_t x = m * 8000000/M##_SIZE(X); \
+    size_t x = m * 3000000/M##_SIZE(X); \
     for (size_t i = 0; i < x; ++i) \
         found += M##_FIND(X, RAND(keybits)); \
     SEED(seed); \
@@ -269,7 +283,7 @@ int main(int argc, char* argv[])
     unsigned n_mill = argc >= 2 ? atoi(argv[1]) : DEFAULT_N_MILL;
     unsigned keybits = argc >= 3 ? atoi(argv[2]) : DEFAULT_KEYBITS;
     unsigned n = n_mill * 1000000;
-    unsigned N1 = n/2, N2 = n/2, N3 = n, N4 = n, N5 = n/2;
+    unsigned N1 = n/2, N2 = n/2, N3 = n, N4 = n, N5 = n;
     stc64_t rng;
     size_t seed = time(NULL);