[Mesa-dev] [PATCH 0/4] Hash table and hash set speedup, second take

[Thomas Helland]

So here comes the second version of this series.
I found a way to exercise the bug in the previous series.
This makes the test fail where it previously passed
and we instead ended up hitting assertions in the code.
This is not perfect, and several different tests could
be added, but at least it addresses this issue.

I've squashed together the patches for implementing
quadratic probing and power-of-two table-size,
so that we do not cause breakage in the git-history.
I've changed the quadratic probing algorithm slighty
to conform with the suggestions in the wikipedia article.
Specifically, hash = starthash + i/2 + i*i/2.
This ensures dsitinct values for 0 < i < table-size.
We can therefore achieve 100% fill rate of the table.

When running shader-db under oprofile, with NIR enabled,
hits in hash_table_search and hash_table_insert
is about halved with pow-of-two + quadratic probing.
Increasing the amount of free space some cuts about
15% of the hits in the functions.
These numbers should be taken with a grain of salt
since the amount of oprofile hits in these functions
where less than 2%.
However, cutting that to under 1% still looks like
a win to me. If anyone has a better testcase let me
know and I'll see if I can do some tests.

get_node from the other hash-table implementation
is now the primary resource-hog when compiling shaders.
Oprofile hits this function 13% of the time.
This leads me to believe that revisiting this
implementation can be quite worthwhile.

CC: Jason Ekstrand <jason at jlekstrand.net>
Thomas Helland (4):
  util/tests: Expand collision test for hash table
  util: Change hash_table to use quadratic probing
  util: Change util/set to use quadratic probing
  util: Change size of table to have 23% free

 src/util/hash_table.c                 | 101 +++++++++++++++++----------------
 src/util/hash_table.h                 |   1 -
 src/util/set.c                        | 103 ++++++++++++++++++----------------
 src/util/set.h                        |   1 -
 src/util/tests/hash_table/collision.c |  14 +++++
 5 files changed, 118 insertions(+), 102 deletions(-)

-- 
2.2.1