From bed7ad8387b9dc99c675cd1e13984a337fecd1c7 Mon Sep 17 00:00:00 2001 From: Quentin Young Date: Wed, 9 Aug 2017 11:57:13 -0400 Subject: [PATCH] lib: use load factor as hash expansion trigger Previous strategy was to resize the hash table when the length of any one bucket exceeded a certain size, with some logic for intelligently stopping resizes when the gains from doing so weren't sufficient. While this was a good idea that attempted to optimize both space and lookup time, unfortunately under transient degenerate conditions this led to some issues with the tables not resizing when they should have, harming performance. The resizing restriction was lifted, but this had the result of exacerbating degenerate behavior and caused out of memory conditions. This patch changes the hash expansion criterion to be based on the number of elements in the table. Once the # of elements in the table exceeds the number of buckets, the table size is doubled. While the space efficiency of this method decreases relative to the perfectness of the hash function, at least this strategy puts the table performance squarely in the hands of the hash function. Signed-off-by: Quentin Young --- lib/hash.c | 5 +---- lib/hash.h | 5 +++-- 2 files changed, 4 insertions(+), 6 deletions(-) diff --git a/lib/hash.c b/lib/hash.c index 801871f839..66341cf2f1 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -141,18 +141,15 @@ void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *)) unsigned int key; unsigned int index; void *newdata; - unsigned int len; struct hash_backet *backet; key = (*hash->hash_key)(data); index = key & (hash->size - 1); - len = 0; for (backet = hash->index[index]; backet != NULL; backet = backet->next) { if (backet->key == key && (*hash->hash_cmp)(backet->data, data)) return backet->data; - ++len; } if (alloc_func) { @@ -160,7 +157,7 @@ void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *)) if (newdata == NULL) return NULL; - if (len > HASH_THRESHOLD) { + if (HASH_THRESHOLD(hash->count + 1, hash->size)) { hash_expand(hash); index = key & (hash->size - 1); } diff --git a/lib/hash.h b/lib/hash.h index 236abbbd6a..b6fe27e257 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -28,8 +28,9 @@ DECLARE_MTYPE(HASH) DECLARE_MTYPE(HASH_BACKET) /* Default hash table size. */ -#define HASH_INITIAL_SIZE 256 /* initial number of backets. */ -#define HASH_THRESHOLD 10 /* expand when backet. */ +#define HASH_INITIAL_SIZE 256 +/* Expansion threshold */ +#define HASH_THRESHOLD(used, size) ((used) > (size)) #define HASHWALK_CONTINUE 0 #define HASHWALK_ABORT -1 -- 2.39.5