Re: [PATCH bpf-next 0/6] New benchmark for hashmap lookups

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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


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.

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

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



[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux