bpf: optimize hashmap lookups when key_size is divisible by 4
PATCH v2 1/1 bpf: optimize hashmap lookups when key_size is divisible by 4
The BPF hashmap uses the jhash() hash function. There is an optimized version of this hash function which may be used if hash size is a multiple of 4. Apply this optimization to the hashmap in a similar way as it is done in the bloom filter map.
On practice the optimization is only noticeable for smaller key sizes, which, however, is sufficient for many applications. An example is listed in the following table of measurements (a hashmap of 65536 elements was used):
--------------------------------------------------------------------
| key_size | fullness | lookups /sec | lookups (opt) /sec | gain |
--------------------------------------------------------------------
| 4 | 25% | 42.990M | 46.000M | 7.0% |
| 4 | 50% | 37.910M | 39.094M | 3.1% |
| 4 | 75% | 34.486M | 36.124M | 4.7% |
| 4 | 100% | 31.760M | 32.719M | 3.0% |
--------------------------------------------------------------------
| 8 | 25% | 43.855M | 49.626M | 13.2% |
| 8 | 50% | 38.328M | 42.152M | 10.0% |
| 8 | 75% | 34.483M | 38.088M | 10.5% |
| 8 | 100% | 31.306M | 34.686M | 10.8% |
--------------------------------------------------------------------
| 12 | 25% | 38.398M | 43.770M | 14.0% |
| 12 | 50% | 33.336M | 37.712M | 13.1% |
| 12 | 75% | 29.917M | 34.440M | 15.1% |
| 12 | 100% | 27.322M | 30.480M | 11.6% |
--------------------------------------------------------------------
| 16 | 25% | 41.491M | 41.921M | 1.0% |
| 16 | 50% | 36.206M | 36.474M | 0.7% |
| 16 | 75% | 32.529M | 33.027M | 1.5% |
| 16 | 100% | 29.581M | 30.325M | 2.5% |
--------------------------------------------------------------------
| 20 | 25% | 34.240M | 36.787M | 7.4% |
| 20 | 50% | 30.328M | 32.663M | 7.7% |
| 20 | 75% | 27.536M | 29.354M | 6.6% |
| 20 | 100% | 24.847M | 26.505M | 6.7% |
--------------------------------------------------------------------
| 24 | 25% | 36.329M | 40.608M | 11.8% |
| 24 | 50% | 31.444M | 35.059M | 11.5% |
| 24 | 75% | 28.426M | 31.452M | 10.6% |
| 24 | 100% | 26.278M | 28.741M | 9.4% |
--------------------------------------------------------------------
| 28 | 25% | 31.540M | 31.944M | 1.3% |
| 28 | 50% | 27.739M | 28.063M | 1.2% |
| 28 | 75% | 24.993M | 25.814M | 3.3% |
| 28 | 100% | 23.513M | 23.500M | -0.1% |
--------------------------------------------------------------------
| 32 | 25% | 32.116M | 33.953M | 5.7% |
| 32 | 50% | 28.879M | 29.859M | 3.4% |
| 32 | 75% | 26.227M | 26.948M | 2.7% |
| 32 | 100% | 23.829M | 24.613M | 3.3% |
--------------------------------------------------------------------
| 64 | 25% | 22.535M | 22.554M | 0.1% |
| 64 | 50% | 20.471M | 20.675M | 1.0% |
| 64 | 75% | 19.077M | 19.146M | 0.4% |
| 64 | 100% | 17.710M | 18.131M | 2.4% |
--------------------------------------------------------------------The following script was used to gather the results (SMT & frequency off):
cd tools/testing/selftests/bpf
for key_size in 4 8 12 16 20 24 28 32 64; do
for nr_entries in `seq 16384 16384 65536`; do
fullness=$(printf '%3s' $((nr_entries*100/65536)))
echo -n "key_size=$key_size: $fullness% full: "
sudo ./bench -d2 -a bpf-hashmap-lookup --key_size=$key_size --nr_entries=$nr_entries --max_entries=65536 --nr_loops=2000000 --map_flags=0x40 | grep cpu
done
echo
done---
v1->v2:
- simplify/optimize code by just testing the (key_len%4 == 0) in hot path (Alexei)
kernel/bpf/hashtab.c | 2 ++ 1 file changed, 2 insertions(+)
kernel/bpf/hashtab.c +2 -0
@@ -607,6 +607,8 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)static inline u32 htab_map_hash (const void *key,u32 key_len,u32 hashrnd) { +if (likely (key_len %4 ==0 )) +return jhash2 (key, key_len /4 , hashrnd);return jhash (key, key_len, hashrnd); }
Signature · 1 line
2.34.1
Quoted 85 lines · Anton Protopopov
The BPF hashmap uses the
jhash()hash function. There is an optimized version of this hash function which may be used if hash size is a multiple of 4. Apply this optimization to the hashmap in a similar way as it is done in the bloom filter map.On practice the optimization is only noticeable for smaller key sizes, which, however, is sufficient for many applications. An example is listed in the following table of measurements (a hashmap of 65536 elements was used):
-------------------------------------------------------------------- | key_size | fullness | lookups /sec | lookups (opt) /sec | gain | -------------------------------------------------------------------- | 4 | 25% | 42.990M | 46.000M | 7.0% | | 4 | 50% | 37.910M | 39.094M | 3.1% | | 4 | 75% | 34.486M | 36.124M | 4.7% | | 4 | 100% | 31.760M | 32.719M | 3.0% | -------------------------------------------------------------------- | 8 | 25% | 43.855M | 49.626M | 13.2% | | 8 | 50% | 38.328M | 42.152M | 10.0% | | 8 | 75% | 34.483M | 38.088M | 10.5% | | 8 | 100% | 31.306M | 34.686M | 10.8% | -------------------------------------------------------------------- | 12 | 25% | 38.398M | 43.770M | 14.0% | | 12 | 50% | 33.336M | 37.712M | 13.1% | | 12 | 75% | 29.917M | 34.440M | 15.1% | | 12 | 100% | 27.322M | 30.480M | 11.6% | -------------------------------------------------------------------- | 16 | 25% | 41.491M | 41.921M | 1.0% | | 16 | 50% | 36.206M | 36.474M | 0.7% | | 16 | 75% | 32.529M | 33.027M | 1.5% | | 16 | 100% | 29.581M | 30.325M | 2.5% | -------------------------------------------------------------------- | 20 | 25% | 34.240M | 36.787M | 7.4% | | 20 | 50% | 30.328M | 32.663M | 7.7% | | 20 | 75% | 27.536M | 29.354M | 6.6% | | 20 | 100% | 24.847M | 26.505M | 6.7% | -------------------------------------------------------------------- | 24 | 25% | 36.329M | 40.608M | 11.8% | | 24 | 50% | 31.444M | 35.059M | 11.5% | | 24 | 75% | 28.426M | 31.452M | 10.6% | | 24 | 100% | 26.278M | 28.741M | 9.4% | -------------------------------------------------------------------- | 28 | 25% | 31.540M | 31.944M | 1.3% | | 28 | 50% | 27.739M | 28.063M | 1.2% | | 28 | 75% | 24.993M | 25.814M | 3.3% | | 28 | 100% | 23.513M | 23.500M | -0.1% | -------------------------------------------------------------------- | 32 | 25% | 32.116M | 33.953M | 5.7% | | 32 | 50% | 28.879M | 29.859M | 3.4% | | 32 | 75% | 26.227M | 26.948M | 2.7% | | 32 | 100% | 23.829M | 24.613M | 3.3% | -------------------------------------------------------------------- | 64 | 25% | 22.535M | 22.554M | 0.1% | | 64 | 50% | 20.471M | 20.675M | 1.0% | | 64 | 75% | 19.077M | 19.146M | 0.4% | | 64 | 100% | 17.710M | 18.131M | 2.4% | --------------------------------------------------------------------The following script was used to gather the results (SMT & frequency off):
cd tools/testing/selftests/bpf for key_size in 4 8 12 16 20 24 28 32 64; do for nr_entries in `seq 16384 16384 65536`; do fullness=$(printf '%3s' $((nr_entries*100/65536))) echo -n "key_size=$key_size: $fullness% full: " sudo ./bench -d2 -a bpf-hashmap-lookup --key_size=$key_size --nr_entries=$nr_entries --max_entries=65536 --nr_loops=2000000 --map_flags=0x40 | grep cpu done echo doneSigned-off-by Anton Protopopov <[email protected]>---
v1->v2:
- simplify/optimize code by just testing the (key_len%4 == 0) in hot path (Alexei)kernel/bpf/hashtab.c | 2 ++ 1 file changed, 2 insertions(+)kernel/bpf/hashtab.c +0
-0
kernel/bpf/hashtab.c static struct bpf_map *htab_map_alloc(union bpf_attr *attr) · line 613
Quoted 7 lines
kernel/bpf/hashtab.c +2
-0@@ -607,6 +607,8 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)static inline u32 htab_map_hash (const void *key,u32 key_len,u32 hashrnd) { +if (likely (key_len %4 ==0 )) +return jhash2 (key, key_len /4 , hashrnd);return jhash (key, key_len, hashrnd); }
This looks much cleaner than v1. Applied.
Do you mind doing similar patch for bloomfilter?
(removing aligned_u32_count variable)
Quoted 4 lines · Alexei Starovoitov
Quoted 3 lines · Anton Protopopov
[...]
Quoted 8 lines
kernel/bpf/hashtab.c static struct bpf_map *htab_map_alloc(union bpf_attr *attr) · line 613
Quoted 6 lines
static inline u32
htab_map_hash(const void *key, u32 key_len, u32 hashrnd){kernel/bpf/hashtab.c +2
-0+if (likely (key_len %4 ==0 )) +return jhash2 (key, key_len /4 , hashrnd);return jhash (key, key_len, hashrnd); }This looks much cleaner than v1. Applied.
Thanks!
Quoted 2 lines
Do you mind doing similar patch for bloomfilter?
(removingaligned_u32_countvariable)
Sure, done.
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 10 lines · On Sat, 1 Apr 2023 20:06:02 +0000 you wrote:
The BPF hashmap uses the
jhash()hash function. There is an optimized version of this hash function which may be used if hash size is a multiple of 4. Apply this optimization to the hashmap in a similar way as it is done in the bloom filter map.On practice the optimization is only noticeable for smaller key sizes, which, however, is sufficient for many applications. An example is listed in the following table of measurements (a hashmap of 65536 elements was used):
[...]
Here is the summary with links:
- [v2,bpf-next] bpf: optimize hashmap lookups when key_size is divisible by 4
https://git.kernel.org/bpf/bpf-next/c/5b85575ad428
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html