[Mesa-dev] [PATCH 0/4] Hash table and hash set speedup, second take

[Thomas Helland]

2015-03-15 16:47 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
> 2015-03-13 23:37 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
>> So here comes the second version of this series.
>> I found a way to exercise the bug in the previous series.
>> This makes the test fail where it previously passed
>> and we instead ended up hitting assertions in the code.
>> This is not perfect, and several different tests could
>> be added, but at least it addresses this issue.
>>
>> I've squashed together the patches for implementing
>> quadratic probing and power-of-two table-size,
>> so that we do not cause breakage in the git-history.
>> I've changed the quadratic probing algorithm slighty
>> to conform with the suggestions in the wikipedia article.
>> Specifically, hash = starthash + i/2 + i*i/2.
>> This ensures dsitinct values for 0 < i < table-size.
>> We can therefore achieve 100% fill rate of the table.
>>
>> When running shader-db under oprofile, with NIR enabled,
>> hits in hash_table_search and hash_table_insert
>> is about halved with pow-of-two + quadratic probing.
>> Increasing the amount of free space some cuts about
>> 15% of the hits in the functions.
>> These numbers should be taken with a grain of salt
>> since the amount of oprofile hits in these functions
>> where less than 2%.
>> However, cutting that to under 1% still looks like
>> a win to me. If anyone has a better testcase let me
>> know and I'll see if I can do some tests.
>
> Forget this part. It is completely wrong.
> I brainfarted and forgot to enable NIR.
> I'll post some statistics ASAP, along with an updated
> patch for the set. It is somehow broken, and only used
> in NIR, so it didn't show up when I was testing due to
> the aforementioned lack of brainfunctioning.
>
> I'll look into getting rid of the hash_sizes table while I'm at it.

So I managed to get rid of the size-table, and compute
the size "on the fly" instead(simple bitshift operation).
I also upped the minimum size of the table to 16.
This works for the hash_table, but doesn't really give noticeable
improvements to anything I can easily measure (with operf).

For some reason I'm not getting the set to work.
Are we doing something "special" in NIR with the set?
I've looked over the code multiple times and it is
exactly the same as it's hash_table counterpart.
However, the hash_table works (as far as I can tell).
If I don't run shader-db with NIR it seems to work, but
there are not that many uses outside of NIR.

One of the asserts I'm hitting is this in
nir_validate.c   validate_ssa_src   line 155

   if (state->instr) {
      _mesa_set_add(def_state->uses, state->instr);

      assert(_mesa_set_search(def->uses, state->instr));
   } else ............

For those of you who are working in this area, any ideas?
It will probably be until easter before I get the time to look
into this thoroughly, as school is a PITA atm, so thought
I'd put this out there.

Regards,
Thomas

>
>>
>> get_node from the other hash-table implementation
>> is now the primary resource-hog when compiling shaders.
>> Oprofile hits this function 13% of the time.
>> This leads me to believe that revisiting this
>> implementation can be quite worthwhile.
>>
>> CC: Jason Ekstrand <jason at jlekstrand.net>
>> Thomas Helland (4):
>>   util/tests: Expand collision test for hash table
>>   util: Change hash_table to use quadratic probing
>>   util: Change util/set to use quadratic probing
>>   util: Change size of table to have 23% free
>>
>>  src/util/hash_table.c                 | 101 +++++++++++++++++----------------
>>  src/util/hash_table.h                 |   1 -
>>  src/util/set.c                        | 103 ++++++++++++++++++----------------
>>  src/util/set.h                        |   1 -
>>  src/util/tests/hash_table/collision.c |  14 +++++
>>  5 files changed, 118 insertions(+), 102 deletions(-)
>>
>> --
>> 2.2.1
>>