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

Sun Mar 15 13:16:52 PDT 2015

2015-03-15 20:04 GMT+01:00 Connor Abbott <cwabbott0 at gmail.com>:
> On Sun, Mar 15, 2015 at 1:50 PM, Thomas Helland
> <thomashelland90 at gmail.com> wrote:
>> 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).
>
> Ok. I think we should keep the getting rid of the table part, because
> having it around seems silly to me when it's just powers of two and
> powers of two times some fraction, but if bumping the size doesn't do
> anything then just leave it and don't waste memory.

OK, I'll let it start at a 4-entry size then.
It's easy enough to change(changing the exponent to start at).

>
>>
>> For some reason I'm not getting the set to work.
>> Are we doing something "special" in NIR with the set?
>
> Not that I know of. Did it break after modifying it to not hard-code
> powers of two? Or after bumping the size? We do rely on multiple
> insertions of the same element not having any additional effect
> though, so if you changed that it won't work.

It broke when going from the original implementation to the
power-of-two + quadratic probing implementation.
It fails both with the hard-coded table and the computed.
It also fails both before and after bumping the size.
I'll check if I might have messed up how it
handles multiple insertions of the same item.

>
>> 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 ............
>
> Ok, it would hit that assert if somehow the use doesn't exist in the
> def's set of all uses. So I guess it's a bug where something didn't
> get inserted correctly, perhaps due to another deletion or something.
> I can't really help much without seeing your code and reproducing the
> assert fail myself, though.
>
>>
>> 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.
>
> :/ I'm on spring break now, so I have more free time, but I know the feeling.
>
>>
>> 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
>>>>
>> _______________________________________________
>> mesa-dev mailing list
>> mesa-dev at lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/mesa-dev