On Wed, 2022-03-30 at 16:01 -0400, Trond Myklebust wrote: > On Wed, 2022-03-30 at 11:17 -0700, Linus Torvalds wrote: > > On Tue, Mar 29, 2022 at 12:36 PM Trond Myklebust > > <trondmy@xxxxxxxxxxxxxxx> 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). Actually, let me correct that. 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. > The linear index showed no collisions up to about 100000 entries. This is unchanged, so with XFS and btrfs as the exported filesystems, we should not have a problem. > > 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@xxxxxxxxxxxxxxx
