[Mesa-dev] [PATCH 3/4] util: Change util/set to use quadratic probing

[Connor Abbott]

On Thu, Feb 9, 2017 at 4:16 PM, Jan Ziak <0xe2.0x9a.0x9b at gmail.com> wrote:
> Hello
>
> IMPORTANT NOTE: Using the uint32_t data type, quad_hash*quad_hash will
> overflow as soon as the hash table has more than 2**16=65536=64K
> elements. To enable more than 64K elements in hash table, the data
> types need to be changed to uint64_t - unfortunately uint64_t
> arithmetic operations will slow down the hash table in 32-bit OpenGL
> apps.

This actually doesn't matter, since at the end of the day we only need
the result modulo the table size which is a power of two -- even if
the multiplication overflows, the lowest n bits (if the table size is
2^n) are still correct, so we get the same answer as long as we use at
least n bits.

>
> OPTIMIZATION: All "} while (hash_address != start_hash_address);" can
> be replaced with "} while (1);" assuming that the hash table always
> contains at least several free/unallocated entries. This optimization
> applies both to current mesa-git and to the quadratic probing patch.
> For quadratic probing this optimization works if the statement "values
> of h(k,i) for i in [0,m-1] are all distinct" at
> https://en.wikipedia.org/wiki/Quadratic_probing is correct.
>
> Jan
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev