aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-11-13 18:12:32 +0100
committerSverker Eriksson <[email protected]>2015-11-27 19:28:37 +0100
commit4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3 (patch)
tree1ef9971987e1988b4e7f1f7d0771464745f8eb4d /erts/emulator
parent99e6213c0f0cebaa01f8310b6950a814cf4b21ee (diff)
downloadotp-4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3.tar.gz
otp-4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3.tar.bz2
otp-4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3.zip
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.
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/hash.c60
-rw-r--r--erts/emulator/beam/hash.h9
2 files changed, 36 insertions, 33 deletions
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;