[Mesa-dev] [PATCH 0/8] Hash table and hash set reworking
jason at jlekstrand.net
Sat Feb 28 08:05:03 PST 2015
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
> 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
> 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
> mesa_hash_data 2.81 ? 3.09 3.05 2.99 3.23 3.25 3.11
> hash_table_insert 4.28 ? 2.57 2.58 2.58 2.71 2.52 2.52
> hash_table_search 4.59 ? 2.67 2.72 2.70 2.87 2.64 2.64
> set_add 2.69 ? 2.81 2.80 2.70 1.69 1.65 1.74
> set_search 2.75 ? 2.84 2.86 2.74 2.11 2.07 2.08
> runtime 175 ? 170 162 165 157 160 160
> With regards to cheaper hash-functions:
> It seems this is a case of "much pain for no gain".
> Looking at this site 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.
> That article also has a different implementation of crc32c
> with fallback that I have not tried.
>  https://github.com/rurban/smhasher
> 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
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the mesa-dev