lkml.org 
[lkml]   [2022]   [Mar]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [GIT PULL] Please pull NFS client changes for Linux 5.18
Date
On Wed, 2022-03-30 at 11:17 -0700, Linus Torvalds wrote:
> On Tue, Mar 29, 2022 at 12:36 PM Trond Myklebust
> <trondmy@hammerspace.com> wrote:
> >
> > - Readdir fixes to improve cacheability of large directories when
> > there
> >   are multiple readers and writers.
>
> So I only took a look at this part now. I've obviously already pulled
> it, but that use of 'xxhash()' just made me go "Whaaa?"
>
> It's claimed that it's used because of its extreme performance, but
> the performance numbers come from using it as a block hash.
>
> That's not what nfs does.
>
> The nfs code just does
>
>     xxhash(&cookie, sizeof(cookie), 0) & NFS_READDIR_COOKIE_MASK;
>
> where that "cookie" is just a 64-bit entity. And then it masks off
> everything but 18 bits.
>
> Is that *really* appropriate use of a new hash function?
>
> Why is this not just doing
>
>   #include <hash.h>
>
>   hash_64(cookie, 18);
>
> which is a lot more obvious than xxhash().
>
> If there really are some serious problems with the perfectly standard
> hash() functionality, I think you should document them.
>
> Because just randomly picking xxhash() without explaining _why_ you
> can't just use the same simple thing we use elsewhere is very odd.
>
> Or rather, when the only documentation is "performance", then I think
> the regular "hash_64()" is the obvious and trivial choice.
>
>                   Linus

My main worry was that hash_64() would have too many collisions. Since
this is using cuckoo nesting, that would be a problem.

I did some quick studies after I got your email, and it seems as if my
concerns were unfounded. I've tested both a linear index and a sample
of ext4 getdents offsets.
While the sample of ext4 offsets did show a larger number of collisions
than a simple linear index, it wasn't too terrible (3 collisions in a
sample of 9000 entries).
The linear index showed no collisions up to about 100000 entries.

So, I'd be OK with changing to hash_64() and will queue up a bugfix for
it. I should have done this study earlier...

--
Trond Myklebust
Linux NFS client maintainer, Hammerspace
trond.myklebust@hammerspace.com


\
 
 \ /
  Last update: 2022-03-30 22:05    [W:0.063 / U:0.856 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site