Re: [GIT PULL] Please pull NFS client changes for Linux 5.18

[Trond Myklebust <trondmy@hammerspace.com>]

On Wed, 2022-03-30 at 15:45 -0700, Linus Torvalds wrote:
> On Wed, Mar 30, 2022 at 3:22 PM Trond Myklebust
> <trondmy@hammerspace.com> wrote:
> > 
> > With 9175 ext4 offsets, I see 157 collisions (== hash buckets with
> > > 1
> > entry). So hash_64() does perform less well when you're hashing a
> > value
> > that is already a hash.
> 
> No collisions with xxhash? Because xxhash() reality seems to do
> pretty
> similar things in the end (multiply by a prime, shift bits down and
> xor them).
> 
> In fact, the main difference seems to be that xxhash() will do a
> "rotl()" by 27 before doing the prime multiplication, and then it
> will
> finish the thing by a few more multiples mixed with shifting the high
> bits down a few times.
> 
> Our regular fast hash doesn't do the "shift bits down", because it
> relies on only using the upper bits anyway (and it is pretty heavily
> geared towards "fast and good enough").
> 
> But if the *source* of the hash has a lot of low bits clear, I can
> imagine that the "rotl" that xxhash does improves on the bit
> distribution of the multiplication (which will only move bits
> upwards).
> 
> And if it turns out our default hash has some bad cases, I'd prefer
> to
> fix _that_ regardless..
> 

Hmm... No there doesn't appear to be a huge difference between the two.
With both test programs running on the same data set of ext4 getdents
offsets, I see the following.

With xxhash64 reduced to 18 bits, I see:
read 57654 entries
min = 0, max = 5, collisions = 5501, avg = 1
read 98978 entries
min = 0, max = 6, collisions = 14730, avg = 1

..and with hash_64() reduced to 18 bits:
read 57654 entries
min = 0, max = 4, collisions = 5538, avg = 1
read 98978 entries
min = 0, max = 5, collisions = 14623, avg = 1

So they both appear to be seeing similar collision rates with the same
data sets
-- 
Trond Myklebust
Linux NFS client maintainer, Hammerspace
trond.myklebust@hammerspace.com