From a913490c248f6cfdca3481d81d6d344f4d066cb9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 18 Apr 2023 17:48:47 +0200 Subject: Removed unneeded custom size type in maps and bits.h. Prepared for possible robin-hood impl. Improved sso_bench.c testing string hash - twice as fast as m.ankeln robin impl !?. --- misc/benchmarks/external/emhash/hash_table7.hpp | 44 +++++++++---------------- 1 file changed, 16 insertions(+), 28 deletions(-) (limited to 'misc/benchmarks/external/emhash/hash_table7.hpp') diff --git a/misc/benchmarks/external/emhash/hash_table7.hpp b/misc/benchmarks/external/emhash/hash_table7.hpp index 8f8982f9..c21e145b 100644 --- a/misc/benchmarks/external/emhash/hash_table7.hpp +++ b/misc/benchmarks/external/emhash/hash_table7.hpp @@ -92,7 +92,7 @@ of resizing granularity. Ignoring variance, the expected occurrences of list siz #include "wyhash.h" #endif -#ifdef EMH_KEY +#ifdef EMH_NEW #undef EMH_KEY #undef EMH_VAL #undef EMH_PKV @@ -547,10 +547,10 @@ public: static PairT* alloc_bucket(size_type num_buckets) { -#if _WIN32 - auto* new_pairs = (PairT*)malloc(AllocSize(num_buckets)); -#else +#ifdef EMH_ALLOC auto* new_pairs = (PairT*)aligned_alloc(EMH_MALIGN, AllocSize(num_buckets)); +#else + auto* new_pairs = (PairT*)malloc(AllocSize(num_buckets)); #endif return new_pairs; } @@ -1668,16 +1668,10 @@ private: // key is not in this map. Find a place to put it. size_type find_empty_bucket(const size_type bucket_from, const size_type main_bucket) { -#ifdef EMH_ALIGN64 // only works 64bit - const auto boset = bucket_from % MASK_BIT; - auto* const align = _bitmask + bucket_from / MASK_BIT; - const auto bmask = ((size_t)align[1] << (MASK_BIT - boset)) | (align[0] >> boset); - if (EMH_LIKELY(bmask != 0)) - return bucket_from + CTZ(bmask); -#elif EMH_ITER_SAFE +#if EMH_ITER_SAFE const auto boset = bucket_from % 8; - auto* const start = (uint8_t*)_bitmask + bucket_from / 8; - size_t bmask; memcpy(&bmask, start + 0, sizeof(bmask)); bmask >>= boset;// bmask |= ((size_t)start[8] << (SIZE_BIT - boset)); + auto* const align = (uint8_t*)_bitmask + bucket_from / 8;(void)main_bucket; + size_t bmask; memcpy(&bmask, align + 0, sizeof(bmask)); bmask >>= boset;// bmask |= ((size_t)align[8] << (SIZE_BIT - boset)); if (EMH_LIKELY(bmask != 0)) return bucket_from + CTZ(bmask); #else @@ -1715,21 +1709,15 @@ private: } // key is not in this map. Find a place to put it. - size_type find_unique_empty(const size_type bucket_from, const size_t main_bucket) - { -#ifdef EMH_ALIGN64 - const auto boset = bucket_from % MASK_BIT; - auto* const align = _bitmask + bucket_from / MASK_BIT; - const auto bmask = ((size_t)align[1] << (MASK_BIT - boset)) | (align[0] >> boset); - static_assert(sizeof(size_t) > 4); -#elif EMH_ITER_SAFE + size_type find_unique_empty(const size_type bucket_from) + { const auto boset = bucket_from % 8; - auto* const start = (uint8_t*)_bitmask + bucket_from / 8; - size_t bmask; memcpy(&bmask, start + 0, sizeof(bmask)); bmask >>= boset; -#else - const auto boset = bucket_from % 8; (void)main_bucket; auto* const align = (uint8_t*)_bitmask + bucket_from / 8; - const auto bmask = (*(size_t*)(align) >> boset); //maybe not aligned and warning + +#if EMH_ITER_SAFE + size_t bmask; memcpy(&bmask, align + 0, sizeof(bmask)); bmask >>= boset; +#else + const auto bmask = (*(size_t*)(align) >> boset); //maybe not aligned and warning #endif if (EMH_LIKELY(bmask != 0)) return bucket_from + CTZ(bmask); @@ -1789,12 +1777,12 @@ private: next_bucket = find_last_bucket(next_bucket); //find a new empty and link it to tail - return EMH_BUCKET(_pairs, next_bucket) = find_unique_empty(next_bucket, bucket); + return EMH_BUCKET(_pairs, next_bucket) = find_unique_empty(next_bucket); } #if EMH_INT_HASH static constexpr uint64_t KC = UINT64_C(11400714819323198485); - inline uint64_t hash64(uint64_t key) + inline static uint64_t hash64(uint64_t key) { #if __SIZEOF_INT128__ && EMH_INT_HASH == 1 __uint128_t r = key; r *= KC; -- cgit v1.2.3 From 80df921622c97634aeea31821a61f46885324d9c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Mon, 29 May 2023 20:42:43 +0200 Subject: Update extern benchmark maps. Removed i_expandby in cmap. Always expand by 2 i.e 2^n buckets.. --- include/stc/cmap.h | 22 ++++------------------ misc/benchmarks/external/ankerl/unordered_dense.h | 6 +++--- misc/benchmarks/external/emhash/hash_table7.hpp | 2 +- misc/examples/scheduler.c | 6 +++--- 4 files changed, 11 insertions(+), 25 deletions(-) (limited to 'misc/benchmarks/external/emhash/hash_table7.hpp') diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 4ba6156b..837631f8 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -265,18 +265,7 @@ _cx_memb(_eq)(const _cx_self* self, const _cx_self* other) { #ifndef i_max_load_factor #define i_max_load_factor 0.80f #endif -#ifndef i_expandby - #define i_expandby 2 -#endif - -#ifndef CMAP_H_INCLUDED -STC_INLINE intptr_t fastrange_1(uint64_t x, uint64_t n) - { return (intptr_t)((uint32_t)x*n >> 32); } // n < 2^32 - -STC_INLINE intptr_t fastrange_2(uint64_t x, uint64_t n) - { return (intptr_t)(x & (n - 1)); } // n power of 2. - -#endif // CMAP_H_INCLUDED +#define fastrange_2(x, n) (intptr_t)((x) & (size_t)((n) - 1)) // n power of 2. STC_DEF _cx_iter _cx_memb(_begin)(const _cx_self* self) { _cx_iter it = {self->data, self->data+self->bucket_count, self->slot}; @@ -356,7 +345,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_expandby)(_hash, (uint64_t)_cap), (uint8_t)(_hash | 0x80)}; + chash_bucket b = {fastrange_2(_hash, _cap), (uint8_t)(_hash | 0x80)}; const chash_slot* s = self->slot; while (s[b.idx].hashx) { if (s[b.idx].hashx == b.hashx) { @@ -413,10 +402,8 @@ _cx_memb(_reserve)(_cx_self* self, const intptr_t _newcap) { const intptr_t _oldbucks = self->bucket_count; if (_newcap != self->size && _newcap <= _oldbucks) return true; - intptr_t _newbucks = (intptr_t)((float)_newcap / (i_max_load_factor)) | 1; - #if i_expandby == 2 + intptr_t _newbucks = (intptr_t)((float)_newcap / (i_max_load_factor)) + 4; _newbucks = cnextpow2(_newbucks); - #endif _cx_self m = { (_cx_value *)i_malloc(_newbucks*c_sizeof(_cx_value)), (chash_slot *)i_calloc(_newbucks + 1, sizeof(chash_slot)), @@ -452,7 +439,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_expandby)(i_hash((&_raw)), (uint64_t)_cap); + k = fastrange_2(i_hash((&_raw)), _cap); if ((j < i) ^ (k <= i) ^ (k > j)) { // is k outside (i, j]? d[i] = d[j]; s[i] = s[j]; @@ -464,7 +451,6 @@ _cx_memb(_erase_entry)(_cx_self* self, _cx_value* _val) { } #endif // i_implement #undef i_max_load_factor -#undef i_expandby #undef _i_isset #undef _i_ismap #undef _i_keyref diff --git a/misc/benchmarks/external/ankerl/unordered_dense.h b/misc/benchmarks/external/ankerl/unordered_dense.h index dc4de8ab..b8cacea7 100644 --- a/misc/benchmarks/external/ankerl/unordered_dense.h +++ b/misc/benchmarks/external/ankerl/unordered_dense.h @@ -1,7 +1,7 @@ ///////////////////////// ankerl::unordered_dense::{map, set} ///////////////////////// // A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion. -// Version 4.0.0 +// Version 4.0.1 // https://github.com/martinus/unordered_dense // // Licensed under the MIT License . @@ -32,7 +32,7 @@ // see https://semver.org/spec/v2.0.0.html #define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 4 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes #define ANKERL_UNORDERED_DENSE_VERSION_MINOR 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality -#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes +#define ANKERL_UNORDERED_DENSE_VERSION_PATCH 1 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes // API versioning with inline namespace, see https://www.foonathan.net/2018/11/inline-namespaces/ @@ -1907,7 +1907,7 @@ auto erase_if(ankerl::unordered_dense::detail::table +#include static bool schedule(Scheduler* sched) { struct Task task = *Scheduler_front(sched); - Scheduler_pop_front(sched); + Scheduler_pop(sched); if (!cco_done(&task)) task.resume(&task); @@ -27,7 +27,7 @@ static bool schedule(Scheduler* sched) static bool push_task(const struct Task* task) { - Scheduler_push_back(task->sched, *task); + Scheduler_push(task->sched, *task); return false; } -- cgit v1.2.3