From 2a50ec5a05a15c022d59ee4e731ef4ab97aed056 Mon Sep 17 00:00:00 2001 From: Tylo Date: Wed, 24 Jun 2020 20:06:12 +0200 Subject: Simplified maxload and shrinklimit. --- examples/benchmark.c | 14 +++++++------- stc/chash.h | 34 ++++++++++++---------------------- 2 files changed, 19 insertions(+), 29 deletions(-) diff --git a/examples/benchmark.c b/examples/benchmark.c index a8c4fb86..5c13cf2e 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -19,20 +19,20 @@ 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_CHash(ii, MAP, int64_t, int64_t, c_emptyDestroy, fibonacci_hash); // c_lowbias32Hash); +declare_CHash(ii, MAP, int64_t, int64_t, c_emptyDestroy, fibonacci_hash); KHASH_MAP_INIT_INT64(ii, uint64_t) size_t seed = 1234; -static const double maxLoadFactor = 0.77; +static const float maxLoadFactor = 0.77f; sfc64_random_t rng; #define SEED(s) rng = sfc64_seed(seed) #define RAND(N) (sfc64_random(&rng) & ((1 << N) - 1)) -#define CMAP_SETUP(tag, Key, Value) CHash_##tag map = chash_init; \ - chash_##tag##_setMaxLoadFactor(&map, maxLoadFactor) +#define CMAP_SETUP(tag, Key, Value) CHash_##tag map = chash_init \ + /* ; chash_##tag##_setLoadFactors(&map, maxLoadFactor, 0.0)*/ #define CMAP_PUT(tag, key, val) chash_##tag##_put(&map, key, val)->value #define CMAP_ERASE(tag, key) chash_##tag##_erase(&map, key) #define CMAP_FIND(tag, key) (chash_##tag##_get(map, key) != NULL) @@ -97,7 +97,7 @@ int rr = RR; erased += M##_ERASE(tag, RAND(rr)); \ } \ difference = clock() - before; \ - printf(#M "(" #tag "): sz: %zu, bucks: %zu, time: %.02f, sum: %zu, erase: %zu\n", \ + printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, sum: %zu, erase: %zu\n", \ M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \ M##_CLEAR(tag); \ } @@ -112,7 +112,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: %zu, time: %.02f, erase %zu\n", \ + printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, erase %zu\n", \ M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ } @@ -129,7 +129,7 @@ int rr = RR; for (size_t i = 0; i < N2; ++i) \ erased += M##_ERASE(tag, RAND(rr)); \ difference = clock() - before; \ - printf(#M "(" #tag "): sz: %zu, bucks: %zu, time: %.02f, erase %zu\n", \ + printf(#M "(" #tag "): sz: %zu, bucks: %8zu, time: %.02f, erase %zu\n", \ M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ M##_CLEAR(tag); \ } diff --git a/stc/chash.h b/stc/chash.h index 7c99c6a1..74ae88a8 100644 --- a/stc/chash.h +++ b/stc/chash.h @@ -53,7 +53,7 @@ int main(void) { #include #include "cdefs.h" -#define chash_init {NULL, NULL, 0, 0, 90, 0} +#define chash_init {NULL, NULL, 0, 0, 0.85f, 0.15f} #define chash_size(map) ((size_t) (map)._size) #define chash_bucketCount(map) ((size_t) (map)._cap) /* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ @@ -123,8 +123,8 @@ typedef struct CHash_##tag { \ CHashEntry_##tag* _table; \ uint8_t* _hashx; \ uint32_t _size, _cap; \ - uint8_t maxLoadPercent; \ - uint8_t shrinkLimitPercent; \ + float maxLoadFactor; \ + float shrinkLimitFactor; \ } CHash_##tag; \ \ typedef struct { \ @@ -145,9 +145,7 @@ chash_##tag##_destroy(CHash_##tag* self); \ STC_API void \ chash_##tag##_clear(CHash_##tag* self); \ STC_API void \ -chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac); \ -STC_API void \ -chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit); \ +chash_##tag##_setLoadFactors(CHash_##tag* self, float maxLoadFactor, float shrinkLimitFactor); \ STC_API size_t \ chash_##tag##_bucket(const CHash_##tag* self, const CHashRawKey_##tag* rawKeyPtr, uint32_t* hxPtr); \ STC_API CHashEntry_##tag* \ @@ -205,17 +203,9 @@ STC_API void chash_##tag##_clear(CHash_##tag* self) { \ } \ \ STC_API void \ -chash_##tag##_setMaxLoadFactor(CHash_##tag* self, double fac) { \ - self->maxLoadPercent = (uint8_t) (fac * 100); \ - if (chash_size(*self) >= chash_bucketCount(*self) * fac) \ - chash_##tag##_reserve(self, (size_t) (chash_size(*self) / fac)); \ -} \ - \ -STC_API void \ -chash_##tag##_setShrinkLimitFactor(CHash_##tag* self, double limit) { \ - self->shrinkLimitPercent = (uint8_t) (limit * 100); \ - if (chash_size(*self) < chash_bucketCount(*self) * limit) \ - chash_##tag##_reserve(self, (size_t) (chash_size(*self) * 1.2 / limit)); \ +chash_##tag##_setLoadFactors(CHash_##tag* self, float maxLoadFactor, float shrinkLimitFactor) { \ + self->maxLoadFactor = maxLoadFactor; \ + self->shrinkLimitFactor = shrinkLimitFactor; \ } \ \ STC_API size_t \ @@ -245,7 +235,7 @@ chash_##tag##_get(const CHash_##tag* self, CHashRawKey_##tag rawKey) { \ } \ \ static inline void _chash_##tag##_reserveExpand(CHash_##tag* self) { \ - if (chash_size(*self) + 1 >= chash_bucketCount(*self) * self->maxLoadPercent * 0.01) \ + if (chash_size(*self) + 1 >= chash_bucketCount(*self) * self->maxLoadFactor) \ chash_##tag##_reserve(self, (size_t) 7 + (1.6 * chash_bucketCount(*self))); \ } \ \ @@ -295,12 +285,12 @@ chash_##tag##_swap(CHash_##tag* a, CHash_##tag* b) { \ STC_API size_t \ chash_##tag##_reserve(CHash_##tag* self, size_t newcap) { \ size_t oldcap = chash_bucketCount(*self); newcap |= 1; \ - if (chash_size(*self) >= newcap * self->maxLoadPercent * 0.01) return oldcap; \ + if (chash_size(*self) >= newcap * self->maxLoadFactor) return oldcap; \ CHash_##tag tmp = { \ c_new_N(CHashEntry_##tag, newcap), \ (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ self->_size, (uint32_t) newcap, \ - self->maxLoadPercent, self->shrinkLimitPercent \ + self->maxLoadFactor, self->shrinkLimitFactor \ }; \ chash_##tag##_swap(self, &tmp); \ \ @@ -347,8 +337,8 @@ chash_##tag##_erase(CHash_##tag* self, CHashRawKey_##tag rawKey) { \ if (chash_size(*self) == 0) \ return false; \ size_t cap = chash_bucketCount(*self); \ - if (chash_size(*self) < cap * self->shrinkLimitPercent * 0.01) \ - chash_##tag##_reserve(self, chash_size(*self) * 120 / self->maxLoadPercent); \ + if (chash_size(*self) < cap * self->shrinkLimitFactor && cap * sizeof(CHashEntry_##tag) > 1024) \ + chash_##tag##_reserve(self, (size_t) (chash_size(*self) * 1.2f / self->maxLoadFactor)); \ uint32_t hx; \ size_t i = chash_##tag##_bucket(self, &rawKey, &hx); \ return chash_##tag##_eraseBucket(self, i); \ -- cgit v1.2.3