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

[Alex Bennée]

Peter Maydell <peter.maydell@linaro.org> writes:

> 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.

Ahh I didn't realise glib was adding extra steps (although I guess it
makes sense if it is resizing its tables) or that their default hash
functions where so basic.

The original primary user of the qemu_xxhash functions is QHT which has
to manage its own tables so relies more on having a well distributed
hash function.

-- 
Alex Bennée
Virtualisation Tech Lead @ Linaro