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

Sat Feb 28 12:32:42 PST 2015

On Feb 28, 2015 5:05 PM, "Jason Ekstrand" <jason at jlekstrand.net> wrote:
>
>
> 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'll look into this and see what I can figure out.

>
> > 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 results are from runs with INTEL_USE_NIR=1.
(I should have probably mentioned that.)
For prog_hash_table I think there's some easy gains to be had.
Just changing from separate chaining to a probing implementation
will improve cache-locality greatly, which should be nice.
Right now, with these patches up to the murmur hash patch,
get_node amounts to 5.3 % of hits with oprofile.
I'll look into this once I find the cause of the assertion failures.

> > 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:// <http://lists.freedesktop.org/mailman/listinfo/mesa-dev>
lists.freedesktop.org
<http://lists.freedesktop.org/mailman/listinfo/mesa-dev>/mailman/
<http://lists.freedesktop.org/mailman/listinfo/mesa-dev>listinfo
<http://lists.freedesktop.org/mailman/listinfo/mesa-dev>/
<http://lists.freedesktop.org/mailman/listinfo/mesa-dev>mesa-de
<http://lists.freedesktop.org/mailman/listinfo/mesa-dev>v
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150228/a7b2dd77/attachment-0001.html>