From 23ad1fbb91ef3cdddec7e54f3bde79082c2b0e24 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 16 Apr 2021 18:33:24 +0200 Subject: Replaced cmap/cset min_load_factor with shrink_to_fit() method. --- benchmarks/shootout1_cmap.cpp | 10 ++++----- benchmarks/shootout2_cmap.cpp | 2 +- docs/cmap_api.md | 3 ++- docs/cset_api.md | 3 ++- stc/cmap.h | 48 ++++++++++++++++--------------------------- 5 files changed, 28 insertions(+), 38 deletions(-) diff --git a/benchmarks/shootout1_cmap.cpp b/benchmarks/shootout1_cmap.cpp index 7f75a242..d368afa8 100644 --- a/benchmarks/shootout1_cmap.cpp +++ b/benchmarks/shootout1_cmap.cpp @@ -70,7 +70,7 @@ static void ins_and_erase_i(picobench::state& s) static void ins_and_erase_cmap_i(picobench::state& s) { cmap_i map = cmap_i_init(); - cmap_i_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0); + cmap_i_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0); stc64_srandom(seed); picobench::scope scope(s); @@ -90,7 +90,7 @@ static void ins_and_erase_cmap_i(picobench::state& s) static void ins_and_erase_cmap_x(picobench::state& s) { cmap_x map = cmap_x_init(); - cmap_x_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0); + cmap_x_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0); stc64_srandom(seed); picobench::scope scope(s); @@ -140,7 +140,7 @@ static void ins_and_access_cmap_i(picobench::state& s) uint64_t mask = (1ull << s.arg()) - 1; size_t result = 0; cmap_i map = cmap_i_init(); - cmap_i_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0); + cmap_i_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0); stc64_srandom(seed); picobench::scope scope(s); @@ -193,7 +193,7 @@ static void ins_and_access_cmap_s(picobench::state& s) cstr str = cstr_with_size(s.arg(), 'x'); size_t result = 0; cmap_str map = cmap_str_init(); - cmap_str_set_load_factors(&map, 0.0, (int)MaxLoadFactor100 / 100.0); + cmap_str_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0); stc64_srandom(seed); picobench::scope scope(s); @@ -254,7 +254,7 @@ static void iterate_x(picobench::state& s) static void iterate_cmap_x(picobench::state& s) { cmap_x map = cmap_x_init(); - cmap_x_set_load_factors(&map, 0.3, (int)MaxLoadFactor100 / 100.0); + cmap_x_max_load_factor(&map, (int)MaxLoadFactor100 / 100.0); uint64_t K = (1ull << s.arg()) - 1; picobench::scope scope(s); diff --git a/benchmarks/shootout2_cmap.cpp b/benchmarks/shootout2_cmap.cpp index cea7b6ec..7c1595f3 100644 --- a/benchmarks/shootout2_cmap.cpp +++ b/benchmarks/shootout2_cmap.cpp @@ -31,7 +31,7 @@ stc64_t rng; #define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \ - ; cmap_##X##_set_load_factors(&map, 0.0, max_load_factor) + ; cmap_##X##_max_load_factor(&map, max_load_factor) #define CMAP_PUT(X, key, val) cmap_##X##_emplace_or_assign(&map, key, val).ref->second #define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).ref->second #define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 5e8d4d26..2f056479 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -51,8 +51,9 @@ cmap_X cmap_X_with_capacity(size_t cap); cmap_X cmap_X_clone(cmap_x map); void cmap_X_clear(cmap_X* self); -void cmap_X_set_load_factors(cmap_X* self, float min_load, float max_load); // default: 0.15, 0.85 +void cmap_X_max_load_factor(cmap_X* self, float max_load); // default: 0.85 void cmap_X_reserve(cmap_X* self, size_t size); +void cmap_X_shrink_to_fit(cmap_X* self); void cmap_X_swap(cmap_X* a, cmap_X* b); void cmap_X_del(cmap_X* self); // destructor diff --git a/docs/cset_api.md b/docs/cset_api.md index 848c6c63..f28c4714 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -28,8 +28,9 @@ cset_X cset_X_with_capacity(size_t cap); cset_X cset_X_clone(cset_x set); void cset_X_clear(cset_X* self); -void cset_X_set_load_factors(cset_X* self, float min_load, float max_load); // default: 0.15, 0.85 +void cset_X_max_load_factor(cset_X* self, float max_load); // default: 0.85 void cset_X_reserve(cset_X* self, size_t size); +void cset_X_shrink_to_fit(cset_X* self); void cset_X_swap(cset_X* a, cset_X* b); void cset_X_del(cset_X* self); // destructor diff --git a/stc/cmap.h b/stc/cmap.h index 45d5790e..9baefe83 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -134,7 +134,7 @@ int main(void) { #ifndef CMAP_SIZE_T #define CMAP_SIZE_T uint32_t #endif -#define _cmap_inits {NULL, NULL, 0, 0, 0.15f, 0.85f} +#define _cmap_inits {NULL, NULL, 0, 0, 0.85f} typedef struct {size_t idx; uint_fast8_t hx;} chash_bucket_t; \ STC_API uint64_t c_default_hash(const void *data, size_t len); @@ -172,7 +172,6 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) CX##_value_t* table; \ uint8_t* _hashx; \ CX##_size_t size, bucket_count; \ - float min_load_factor; \ float max_load_factor; \ } CX; \ \ @@ -188,19 +187,20 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) STC_API CX CX##_with_capacity(size_t cap); \ STC_API CX CX##_clone(CX map); \ STC_API void CX##_reserve(CX* self, size_t capacity); \ + STC_INLINE void CX##_shrink_to_fit(CX* self) {CX##_reserve(self, self->size);} \ + STC_INLINE void CX##_max_load_factor(CX* self, float ml) {self->max_load_factor = ml;} \ STC_API void CX##_del(CX* self); \ STC_API void CX##_clear(CX* self); \ STC_INLINE bool CX##_empty(CX m) {return m.size == 0;} \ STC_INLINE size_t CX##_size(CX m) {return (size_t) m.size;} \ STC_INLINE size_t CX##_bucket_count(CX map) {return (size_t) map.bucket_count;} \ STC_INLINE size_t CX##_capacity(CX map) \ - {return (size_t) (map.bucket_count*map.max_load_factor);} \ + {return (size_t) (map.bucket_count * map.max_load_factor);} \ STC_INLINE void CX##_swap(CX *map1, CX *map2) {c_swap(CX, *map1, *map2);} \ STC_API CX##_iter_t CX##_find(const CX* self, RawKey rkey); \ STC_INLINE bool CX##_contains(const CX* self, RawKey rkey) \ {return self->size && self->_hashx[CX##_bucket_(self, &rkey).idx];} \ STC_API void CX##_erase_entry(CX* self, CX##_value_t* val); \ - STC_API CX##_iter_t CX##_erase_it(CX* self, CX##_iter_t it); \ \ STC_INLINE CX##_value_t \ CX##_value_clone(CX##_value_t val) { \ @@ -215,12 +215,6 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) MAP_ONLY_##C( mappedDel(&val->second); ) \ } \ \ - STC_INLINE void \ - CX##_set_load_factors(CX* self, float min_load, float max_load) { \ - self->min_load_factor = min_load; \ - self->max_load_factor = max_load; \ - } \ - \ STC_INLINE CX##_result_t \ CX##_emplace(CX* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped)) { \ CX##_result_t res = CX##_insert_entry_(self, rkey); \ @@ -292,6 +286,13 @@ STC_INLINE uint64_t c_default_hash64(const void* data, size_t ignored) chash_bucket_t b = CX##_bucket_(self, &rkey); \ return self->_hashx[b.idx] ? CX##_erase_entry(self, self->table + b.idx), 1 : 0; \ } \ +\ + STC_INLINE CX##_iter_t \ + CX##_erase_it(CX* self, CX##_iter_t it) { \ + CX##_erase_entry(self, it.ref); \ + if (*it._hx == 0) CX##_next(&it); \ + return it; \ + } \ \ _c_implement_chash(CX, C, Key, Mapped, keyEqualsRaw, keyHashRaw, \ mappedDel, mappedFromRaw, mappedToRaw, RawMapped, \ @@ -364,13 +365,10 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ return it; \ } \ \ - STC_INLINE void CX##_reserve_expand_(CX* self) { \ - if (self->size + 1 >= self->bucket_count*self->max_load_factor) \ - CX##_reserve(self, 5 + self->size * 3 / 2); \ - } \ STC_DEF CX##_result_t \ CX##_insert_entry_(CX* self, RawKey rkey) { \ - CX##_reserve_expand_(self); \ + if (self->size + 1 >= (CX##_size_t) (self->bucket_count * self->max_load_factor)) \ + CX##_reserve(self, 8 + self->size * 3 / 2); \ chash_bucket_t b = CX##_bucket_(self, &rkey); \ CX##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ if (res.inserted) { \ @@ -385,7 +383,7 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ CX clone = { \ c_new_2(CX##_value_t, m.bucket_count), \ (uint8_t *) memcpy(c_malloc(m.bucket_count + 1), m._hashx, m.bucket_count + 1), \ - m.size, m.bucket_count, m.min_load_factor, m.max_load_factor \ + m.size, m.bucket_count, m.max_load_factor \ }; \ CX##_value_t *e = m.table, *end = e + m.bucket_count, *dst = clone.table; \ for (uint8_t *hx = m._hashx; e != end; ++hx, ++e, ++dst) \ @@ -397,12 +395,12 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ CX##_reserve(CX* self, size_t newcap) { \ if (newcap < self->size) return; \ size_t oldcap = self->bucket_count; \ - newcap = (size_t) (newcap / self->max_load_factor) | 1; \ + newcap = (size_t) (2 + newcap / self->max_load_factor) | 1; \ CX tmp = { \ c_new_2 (CX##_value_t, newcap), \ (uint8_t *) c_calloc(newcap + 1, sizeof(uint8_t)), \ self->size, (CX##_size_t) newcap, \ - self->min_load_factor, self->max_load_factor \ + self->max_load_factor \ }; \ /* Rehash: */ \ tmp._hashx[newcap] = 0xff; c_swap(CX, *self, tmp); \ @@ -434,18 +432,8 @@ STC_INLINE size_t fastrange_uint64_t(uint64_t x, uint64_t n) \ if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ } \ - hashx[i] = 0, k = --self->size; \ - if (k < cap*self->min_load_factor && k > 512) \ - CX##_reserve(self, k*1.2); \ - } \ -\ - STC_DEF CX##_iter_t \ - CX##_erase_it(CX* self, CX##_iter_t it) { \ - size_t idx = it.ref - self->table; \ - CX##_erase_entry(self, it.ref); \ - it.ref = self->table + idx, it._hx = self->_hashx + idx; \ - if (*it._hx == 0) CX##_next(&it); \ - return it; \ + hashx[i] = 0; \ + --self->size; \ } -- cgit v1.2.3