diff options
| author | Kimplul <kimi.h.kuparinen@gmail.com> | 2026-08-23 22:19:10 +0300 |
|---|---|---|
| committer | Kimplul <kimi.h.kuparinen@gmail.com> | 2026-08-23 22:19:10 +0300 |
| commit | 27aa9e5d0eef9f9508163ae7aee8404a1be50a17 (patch) | |
| tree | 7648e1e91ea5951ce9c60c719c1a2e4312025983 /include | |
| parent | 917a8737e63007352b23048d45049576ef2c487d (diff) | |
| download | conts-27aa9e5d0eef9f9508163ae7aee8404a1be50a17.tar.gz conts-27aa9e5d0eef9f9508163ae7aee8404a1be50a17.zip | |
allow specifying growth factorv0.0.2
+ 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.
Diffstat (limited to 'include')
| -rw-r--r-- | include/conts/map.h | 28 |
1 files 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 |