[Mesa-dev] [PATCH 0/4] Hash table and hash set speedup, second take
Jason Ekstrand
jason at jlekstrand.net
Sun Mar 15 17:15:12 PDT 2015
On Sun, Mar 15, 2015 at 1:16 PM, Thomas Helland
<thomashelland90 at gmail.com> wrote:
> 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.
My best guess would be that you made a change to one place in the code
but not another. Between the set and table, there are either 4 or 6
places where the exact same table-walking logic is present and it's
easy to make a mistake in one of them. The first thing I'd do is just
double-check that.
Another thing you can do is write a hash-table "validator" that goes
through the table and checks a bunch of invariants such as "no element
exists twice", "the number of dead/valid elements is the same as
what's recorded", etc. and run that after every insert/remove. It'll
really slow things down (It's probably O(n^2)) but it can help you
find the bug exactly when it happens so you can identify the exact
state of the hash table then instead of trying to dissect it later.
Beyond that? Sorry buddy, it's a pain. Hash table bugs are in a
class of their own when it comes to being annoying to track down.
It's worth noting that, while NIR thrashes on the hash sets pretty
hard, it's also fairly deterministic about it. It's not 100%
deterministic because it keys off of pointers that get malloc'd so
they do change from run to run. However the pattern of inserts and
removals (i.e. +A +B +C +A -B +D +B etc) is the same just with
possibly different actual keys/hashes. Therefore, you can probably
find a single shader that does it fairly consistently and just look at
that.
Another thing you can do to make hitting these bugs more likely is to
turn on GCM. Just add nir_opt_gcm to the list of optimizations in
brw_fs.cpp right after nir_opt_dce. (We don't have it turned on right
now because it actually hurts code-generation slightly.) It'll make
the shader-db results just a bit worse, but GCM thrashes the sets even
harder. It's when I was writing GCM that I first noticed (and had to
fix) the hash set double-insert bug that I've mentioned to you before.
Hope that helps,
--Jason
>>
>>> 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
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list