Tuned cmap.h and hash function.

4 files changed, 68 insertions, 46 deletions

diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h
index 2453143c..bac25fb1 100644
--- a/include/stc/ccommon.h
+++ b/include/stc/ccommon.h
@@ -147,13 +147,13 @@ STC_INLINE uint64_t cfasthash(const void* key, intptr_t len) {
         case 0: return 1;
     }
     const uint8_t *x = (const uint8_t*)key;
-    uint64_t h = *x*0x811c9dc5ULL, n = (uint64_t)len >> 3;
+    uint64_t h = *x | (*x << 15), n = (uint64_t)len >> 3;
     len &= 7;
     while (n--) {
         memcpy(&u8, x, 8), x += 8;
-        h = (h ^ u8)*0x01000193ULL;
+        h = (h ^ u8)*0x9e3779b97f4a7c15;
     }
-    while (len--) h = (h ^ *x++)*0x01000193ULL;
+    while (len--) h = (h ^ *x++)*0xbf58476d1ce4e5b9;
     return h;
 }
 
diff --git a/include/stc/cmap.h b/include/stc/cmap.h
index 986771e5..1aeb63df 100644
--- a/include/stc/cmap.h
+++ b/include/stc/cmap.h
@@ -71,10 +71,10 @@ typedef struct { intptr_t idx; uint8_t hashx, found; } chash_bucket;
 #endif
 #define _i_ishash
 #ifndef i_max_load_factor
-  #define i_max_load_factor 0.82f
+  #define i_max_load_factor 0.80f
 #endif
-#ifndef i_sizebits
-  #define i_sizebits 32
+#ifndef i_expandby
+  #define i_expandby 1
 #endif
 #include "priv/template.h"
 #ifndef i_is_forward
