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

[Eric Anholt]

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.

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 818 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150330/669f9742/attachment.sig>