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

[Jason Ekstrand]

On Feb 28, 2015 4:55 AM, "Thomas Helland" <thomashelland90 at gmail.com> 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.

It sounds like we need more unit tests.  The ones we currently have are
pretty sparse (as seen by the double-insertion bug I found recently).
Please figure out why the first patch fails and write a unit test to
trigger that.

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

If you've got an Intel card please also test and give shader-db results
with INTEL_USE_NIR=1.  The NIR code thrashes the hash table/set code more
than anything else in the driver.  NIR also uses different access patterns
than the rest of the driver since most of the hash table lookups outside of
NIR are for glUint  -> object lookups in entry points.

If this is shown to have good improvements, it might be worth looking at
the C++-based hash table we use in the GLSL compiler which doesn't
currently use the implementation in util.

> 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
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150228/e1906324/attachment.html>