On Sun, 4 Sep 2011, Henrik Grubbstr?m (Lysator) @ Pike (-) developers forum wrote:
No. It's comparing the hashtable size with the minimum required number of keypairs, these two usually differ by a factor of AVG_LINK_LENGTH.
One optimization we should probably do is to check if the mapping size is already at the minimum before rehashing to a smaller one. Currently it seems like it would rehash to the same size when removing an element from a mapping thats already at the minimum.
Here is a patch. Maybe someone can ack this, before I push it.
diff --git a/src/mapping.c b/src/mapping.c index def183a..ef693b2 100644 --- a/src/mapping.c +++ b/src/mapping.c @@ -27,6 +27,7 @@
#define AVG_LINK_LENGTH 4 #define MIN_LINK_LENGTH 1 +#define MIN_HASHSIZE 32 #define MAP_SLOTS(X) ((X)?((X)+((X)>>4)+8):0)
struct mapping *first_mapping; @@ -182,7 +183,7 @@ static void init_mapping(struct mapping *m, if(size) { hashsize = size / AVG_LINK_LENGTH + 1; - hashsize = (hashsize <= 32) ? 32 : find_next_power(hashsize); + hashsize = (hashsize <= MIN_HASHSIZE) ? MIN_HASHSIZE : find_next_power(hashsize);
e=MAPPING_DATA_SIZE(hashsize, size);
@@ -1017,7 +1018,7 @@ PMOD_EXPORT void map_delete_no_free(struct mapping *m, m->debug_size--; #endif
- if(md->size < (md->hashsize + 1) * MIN_LINK_LENGTH) + if((md->hashsize > MIN_HASHSIZE) && (md->size < (md->hashsize + 1) * MIN_LINK_LENGTH)) { debug_malloc_touch(m); rehash(m, MAP_SLOTS(m->data->size)); @@ -1092,7 +1093,7 @@ PMOD_EXPORT void check_mapping_for_destruct(struct mapping *m) md->val_types = val_types; md->ind_types = ind_types;
- if(MAP_SLOTS(md->size) < md->hashsize * MIN_LINK_LENGTH) + if((md->hashsize > MIN_HASHSIZE) && (MAP_SLOTS(md->size) < md->hashsize * MIN_LINK_LENGTH)) { debug_malloc_touch(m); rehash(m, MAP_SLOTS(md->size));