From 677337a982227818a88288d05f535b6a1f1c24ac Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 26 Jul 2020 14:42:11 +0200 Subject: Replaced lowBiasHash with fibonacciHash32 / fibonacciHash64. Added __init(void) function. --- examples/benchmark.c | 34 +++++++++++++++------------------- stc/cdefs.h | 21 ++++++++++----------- stc/clist.h | 7 +++---- stc/cmap.h | 8 +++----- stc/cstr.h | 8 ++------ stc/cvec.h | 5 ++--- 6 files changed, 35 insertions(+), 48 deletions(-) diff --git a/examples/benchmark.c b/examples/benchmark.c index 3c1b49bb..65eef03f 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -14,16 +14,11 @@ // Visual Studio: compile with -TP to force C++: cl -TP -EHsc -O2 benchmark.c - -static inline uint32_t fibonacci_hash(const void* data, size_t len) { - const uint64_t key = *(const uint64_t *) data; - return (uint32_t) (key * 11400714819323198485llu); -} -declare_CMap(ii, int64_t, int64_t, c_defaultDestroy, c_defaultEquals, fibonacci_hash); +declare_CMap(ii, int64_t, int64_t, c_defaultDestroy, c_defaultEquals, c_fibonacciHash64); KHASH_MAP_INIT_INT64(ii, uint64_t) -size_t seed = 1234; +size_t seed; static const float maxLoadFactor = 0.77f; crandom64_t rng; @@ -32,7 +27,7 @@ crandom64_t rng; #define CMAP_SETUP(tag, Key, Value) CMap_##tag map = cmap_init \ - /* ; cmap_##tag##_setLoadFactors(&map, maxLoadFactor, 0.0)*/ + ; cmap_##tag##_setLoadFactors(&map, maxLoadFactor, 0.0) #define CMAP_PUT(tag, key, val) cmap_##tag##_put(&map, key, val)->value #define CMAP_ERASE(tag, key) cmap_##tag##_erase(&map, key) #define CMAP_FIND(tag, key) (cmap_##tag##_find(map, key) != NULL) @@ -80,8 +75,9 @@ crandom64_t rng; #define RMAP_BUCKETS(tag) map.bucket_count() #define RMAP_CLEAR(tag) map.clear() -const size_t N1 = 7000000; -const size_t N2 = 10000000; +const size_t N1 = 10000000 * 5; +const size_t N2 = 10000000 * 5; +const size_t N3 = 10000000 * 10; #define RR 20 int rr = RR; @@ -97,7 +93,7 @@ int rr = RR; erased += M##_ERASE(tag, RAND(rr)); \ } \ difference = clock() - before; \ - printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, sum: %zu, erase: %zu\n", \ + printf(#M ": size: %zu, buckets: %8zu, time: %.02f, sum: %zu, erased %zu\n", \ M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \ M##_CLEAR(tag); \ } @@ -112,7 +108,7 @@ int rr = RR; for (size_t i = 0; i < N2; ++i) \ erased += M##_ERASE(tag, i); \ difference = clock() - before; \ - printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, erase %zu\n", \ + printf(#M ": size: %zu, buckets: %8zu, time: %.02f, erased %zu\n", \ M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ } @@ -123,13 +119,13 @@ int rr = RR; size_t erased = 0; \ clock_t difference, before = clock(); \ SEED(seed); \ - for (size_t i = 0; i < N2; ++i) \ + for (size_t i = 0; i < N3; ++i) \ M##_PUT(tag, RAND(rr), i); \ SEED(seed); \ - for (size_t i = 0; i < N2; ++i) \ + for (size_t i = 0; i < N3; ++i) \ erased += M##_ERASE(tag, RAND(rr)); \ difference = clock() - before; \ - printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, erase %zu\n", \ + printf(#M ": size: %zu, buckets: %8zu, time: %.02f, erased %zu\n", \ M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ } @@ -139,8 +135,8 @@ int main(int argc, char* argv[]) { rr = argc == 2 ? atoi(argv[1]) : RR; seed = time(NULL); - printf("\nRandom keys are in range [0, 2^%d):\n", rr); - printf("\nmap: %zu repeats of Insert random key + remove a different random key:\n", N1); + printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); + printf("\nUnordered maps: %zu repeats of Insert random key + try to remove a random key:\n", N1); MAP_TEST1(CMAP, ii) MAP_TEST1(KMAP, ii) #ifdef __cplusplus @@ -150,7 +146,7 @@ int main(int argc, char* argv[]) MAP_TEST1(RMAP, ii) #endif - printf("\nmap: Insert %zu index keys, then remove them in same order:\n", N2); + printf("\nUnordered maps: Insert %zu index keys, then remove them in same order:\n", N2); MAP_TEST2(CMAP, ii) MAP_TEST2(KMAP, ii) #ifdef __cplusplus @@ -160,7 +156,7 @@ int main(int argc, char* argv[]) MAP_TEST2(RMAP, ii) #endif - printf("\nmap: Insert %zu random keys, then remove them in same order:\n", N2); + printf("\nUnordered maps: Insert %zu random keys, then remove them in same order:\n", N3); MAP_TEST3(CMAP, ii) MAP_TEST3(KMAP, ii) #ifdef __cplusplus diff --git a/stc/cdefs.h b/stc/cdefs.h index b33b9186..8e536438 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -38,12 +38,8 @@ #if defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define STC_API extern -#define STC_VARDECL extern -#define STC_VARDEF #else #define STC_API STC_INLINE -#define STC_VARDECL static -#define STC_VARDEF static #endif /* Macro overloading feature support: https://rextester.com/ONP80107 */ @@ -97,16 +93,19 @@ static inline uint32_t c_defaultHash(const void *data, size_t len) { return x; } -/* https://nullprogram.com/blog/2018/07/31/: assume len positive multiple of 4 */ +/* https://programmingpraxis.com/2018/06/19/fibonacci-hash */ /* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ -static inline uint32_t c_lowbias32Hash(const void *data, size_t len) { +static inline uint32_t c_fibonacciHash32(const void* data, size_t len) { const volatile uint32_t *key = (const uint32_t *) data; - uint32_t x = *key; - do { - x ^= *key++ >> 16; - x *= UINT32_C(0x7feb352d); - } while (len -= 4); + uint32_t x = *key++ * 2654435769u; + while (len -= 4) x ^= *key++ * 2654435769u; return x; } +static inline uint32_t c_fibonacciHash64(const void* data, size_t len) { + const volatile uint64_t *key = (const uint64_t *) data; + uint64_t x = *key++ * 11400714819323198485ull; + while (len -= 8) x ^= *key++ * 11400714819323198485ull; + return (uint32_t) (x >> 13); +} #endif diff --git a/stc/clist.h b/stc/clist.h index 85c2d9b9..026becff 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -91,7 +91,8 @@ \ declare_CListTypes(tag, Value); \ \ - STC_VARDECL CList_##tag clist_##tag##_init; \ + STC_INLINE CList_##tag \ + clist_##tag##_init(void) {CList_##tag x = clist_init; return x;} \ STC_API void \ clist_##tag##_destroy(CList_##tag* self); \ STC_INLINE void \ @@ -149,9 +150,7 @@ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_CList_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \ - \ - STC_VARDEF CList_##tag clist_##tag##_init = clist_init; \ - \ + \ STC_API void \ clist_##tag##_destroy(CList_##tag* self) { \ while (self->last) \ diff --git a/stc/cmap.h b/stc/cmap.h index 0b5ae2a5..21f24862 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -158,7 +158,8 @@ typedef struct { \ uint8_t* _hx; \ } CType##Iter_##tag, ctype##_##tag##_iter_t; \ \ -STC_VARDECL CType##_##tag ctype##_##tag##_init; \ +STC_INLINE CType##_##tag \ +ctype##_##tag##_init(void) {CType##_##tag x = cmap_init; return x;} \ STC_API CType##_##tag \ ctype##_##tag##_make(size_t initialSize); \ STC_API void \ @@ -203,10 +204,7 @@ typedef Value CType##Value_##tag, ctype##_##tag##_value_t #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_CHASH(tag, CType, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ keyDestroy, RawKey, keyGetRaw, keyInitRaw) \ - \ -STC_VARDEF CType##_##tag ctype##_##tag##_init = cmap_init; \ - \ -STC_API CType##_##tag \ + STC_API CType##_##tag \ ctype##_##tag##_make(size_t initialSize) { \ CType##_##tag h = ctype##_init; \ ctype##_##tag##_reserve(&h, initialSize); \ diff --git a/stc/cstr.h b/stc/cstr.h index 4cb1fe60..972e29b6 100644 --- a/stc/cstr.h +++ b/stc/cstr.h @@ -35,18 +35,16 @@ typedef struct CStr { char* str; } CStr; -static size_t _cstr_nullrep[] = {0, 0, 0}; #define _cstr_rep(self) (((size_t *) (self)->str) - 2) #define _cstr_size(s) ((size_t *) (s).str)[-2] #define _cstr_mem(cap) (sizeof(size_t) * (3 + (cap)/sizeof(size_t))) +static size_t _cstr_nullrep[] = {0, 0, 0}; +static CStr cstr_init = {(char* ) &_cstr_nullrep[2]}; #define cstr_size(s) ((const size_t *) (s).str)[-2] #define cstr_capacity(s) ((const size_t *) (s).str)[-1] #define cstr_npos ((size_t) (-1)) - -STC_VARDECL CStr cstr_init; - STC_API CStr cstr_makeN(const char* str, size_t len); STC_API CStr @@ -198,8 +196,6 @@ STC_INLINE uint32_t cstr_hashRaw(const char* const* sPtr, size_t ignored) { #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -STC_VARDEF CStr cstr_init = {(char* ) &_cstr_nullrep[2]}; - STC_API void cstr_reserve(CStr* self, size_t cap) { size_t len = cstr_size(*self), oldcap = cstr_capacity(*self); diff --git a/stc/cvec.h b/stc/cvec.h index 5f393223..74153455 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -51,7 +51,8 @@ typedef struct CVec_##tag { \ Value* data; \ } CVec_##tag; \ \ -STC_VARDECL CVec_##tag cvec_##tag##_init; \ +STC_INLINE CVec_##tag \ +cvec_##tag##_init(void) {CVec_##tag x = cvec_init; return x;} \ STC_API CVec_##tag \ cvec_##tag##_make(size_t size, Value null); \ STC_API void \ @@ -113,8 +114,6 @@ typedef RawValue CVecRawValue_##tag #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) #define implement_CVec_6(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueGetRaw) \ \ -STC_VARDEF CVec_##tag cvec_##tag##_init = cvec_init; \ - \ STC_API CVec_##tag \ cvec_##tag##_make(size_t size, Value null) { \ CVec_##tag vec = cvec_init; \ -- cgit v1.2.3