[Mesa-dev] [PATCH 0/8] Hash table and hash set reworking

[Thomas Helland]

So here comes my hash-table series mentioned earlier.

So, first of all, there's some issues.
I've been strugling with hitting assertion failures.
The table returns null at times when it apparently should not.
It occurs after patch 1, and is fixed by patch 2.
It also occured when I was tweaking the amount of free space in the 
table.

With this series it should be tweaked and working (apart from patch 1),
but it would be wonderfull if people gave it a run.
I'm suspecting we might have some threading issues,
but I don't really have much experience with threading in C/C++,
so I haven't really debugged it to much.

I did not have any good testcases, so a shader-db run had to do.
If anyone knows of any cpu-bound applications that specifically
hit the hash-table I would be happy to hear about it.

These are results from running shader-db with oprofile after each commit.
Function           master comm1  comm2  comm3  comm4  comm5  comm6  comm7  comm8
mesa_hash_data     2.81   ?      3.09   3.05   2.99   3.23   3.25   3.11   3.12
hash_table_insert  4.28   ?      2.57   2.58   2.58   2.71   2.52   2.52   2.50
hash_table_search  4.59   ?      2.67   2.72   2.70   2.87   2.64   2.64   2.59
set_add            2.69   ?      2.81   2.80   2.70   1.69   1.65   1.74   1.72
set_search         2.75   ?      2.84   2.86   2.74   2.11   2.07   2.08   2.09
runtime            175    ?      170    162    165    157    160    160    164

With regards to cheaper hash-functions:
It seems this is a case of "much pain for no gain".
Looking at this site[1] it looks like most popular
hashes have about the same instruction cost
for smaller amounts of data(10 bytes).
I tried copying the C-code example from the
Wikipedia-article on Murmur-hash 3, and using this.
It did show a speed-up, but not close to what I would expect.

It should also be noted that the crc32c instruction has a latency
of three cycles on older processors[2].
That article also has a different implementation of crc32c
with fallback that I have not tried.

[1] https://github.com/rurban/smhasher
[2] http://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software

Thomas Helland (8):
  util: Change hash_table to use quadratic probing.
  util: Change table size to be power of two
  glsl: Change ir_const_expr to use util/hash_table
  util: Change util/set to use quadratic probing
  util: Change set to use power-of-two sized table
  util: Change size of table to have 23% free
  util: Add murmur3 hashing function
  util: Add header for hardware crc32c

 src/glsl/ir_constant_expression.cpp |  20 +++---
 src/mesa/x86/common_x86.c           |   4 ++
 src/mesa/x86/common_x86_features.h  |   8 +++
 src/util/crc32c_hw.h                |  67 ++++++++++++++++++++
 src/util/hash_table.c               | 120 +++++++++++++++++++-----------------
 src/util/hash_table.h               |  55 ++++++++++++++++-
 src/util/set.c                      |  97 ++++++++++++++---------------
 src/util/set.h                      |   1 -
 8 files changed, 258 insertions(+), 114 deletions(-)
 create mode 100644 src/util/crc32c_hw.h

-- 
2.2.1