From 4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3 Mon Sep 17 00:00:00 2001
From: Sverker Eriksson <sverker@erlang.org>
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')

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