On Tue, Jan 31, 2023 at 11:18 AM Anton Protopopov <aspsk@xxxxxxxxxxxxx> wrote: > > On 23/01/31 10:48, Andrii Nakryiko wrote: > > On Tue, Jan 31, 2023 at 2:47 AM Anton Protopopov <aspsk@xxxxxxxxxxxxx> wrote: > > > > > > On 23/01/30 04:17, Andrii Nakryiko wrote: > > > > On Fri, Jan 27, 2023 at 10:14 AM Anton Protopopov <aspsk@xxxxxxxxxxxxx> wrote: > > > > > > > > > > Add a new benchmark for hashmap lookups and fix several typos. See individual > > > > > commits for descriptions. > > > > > > > > > > One thing to mention here is that in commit 3 I've patched bench so that now > > > > > command line options can be reused by different benchmarks. > > > > > > > > > > The benchmark itself is added in the last commit 6. I am using this benchmark > > > > > to test map lookup productivity when using a different hash function (see > > > > > https://fosdem.org/2023/schedule/event/bpf_hashing/). The results provided by > > > > > the benchmark look reasonable and match the results of my different benchmarks > > > > > (requiring to patch kernel to get actual statistics on map lookups). > > > > > > > > Could you share the results with us? Curious which hash functions did > > > > you try and which one are the most promising :) > > > > > > For the longer version with pictures see the talk I've referenced above (it's > > > at FOSDEM next Sunday Feb 5). A short version follows. > > > > Yep, I'll try to watch it. > > > > > > > > The xxh3 hash works fine for big keys, where "big" is different for different > > > architectures and for different maps sizes. On my Intel i7 machine this means > > > key size >= 8. On my AMD machine xxh3 works better for all keys for small maps, > > > but degrades for keys of size 12,16,20 for bigger maps (>=200K elements or so). > > > Example (map size 100K, 50% full, measuring M ops/second): > > > > Nice, I was hoping you would look at xxh3, as I've been meaning to try > > it out as well (have dirty patches to introduce xxh3 into > > lib/xxhash.c, but didn't get to actual benchmarking). > > My first attempt was with lib/xxhash.c, and it looked well on the first glance > (outperformed every other hash in my hash benchmark). However, when used inside > the hashmap, it behaved way worse than expected, so I had to inline it. > > > Despite this AMD-specific degradation (which is interesting in its own > > right, could it be some fluke in testing?), I think it's a good idea > > to switch from jhash to xxh3, as it seems almost universally better. > > See also below. > > > > > > hash_size 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 > > > orig_map 15.7 15.4 14.2 13.9 13.1 13.2 12.0 12.0 11.5 11.2 10.6 10.7 10.0 10.0 9.6 9.3 > > > new_map 15.5 15.9 15.2 15.3 14.3 14.6 14.0 14.2 13.3 13.6 13.1 13.4 12.7 13.1 12.3 12.8 > > > > > > A smaller map (10K, 50% full): > > > > > > hash_size 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 > > > orig_map 36.1 36.8 32.1 32.4 29.0 29.1 26.2 26.4 23.9 24.3 21.8 22.5 20.4 20.7 19.3 19.1 > > > new_map 37.7 39.6 34.0 36.5 31.5 34.1 30.7 32.7 28.1 29.5 27.4 28.8 27.1 28.1 26.4 27.8 > > > > > > Other hash functions I've tried (older xxh32/64, spooky) work _way_ worse for > > > small keys than jhash/xxh3. (Answering a possible question about vector instructions: > > > xxh3 is scalar until key size <= 240, then the xxh64/xxh32 can be used which > > > also provides ~2x map lookup speed gain comparing to jhash for keys >240.) > > > > Yeah, not suprising. xxh32/64 were optimized for long byte arrays, not > > for short keys. While xxh3 puts a lot of attention on short keys. Do > > you see xxh64 being faster than xxh3 for longs keys, as implemented in > > kernel? Kernel doesn't use SSE2/AVX versions, just purely scalars, so > > from reading benchmarks of xxh3/xxh64 author, xxh3 should win in all > > situations. > > For keys longer than 240 the scalar xxh3 works way worse than xxhash. BTW, do > you know use cases when hashmap keys are > 240? (For cilium/tetragon the most > interesting use cases are keys of sizes ~4-40.) Can't recall such big keys, but if someone was to use bpf_get_stack() and using stack traces as keys of hashmap, we'd be looking at 1KB+ keys in such case. When you say "way worse", how much do you think? This is surprising, given official benchmark results. But then, I don't think official benchmark has scalar xxh3 on some of the graphs. > > > > > > > Bloom filters for big >= ~40 keys, predictably, work way faster with xxh3 than > > > with jhash. (Why not similar to hashmap? Because Bloom filters use jhash2 for > > > keys % 4 which works faster than jhash for small keys, see also a patch below.) > > > > > > The stacktrace map doesn't work much faster, because 95% of time it spends in > > > get_perf_callchain (the hash part, though, runs ~1.5-2.0 faster with xxh, as > > > hash size is typically about 60-90 bytes, so this makes sense to use xxh3 in > > > stacktrace by default). > > > > For stacktrace very important aspect would be to pay attention (and > > minimize) hash collisions, though. This was a big problem with > > bpf_get_stackid() and STACK_TRACE map (and what motivated > > bpf_get_stack()). Even with a big sparsely populated map we'd get a > > lot of collisions between stack traces. xxh3 should have much better > > distribution, so in production it should result in less > > dropped/replaced stack traces. If you get a chance, it would be nice > > to collect these stats for jhash and xxh3-based implementations. Note > > that kernel's jhash2 seems to be what SMHasher ([0]) denotes as > > lookup3 (as does Jenkins himself). It's not a very good hash anymore > > in terms of distribution (and throughput as well), compared to xxh3 > > (and lots of other more modern hashes). > > > > [0] https://github.com/rurban/smhasher > > Ok, this makes sense. Based on the fact that for stacktrace xxh3 also works > about twice faster (for stack depths of 10 and more), I see no problem just > using it as is (corrected by the fact that for key sizes of 240 and more we > might prefer xxh64; this shouldn't break the stacktrace algorithms if we use > different hash algorithms, right?). Yep, it shouldn't, it's implementation detail. But of course it would be nice to stick to just one hashing algorithm. > > > > > > > One very simple change which brings 5-10% speed gain for all hashmaps is this: > > > > > > static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd) > > > { > > > + if (likely((key_len & 0x3) == 0)) > > > + return jhash2(key, key_len >> 2, hashrnd); > > > return jhash(key, key_len, hashrnd); > > > } > > > > > > I will follow up with a patch as simple as this ^ or with a combination of > > > jhash, jhash2, and xxh3 once I will run benchmarks on more architectures to > > > check that there are no degradations. > > > > > > Sounds good, looking forward to it! > > Benchmarks for "the better hash" are running already!
