| Message ID | 7b0576d8d49bbd358767620218c1966e8fe9a883.camel@hammerspace.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [GIT,PULL] Please pull NFS client changes for Linux 5.18 | expand |
The pull request you sent on Tue, 29 Mar 2022 19:36:00 +0000:
> git://git.linux-nfs.org/projects/trondmy/linux-nfs.git tags/nfs-for-5.18-1
has been merged into torvalds/linux.git:
https://git.kernel.org/torvalds/c/965181d7ef7e1a863477536dc328c23a7ebc8a1d
Thank you!
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
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...
On Wed, Mar 30, 2022 at 1:02 PM Trond Myklebust <trondmy@hammerspace.com> wrote: > > My main worry was that hash_64() would have too many collisions. So as you found out, hash_64() is actually a fairly good hash despite being very simple. In fact, with an input of just one word, it's generally hard to do much better. I'm obviously not claiming it's a _cryptographic_ hash, but compared to the usual "xor and shift a few times", it really shouldn't be too bad. And that's really what xxhash() does anyway. I think the reason to use xxhash() would be if you have a noticeably bigger input, or some truly special cases. But for a single word, and then not even using very many of the resulting bits, our regular family of 'hash()' routines really should generally be perfectly fine. It should spread and mix the input bits competently. Linus
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@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). 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... >
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
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
On Wed, Mar 30, 2022 at 4:18 PM Trond Myklebust <trondmy@hammerspace.com> wrote: > > Hmm... No there doesn't appear to be a huge difference between the two. Ok, thanks for checking. It's basically what I would have expected, both models really just depend on a reasonable mixing and shuffling of bits in the word, and it really looks like they have very similar collision behavior. At some point even with equivalent functions you obviously end up with just random differences that just depend on the input set and prue luck. But at least based on your numbers, it does look like they really are equivalent, and hash_64() certainly doesn't look any worse. All the extra work xxhash() does should matter mainly for (a) using more final bits of the hash (ir not reducing them in the end) (b) all the cases where you have much more input than one single word Here, (b) obviously isn't an issue. And that (a) is by design - those default kernel hash() functions are literally designed for generating the index for hash tables, and so expects that final reduction in size. As a result, unlike xxhash(), it doesn't try to mix in bits in the low bits, because it knows those will be shifted away in the use-case it's designed for (the hash() reduction in bits always takes the high bits). But that use-case is really exactly what nfs is looking for too, which is why I was expecting the regular hash_64() to JustWork(tm) for the nfs case. Linus