Re: [PATCH for 8.1] intel_iommu: refine iotlb hash calculation

[Peter Maydell]

On Wed, 12 Apr 2023 at 09:40, Alex Bennée <alex.bennee@linaro.org> wrote:
> Peter Maydell <peter.maydell@linaro.org> writes:
> > Whoops, hadn't noticed that guint type... (glib's
> > g_int64_hash()'s approach to this is to XOR the top
> > 32 bits with the bottom 32 bits to produce the 32-bit
> > hash value.)
>
> This is less of a hash and more just concatting a bunch of fields. BTW
> if the glib built-in hash isn't suitable we also have the qemu_xxhash()
> functions which claim a good distribution of values and we use in a
> number of places throughout the code.

Is that really necessary? If glib doesn't do anything complex
for "my keys are just integers" I don't see that we need to
do anything complex for "my keys are a handful of integers".
glib does do a bit on its end to counteract suboptimal hash functions:

https://github.com/GNOME/glib/blob/main/glib/ghash.c#L429

static inline guint
g_hash_table_hash_to_index (GHashTable *hash_table, guint hash)
{
  /* Multiply the hash by a small prime before applying the modulo. This
   * prevents the table from becoming densely packed, even with a poor hash
   * function. A densely packed table would have poor performance on
   * workloads with many failed lookups or a high degree of churn. */
  return (hash * 11) % hash_table->mod;
}

I figure if glib thought that users of hash tables should be
doing more complex stuff then they would (a) provide helpers
for that and (b) call it out in the docs. They don't do either.

thanks
-- PMM