From 99e6213c0f0cebaa01f8310b6950a814cf4b21ee Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 13 Nov 2015 18:04:09 +0100 Subject: erts: Remove dead code erts_hash_merge --- erts/emulator/beam/hash.c | 50 ----------------------------------------------- erts/emulator/beam/hash.h | 2 -- 2 files changed, 52 deletions(-) (limited to 'erts/emulator') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index e0fde337f2..636aafc108 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -280,56 +280,6 @@ void* hash_put(Hash* h, void* tmpl) return (void*) b; } -static void -hash_insert_entry(Hash* h, HashBucket* entry) -{ - HashValue hval = entry->hvalue; - int ix = hval % h->size; - HashBucket* b = h->bucket[ix]; - - while (b != (HashBucket*) 0) { - if ((b->hvalue == hval) && (h->fun.cmp((void*)entry, (void*)b) == 0)) { - abort(); /* Should not happen */ - } - b = b->next; - } - - if (h->bucket[ix] == NULL) - h->used++; - - entry->next = h->bucket[ix]; - h->bucket[ix] = entry; - - if (h->used > h->size80percent) /* rehash at 80% */ - rehash(h, 1); -} - - -/* - * Move all entries in src into dst; empty src. - * Entries in src must not exist in dst. - */ -void -erts_hash_merge(Hash* src, Hash* dst) -{ - int limit = src->size; - HashBucket** bucket = src->bucket; - int i; - - src->used = 0; - for (i = 0; i < limit; i++) { - HashBucket* b = bucket[i]; - HashBucket* next; - - bucket[i] = NULL; - while (b) { - next = b->next; - hash_insert_entry(dst, b); - b = next; - } - } -} - /* ** Erase hash entry return template if erased ** return 0 if not erased diff --git a/erts/emulator/beam/hash.h b/erts/emulator/beam/hash.h index 87fdb360e3..c9e75d7acf 100644 --- a/erts/emulator/beam/hash.h +++ b/erts/emulator/beam/hash.h @@ -93,6 +93,4 @@ void* hash_erase(Hash*, void*); void* hash_remove(Hash*, void*); void hash_foreach(Hash*, void (*func)(void *, void *), void *); -void erts_hash_merge(Hash* src, Hash* dst); - #endif -- cgit v1.2.3 From 4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 13 Nov 2015 18:12:32 +0100 Subject: erts: Redesign grow/shrink thresholds of hash.c 1. Use load factor as indicator, not used buckets. Used buckets is a bad indicator as it makes the situation even worse with a bad hash function. Set grow_threshold to load factor of 160% as it roughly corresponds to the old 80% used bucket limit. 2. Never shrink table below initial size. --- erts/emulator/beam/hash.c | 60 ++++++++++++++++++++++++----------------------- erts/emulator/beam/hash.h | 9 +++---- 2 files changed, 36 insertions(+), 33 deletions(-) (limited to 'erts/emulator') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index 636aafc108..9d247db039 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -66,6 +66,7 @@ void hash_get_info(HashInfo *hi, Hash *h) int i; int max_depth = 0; int objects = 0; + int used = 0; for (i = 0; i < size; i++) { int depth = 0; @@ -76,14 +77,18 @@ void hash_get_info(HashInfo *hi, Hash *h) depth++; b = b->next; } - if (depth > max_depth) - max_depth = depth; + if (depth) { + used++; + if (depth > max_depth) + max_depth = depth; + } } + ASSERT(objects == h->nobjs); hi->name = h->name; hi->size = h->size; - hi->used = h->used; - hi->objs = objects; + hi->used = used; + hi->objs = h->nobjs; hi->depth = max_depth; } @@ -119,6 +124,15 @@ hash_table_sz(Hash *h) } +static ERTS_INLINE void set_thresholds(Hash* h) +{ + h->grow_threshold = (8*h->size)/5; /* grow at 160% load */ + if (h->size_ix > h->min_size_ix) + h->shrink_threshold = h->size / 5; /* shrink at 20% load */ + else + h->shrink_threshold = -1; /* never shrink below inital size */ +} + /* ** init a pre allocated or static hash structure ** and allocate buckets. @@ -145,10 +159,10 @@ Hash* hash_init(ErtsAlcType_t type, Hash* h, char* name, int size, HashFunctions h->name = name; h->fun = fun; h->size = size; - h->size20percent = h->size/5; - h->size80percent = (4*h->size)/5; - h->ix = ix; - h->used = 0; + h->size_ix = ix; + h->min_size_ix = ix; + h->nobjs = 0; + set_thresholds(h); return h; } @@ -199,32 +213,26 @@ static void rehash(Hash* h, int grow) int i; if (grow) { - if ((h_size_table[h->ix+1]) == -1) + if ((h_size_table[h->size_ix+1]) == -1) return; - h->ix++; + h->size_ix++; } else { - if (h->ix == 0) + if (h->size_ix == 0) return; - h->ix--; + h->size_ix--; } - h->size = h_size_table[h->ix]; - h->size20percent = h->size/5; - h->size80percent = (4*h->size)/5; + h->size = h_size_table[h->size_ix]; sz = h->size*sizeof(HashBucket*); new_bucket = (HashBucket **) erts_alloc(h->type, sz); sys_memzero(new_bucket, sz); - h->used = 0; - for (i = 0; i < old_size; i++) { HashBucket* b = h->bucket[i]; while (b != (HashBucket*) 0) { HashBucket* b_next = b->next; int ix = b->hvalue % h->size; - if (new_bucket[ix] == NULL) - h->used++; b->next = new_bucket[ix]; new_bucket[ix] = b; b = b_next; @@ -232,6 +240,7 @@ static void rehash(Hash* h, int grow) } erts_free(h->type, (void *) h->bucket); h->bucket = new_bucket; + set_thresholds(h); } /* @@ -268,14 +277,11 @@ void* hash_put(Hash* h, void* tmpl) } b = (HashBucket*) h->fun.alloc(tmpl); - if (h->bucket[ix] == NULL) - h->used++; - b->hvalue = hval; b->next = h->bucket[ix]; h->bucket[ix] = b; - if (h->used > h->size80percent) /* rehash at 80% */ + if (++h->nobjs > h->grow_threshold) rehash(h, 1); return (void*) b; } @@ -298,9 +304,7 @@ void* hash_erase(Hash* h, void* tmpl) else h->bucket[ix] = b->next; h->fun.free((void*)b); - if (h->bucket[ix] == NULL) - h->used--; - if (h->used < h->size20percent) /* rehash at 20% */ + if (--h->nobjs < h->shrink_threshold) rehash(h, 0); return tmpl; } @@ -331,9 +335,7 @@ hash_remove(Hash *h, void *tmpl) prev->next = b->next; else h->bucket[ix] = b->next; - if (h->bucket[ix] == NULL) - h->used--; - if (h->used < h->size20percent) /* rehash at 20% */ + if (--h->nobjs < h->shrink_threshold) rehash(h, 0); return (void *) b; } diff --git a/erts/emulator/beam/hash.h b/erts/emulator/beam/hash.h index c9e75d7acf..dc7e9c10c5 100644 --- a/erts/emulator/beam/hash.h +++ b/erts/emulator/beam/hash.h @@ -72,10 +72,11 @@ typedef struct hash ErtsAlcType_t type; char* name; /* Table name (static string, for debugging) */ int size; /* Number of slots */ - int size20percent; /* 20 percent of number of slots */ - int size80percent; /* 80 percent of number of slots */ - int ix; /* Size index in size table */ - int used; /* Number of slots used */ + int shrink_threshold; + int grow_threshold; + int size_ix; /* Size index in size table */ + int min_size_ix; /* Never shrink table smaller than this */ + int nobjs; /* Number of objects in table */ HashBucket** bucket; /* Vector of bucket pointers (objects) */ } Hash; -- cgit v1.2.3 From 2afa7580910050b9b087a188215f27553cc0aba3 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 30 Nov 2015 12:08:15 +0100 Subject: erts: Remove unused include files from hash.c Note that hash.c is quite "clean" from Erlang stuff and is used by erl_child_setup as well. --- erts/emulator/beam/hash.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'erts/emulator') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index 9d247db039..75d091d11c 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -27,8 +27,6 @@ #endif #include "sys.h" -#include "erl_vm.h" -#include "global.h" #include "hash.h" /* -- cgit v1.2.3