lib: Remove expansion of hash table

The hash code has the idea of stopping expanding
the hash table when certain criteria are set.
With the recent addition of `show hashtable`
we can now see that when we have a full internet
feed we've stopped expanding the table at 1k
buckets.  This results in some serious performance
issues at scale.

Since we now have the ability to see the statistics
on a hash table, let's allow it to expand.  Doing
so on a full feed showed this:

before:
   Hash table          |  Buckets   Entries   Empty   LF        SD      FLF       SD
 ----------------------+----------------------------------------------------------------
   route table hash    |  1024      1187579   0%      1159.75   34.06   1159.75   35.08
   route table hash    |  32768     76208     10%     2.33      2.80    2.58      4.03
   route table hash    |  1024      1187572   0%      1159.74   34.06   1159.74   35.08
   route table hash    |  2048      76205     0%      37.21     6.13    37.21     7.29

Showing hash table statistics for BGP
-------------------------------------

   Hash table         |  Buckets   Entries   Empty   LF       SD      FLF      SD
 ---------------------+--------------------------------------------------------------
   BGP Attributes     |  131072    251229    15%     1.92     2.48    2.25     3.33
   route table hash   |  4096      1187572   0%      289.93   17.03   289.93   17.87
   route table hash   |  32768     76205     10%     2.33     2.90    2.58     4.21

After:

   Hash table          |  Buckets   Entries   Empty   LF     SD     FLF    SD
 ----------------------+--------------------------------------------------------
   route table hash    |  1048576   1187349   32%     1.13   2.57   1.67   3.16
   route table hash    |  32768     76195     10%     2.33   2.81   2.58   4.03
   route table hash    |  1048576   1187342   32%     1.13   2.58   1.67   3.16
   route table hash    |  32768     76192     10%     2.33   2.68   2.58   3.81

Showing hash table statistics for BGP
-------------------------------------

   Hash table         |  Buckets   Entries   Empty   LF     SD     FLF    SD
 ---------------------+--------------------------------------------------------
   BGP Attributes     |  131072    251222    15%     1.92   2.64   2.25   3.58
   route table hash   |  1048576   1187342   32%     1.13   2.52   1.67   3.07
   route table hash   |  32768     76192     10%     2.33   2.86   2.58   4.12

We should see some significant performance improvements across the board
for full feeds.

Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>

1 files changed, 2 insertions, 19 deletions

diff --git a/lib/hash.c b/lib/hash.c
index 7adbd908d..a7714f156 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -49,7 +49,6 @@ struct hash *hash_create_size(unsigned int size,
 	hash->index =
 		XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * size);
 	hash->size = size;
-	hash->no_expand = 0;
 	hash->hash_key = hash_key;
 	hash->hash_cmp = hash_cmp;
 	hash->count = 0;
@@ -91,7 +90,7 @@ void *hash_alloc_intern(void *arg)
 /* Expand hash if the chain length exceeds the threshold. */
 static void hash_expand(struct hash *hash)
 {
-	unsigned int i, new_size, losers;
+	unsigned int i, new_size;
 	struct hash_backet *hb, *hbnext, **new_index;
 
 	new_size = hash->size * 2;
@@ -128,22 +127,6 @@ static void hash_expand(struct hash *hash)
 	XFREE(MTYPE_HASH_INDEX, hash->index);
 	hash->size = new_size;
 	hash->index = new_index;
-
-	/* Ideally, new index should have chains half as long as the original.
-	 * If expansion didn't help, then not worth expanding again,
-	 * the problem is the hash function. */
-	losers = 0;
-	for (i = 0; i < hash->size; i++) {
-		unsigned int len = hash->index[i] ? hash->index[i]->len : 0;
-
-		if (len > HASH_THRESHOLD / 2)
-			++losers;
-		if (len >= HASH_THRESHOLD)
-			hash->no_expand = 1;
-	}
-
-	if (losers > hash->count / 2)
-		hash->no_expand = 1;
 }
 
 /* Lookup and return hash backet in hash.  If there is no
@@ -173,7 +156,7 @@ void *hash_get(struct hash *hash, void *data, void *(*alloc_func)(void *))
 		if (newdata == NULL)
 			return NULL;
 
-		if (len > HASH_THRESHOLD && !hash->no_expand) {
+		if (len > HASH_THRESHOLD) {
 			hash_expand(hash);
 			index = key & (hash->size - 1);
 		}