@@ -285,20 +285,26 @@ _cx_memb(_eq)(const _cx_self* self, const _cx_self* other) {
 #if defined(i_implement)
 
 #ifndef CMAP_H_INCLUDED
-STC_INLINE int64_t fastrange_32(uint64_t x, uint64_t n)
-    { return (int64_t)((uint32_t)x*n >> 32); } // n < 2^31
-
-STC_INLINE int64_t fastrange_64(uint64_t x, uint64_t n) {
-    uint64_t lo, hi; c_umul128(x, n, &lo, &hi);
-    return (int64_t)hi;
+STC_INLINE int64_t fastrange_1(uint64_t x, uint64_t n)
+    { return (int64_t)((uint32_t)x*n >> 32); } // n < 2^32
+
+STC_INLINE int64_t fastrange_2(uint64_t x, uint64_t n) 
+    { return (int64_t)(x & (n - 1)); } // n power of 2.
+
+STC_INLINE uint64_t next_power_of_2(uint64_t n) {
+    n--;
+    n |= n >>  1, n |= n >>  2;
+    n |= n >>  4, n |= n >>  8;
+    n |= n >> 16, n |= n >> 32;
+    return n + 1;
 }
 #endif // CMAP_H_INCLUDED
 
 STC_DEF _cx_self
 _cx_memb(_with_capacity)(const intptr_t cap) {
-    _cx_self h = {0};
-    _cx_memb(_reserve)(&h, cap);
-    return h;
+    _cx_self map = {0};
+    _cx_memb(_reserve)(&map, cap);
+    return map;
 }
 
 STC_INLINE void _cx_memb(_wipe_)(_cx_self* self) {
@@ -356,7 +362,7 @@ STC_DEF chash_bucket
 _cx_memb(_bucket_)(const _cx_self* self, const _cx_keyraw* rkeyptr) {
     const uint64_t _hash = i_hash(rkeyptr);
     intptr_t _cap = self->bucket_count;
-    chash_bucket b = {c_PASTE(fastrange_,i_sizebits)(_hash, (uint64_t)_cap), (uint8_t)(_hash | 0x80)};
+    chash_bucket b = {c_PASTE(fastrange_,i_expandby)(_hash, (uint64_t)_cap), (uint8_t)(_hash | 0x80)};
     const chash_slot* s = self->slot;
     while (s[b.idx].hashx) {
         if (s[b.idx].hashx == b.hashx) {
@@ -414,7 +420,11 @@ _cx_memb(_reserve)(_cx_self* self, const intptr_t _newcap) {
     if (_newcap != self->size && _newcap <= _oldbucks)
         return true;
     intptr_t _newbucks = (intptr_t)((float)_newcap / (i_max_load_factor)) + 4;
+    #if i_expandby == 2
+    _newbucks = (intptr_t)next_power_of_2(_newbucks);
+    #else
     _newbucks |= 1;
+    #endif
     _cx_self m = {
         (_cx_value *)i_malloc(_newbucks*c_sizeof(_cx_value)),
         (chash_slot *)i_calloc(_newbucks + 1, sizeof(chash_slot)),
@@ -450,7 +460,7 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) {
         if (! s[j].hashx)
             break;
         const _cx_keyraw _raw = i_keyto(_i_keyref(d + j));
-        k = (intptr_t)c_PASTE(fastrange_,i_sizebits)(i_hash((&_raw)), (uint64_t)_cap);
+        k = (intptr_t)c_PASTE(fastrange_,i_expandby)(i_hash((&_raw)), (uint64_t)_cap);
         if ((j < i) ^ (k <= i) ^ (k > j)) { // is k outside (i, j]?
             d[i] = d[j];
             s[i] = s[j];
@@ -463,7 +473,7 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) {
 
 #endif // i_implement
 #undef i_max_load_factor
-#undef i_sizebits
+#undef i_expandby
 #undef _i_isset
 #undef _i_ismap
 #undef _i_ishash
diff --git a/misc/benchmarks/shootout_hashmaps.cpp b/misc/benchmarks/shootout_hashmaps.cpp
index 8eb36b34..54680402 100644
--- a/misc/benchmarks/shootout_hashmaps.cpp
+++ b/misc/benchmarks/shootout_hashmaps.cpp
@@ -35,7 +35,6 @@ KHASH_MAP_INIT_INT64(ii, IValue)
 // cmap template expansion
 #define i_key IKey
 #define i_val IValue
-//#define i_sizebits 64 // more than 2.2 billion elements?
 #define i_tag ii
 #define i_max_load_factor MAX_LOAD_FACTOR / 100.0f
 #include <stc/cmap.h>
diff --git a/misc/benchmarks/various/sso_bench.cpp b/misc/benchmarks/various/sso_bench.cpp
index 9841c296..71d123e8 100644
--- a/misc/benchmarks/various/sso_bench.cpp
+++ b/misc/benchmarks/various/sso_bench.cpp
@@ -9,19 +9,32 @@
 #define i_val_str
 #include <stc/cstack.h>
 
-#define i_type StcSet
-#define i_expandby 2
-#define i_val_str
-#include <stc/cset.h>
-
 #include <vector>
 using StdVec = std::vector<std::string>;
 
-//#include "../external/ankerl/robin_hood.h"
-//using StdSet = robin_hood::unordered_flat_set<std::string>;
 
 #include <unordered_set>
-using StdSet = std::unordered_set<std::string>;
+#include "../external/ankerl/robin_hood.h"
+
+struct string_hash {
+  using is_transparent = void;
+  [[nodiscard]] size_t operator()(const char *txt) const {
+    return std::hash<std::string_view>{}(txt);
+  }
+  [[nodiscard]] size_t operator()(std::string_view txt) const {
+    return std::hash<std::string_view>{}(txt);
+  }
+  [[nodiscard]] size_t operator()(const std::string &txt) const {
+    return std::hash<std::string>{}(txt);
+  }
+};
+using StdSet = robin_hood::unordered_flat_set<std::string, string_hash, std::equal_to<>>;
+//using StdSet = std::unordered_set<std::string>;
+
+#define i_type StcSet
+#define i_val_str
+//#define i_hash(txtp) std::hash<std::string_view>{}(*txtp)
+#include <stc/cset.h>
 
 
 static const int BENCHMARK_SIZE = 250000;
@@ -43,28 +56,28 @@ static inline const char* randomString(int strsize) {
 
 
 
-static inline void addRandomString(StdVec& vec, int strsize) {
-    vec.push_back(randomString(strsize));
+static inline void addRandomString(StdVec& vec, const char* str) {
+    vec.push_back(str);
 }
 
-static inline void addRandomString(StcVec& vec, int strsize) {
-    StcVec_emplace(&vec, randomString(strsize));
+static inline void addRandomString(StcVec& vec, const char* str) {
+    StcVec_emplace(&vec, str);
 }
 
-static inline void addRandomString(StdSet& set, int strsize) {
-    set.insert(randomString(strsize));
+static inline void addRandomString(StdSet& set, const char* str) {
+    set.insert(str);
 }
 
-static inline void addRandomString(StcSet& set, int strsize) {
-    StcSet_emplace(&set, randomString(strsize));
+static inline void addRandomString(StcSet& set, const char* str) {
+    StcSet_emplace(&set, str);
 }
 
-static inline bool getRandomString(const StdSet& set, int strsize) {
-    return set.find(randomString(strsize)) != set.end();
+static inline bool getRandomString(const StdSet& set, const char* str) {
+    return set.find(str) != set.end();
 }
 
-static inline bool getRandomString(const StcSet& set, int strsize) {
-    return StcSet_contains(&set, randomString(strsize));
+static inline bool getRandomString(const StcSet& set, const char* str) {
+    return StcSet_contains(&set, str);
 }
 
 
@@ -73,7 +86,7 @@ int benchmark(C& container, const int n, const int strsize) {
     time_point t1 = std::chrono::high_resolution_clock::now();
 
     for (int i = 0; i < n; i++)
-        addRandomString(container, strsize);
+        addRandomString(container, randomString(strsize));
 
     time_point t2 = std::chrono::high_resolution_clock::now();
     const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
@@ -84,12 +97,12 @@ int benchmark(C& container, const int n, const int strsize) {
 template <class C>
 int benchmark_lookup(C& container, const int n, const int strsize) {
     for (int i = 0; i < n; i++)
-        addRandomString(container, strsize);
+        addRandomString(container, randomString(strsize));
 
     time_point t1 = std::chrono::high_resolution_clock::now();
     int found = 0;
     for (int i = 0; i < n; i++)
-        found += (int)getRandomString(container, strsize);
+        found += (int)getRandomString(container, randomString(strsize));
 
     time_point t2 = std::chrono::high_resolution_clock::now();
     const auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
@@ -97,9 +110,9 @@ int benchmark_lookup(C& container, const int n, const int strsize) {
     return (int)duration;
 }
 
-
+#include <time.h>
 int main() {
-    uint64_t seed = 4321;
+    uint64_t seed = time(NULL); // 4321;
     int sum, n;
 
     // VECTOR WITH STRINGS
@@ -154,7 +167,7 @@ int main() {
     csrand(seed);
     sum = 0, n = 0;
     std::cerr << "\nstrsize\tmsecs\tfind: robin_hood::unordered_flat_set<std::string>, size=" << BENCHMARK_SIZE/2 << "\n";
-    for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 4) {
+    for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 2) {
         StdSet set; set.reserve(BENCHMARK_SIZE/2);
         sum += benchmark_lookup(set, BENCHMARK_SIZE/2, strsize), ++n;
         std::cout << '\t' << *set.begin() << '\n';
@@ -164,7 +177,7 @@ int main() {
     csrand(seed);
     sum = 0, n = 0;
     std::cerr << "\nstrsize\tmsecs\tfind: cset<cstr>, size=" << BENCHMARK_SIZE/2 << "\n";
-    for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 4) {
+    for (int strsize = 1; strsize <= MAX_STRING_SIZE; strsize += 2) {
         StcSet set = StcSet_with_capacity(BENCHMARK_SIZE/2);
         sum += benchmark_lookup(set, BENCHMARK_SIZE/2, strsize), ++n;
         std::cout << '\t' << cstr_str(StcSet_begin(&set).ref) << '\n';