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". 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@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
