[Mesa-dev] [PATCH 1/3] util: Change hash_table to use quadratic probing

[Jason Ekstrand]

On Mon, Mar 30, 2015 at 5:18 PM, Eric Anholt <eric at anholt.net> wrote:
> Thomas Helland <thomashelland90 at gmail.com> writes:
>
>> This should give better cache locality, less memory consumption,
>> less code, and should also be faster since we avoid a modulo operation.
>> Also change table size to be power of two.
>> This gives better performance as we can do bitmasking instead of
>> modulo operations for fitting the hash in the address space.
>> By using the algorithm hash = sh + i/2 + i*i/2
>> we are guaranteed that all retries from the quad probing
>> are distinct, and so should be able to completely fill the table.
>> This passes the test added to exercise a worst case collision scenario.
>> Also, start at size = 16 instead of 4.
>> This should reduce some allocation overhead
>> when constantly using tables larger than 3 entries.
>> The amount of space used before rehash is changed to 70%.
>> This should decrease collisions slightly, leading to better performance.
>
> I've run a test to confirm that the (i + i * i) / 2 probing does
> actually get us unique values, up to a maximum table size of (1 << 31)
> entries.

I sat down with a whiteboard today and also proved it correct.

> The amount-filled-before-rehash should probably be a separate commit,
> since it's increasing memory overhead, and each commit have its own
> performance data justifying it (actually, it looks like that's missing
> From this commit message).  Similarly for start size = 16 instead of 4.
> I wouldn't mind set/hash changes being in the same commits, though.
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>