From 27aa9e5d0eef9f9508163ae7aee8404a1be50a17 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 23 Aug 2026 22:19:10 +0300 Subject: allow specifying growth factor + A bit crude, but allows trading memory for speed. On my machine, MAP_FACTOR Runtime (s) 2 4.94 3 3.00 4 2.77 Further speed increases might be from changing the open hashing to be more efficient, some kind of pseudo-random index generation for example. --- include/conts/map.h | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-) diff --git a/include/conts/map.h b/include/conts/map.h index 571eda2..f617d10 100644 --- a/include/conts/map.h +++ b/include/conts/map.h @@ -18,6 +18,10 @@ #error "Need map name" #endif +#ifndef MAP_FACTOR +#define MAP_FACTOR 2 +#endif + #ifndef MAP_MALLOC #define MAP_MALLOC malloc #endif @@ -130,16 +134,16 @@ static inline void MAP(destroy)(struct MAP_ROOT *root) static inline MAP_VALUE_TYPE *MAP(find_hash)(struct MAP_ROOT *root, MAP_KEY_TYPE key, uint32_t hash) { - for (size_t s = MAP_SPVEC(len)(&root->buf); s >= conts_spvec_size(0); s /= 2) { + for (size_t s = MAP_SPVEC(len)(&root->buf); + s >= conts_spvec_size(0); + s /= MAP_FACTOR) { bool base = s == conts_spvec_size(0); - size_t range = base ? s : s / 2; - size_t offst = base ? 0 : s / 2; + size_t range = base ? s : (MAP_FACTOR - 1) * s / MAP_FACTOR; + size_t offst = base ? 0 : s / MAP_FACTOR; /* linear probing for now */ for (size_t i = 0; i < range; ++i) { - assert(__builtin_popcountll(range) == 1); - size_t idx = (hash + i) & (range - 1); - + size_t idx = (hash + i) % range; struct MAP_NODE *n = MAP_SPVEC(at)(&root->buf, idx + offst); /* unused node means chain must not exist in this range */ @@ -182,8 +186,8 @@ static inline MAP_VALUE_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY_TYPE ke /* grow as needed */ size_t s = MAP_SPVEC(len)(&root->buf); - if (2 * root->n >= s) { - s *= 2; + if (MAP_FACTOR * root->n >= s) { + s *= MAP_FACTOR; if (!MAP_SPVEC(reserve)(&root->buf, s)) return NULL; @@ -194,13 +198,12 @@ static inline MAP_VALUE_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY_TYPE ke /* there must always be at least one free spot */ root->n++; bool base = s == conts_spvec_size(0); - size_t range = base ? s : s / 2; - size_t offst = base ? 0 : s / 2; + size_t range = base ? s : (MAP_FACTOR - 1) * s / MAP_FACTOR; + size_t offst = base ? 0 : s / MAP_FACTOR; /* linear probing for now */ for (size_t i = 0; i < range; ++i) { - assert(__builtin_popcountll(range) == 1); - size_t idx = (hash + i) & (range - 1); + size_t idx = (hash + i) % range; struct MAP_NODE *n = MAP_SPVEC(at)(&root->buf, idx + offst); if (n->used == CONTS_MAP_USED) @@ -291,6 +294,7 @@ static inline size_t MAP(len)(struct MAP_ROOT *root) #undef MAP_ROOT #undef MAP_KEY_TYPE #undef MAP_VALUE_TYPE +#undef MAP_FACTOR #undef MAP_CMP #undef MAP_HASH #undef MAP_NAME -- cgit v1.3