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

[Erik Faye-Lund]

On Sat, Feb 28, 2015 at 1:53 PM, Thomas Helland
<thomashelland90 at gmail.com> wrote:
> This should give better cache locality, less memory consumption,
> less code, and should also be faster since we avoid a modulo operation.
>
> This is not the quadratic probing function you see most places.
> They do not accumulate, so you try hash +1, +4, +9, etc.
> My code accumulates; so it becomes hash +1, +5, +14, etc.
> It felt more natural to do it like this.
>
> However, it causes an assertion failure.
> The search function is apparently returning null when it shouldn't.
> This does not get caught by make-check.
> This gets fixed by the next patch.
> ---
>  src/util/hash_table.c | 91 ++++++++++++++++++++++++---------------------------
>  src/util/hash_table.h |  1 -
>  2 files changed, 43 insertions(+), 49 deletions(-)
>
> diff --git a/src/util/hash_table.c b/src/util/hash_table.c
> index 3247593..542f583 100644
> --- a/src/util/hash_table.c
> +++ b/src/util/hash_table.c
> @@ -33,7 +33,7 @@
>   */
>
>  /**
> - * Implements an open-addressing, linear-reprobing hash table.
> + * Implements an open-addressing, quadratic probing hash table.
>   *
>   * For more information, see:
>   *
> @@ -51,44 +51,44 @@
>  static const uint32_t deleted_key_value;
>
>  /**
> - * From Knuth -- a good choice for hash/rehash values is p, p-2 where
> - * p and p-2 are both prime.  These tables are sized to have an extra 10%
> - * free to avoid exponential performance degradation as the hash table fills
> + * From Knuth -- a good choice for hash values is p, where is prime.
> + * These tables are sized to have an extra 10% free to avoid
> + * exponential performance degradation as the hash table fills

"[...] where is prime"? Where what is prime?