Received-SPF: pass (google.com: domain of linux-nfs-owner@vger.kernel.org designates 2620:137:e000::1:18 as permitted sender) client-ip=2620:137:e000::1:18;
MIME-Version: 1.0
References: <7b0576d8d49bbd358767620218c1966e8fe9a883.camel@hammerspace.com>
 <CAHk-=wh-hs_q-sL6PNptfVmNm7tWrt24o4-YR74Fxo+fdKsmxA@mail.gmail.com>
 <c5401981cb21674bdd3ffd9cc4fac9fe48fb8265.camel@hammerspace.com> <4eed252caf56f16c290f0c54b5d850d4eab5dc1b.camel@hammerspace.com>
In-Reply-To: <4eed252caf56f16c290f0c54b5d850d4eab5dc1b.camel@hammerspace.com>
From:   Linus Torvalds <torvalds@linux-foundation.org>
Date:   Wed, 30 Mar 2022 15:45:21 -0700
Message-ID: <CAHk-=wi_0L4u_Fd1S3r+-1Ok95HveaXNqY8h3McJOUCfk-tqDg@mail.gmail.com>
Subject: Re: [GIT PULL] Please pull NFS client changes for Linux 5.18
To:     Trond Myklebust <trondmy@hammerspace.com>
Cc:     "linux-nfs@vger.kernel.org" <linux-nfs@vger.kernel.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

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

             Linus