On Feb 28, 2015 5:05 PM, "Jason Ekstrand" <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > > > On Feb 28, 2015 4:55 AM, "Thomas Helland" <<a href="mailto:thomashelland90@gmail.com">thomashelland90@gmail.com</a>> 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]<a href="https://github.com/rurban/smhasher"> https://github.com/rurban/smhasher</a> > > [2]<a href="http://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software"> http://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software</a> > > > > 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 > ><a href="mailto:mesa-dev@lists.freedesktop.org"> mesa-dev@lists.freedesktop.org</a> > ><a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev"> http://</a><a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">lists.freedesktop.org</a><a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">/mailman/</a><a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">listinfo</a><a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">/</a><a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev">mesa-de</a>v