]> git.puffer.fish Git - mirror/frr.git/commit
lib: use load factor as hash expansion trigger 940/head
authorQuentin Young <qlyoung@cumulusnetworks.com>
Wed, 9 Aug 2017 15:57:13 +0000 (11:57 -0400)
committerQuentin Young <qlyoung@cumulusnetworks.com>
Wed, 9 Aug 2017 17:53:11 +0000 (13:53 -0400)
commitbed7ad8387b9dc99c675cd1e13984a337fecd1c7
treeec771b68a08e1a408a271644b7568b11634060c1
parentd1783281630a888a61a24299ae73c973588ff481
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 <qlyoung@cumulusnetworks.com>
lib/hash.c
lib/hash.h