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

[Timothy Arceri]

On Sat, 2015-02-28 at 13:53 +0100, Thomas Helland wrote:
> 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".

Hi Thomas,

I think the way you implemented the crc32 hash might not be the best fit
for the hash table and might be causing it to not perform as well as it
could. 

_mesa_hash_data despite the name is use only to hash a pointer (except
for two places in the vc4 driver). The way your patch implements the
crc32 hashing looks like its optimised to hash a large amount of data
maximising throughput. However as the table is just hashing a small
amount of data lost of times the code aligning the data and calculating
which intrinsic to use is likely just adding extra overhead for no gain.

I found that an implementation as simple as:

   uint32_t hash = 2166136261ul;
   const uint8_t *bytes = data;

   while (size-- != 0) {
      hash = _mm_crc32_u8(hash, *bytes);
      bytes++;
   }

   return hash;

gave a nice boost over fnv-1a.

Also I should note I didn't bother changing _mesa_hash_string as it
wasn't a bottleneck. I assume you found the same as its not included in
your results table.

It would be interesting to see if simplifying the crc32 implementation
does improve things with your testcase as it did in mine.

> 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
>