projects / platform / kernel / linux-rpi.git / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: ed9109a) | patch
bpf/benchs: Add benchmark tests for bloom filter throughput + false positive
authorJoanne Koong <joannekoong@fb.com>
Wed, 27 Oct 2021 23:45:03 +0000 (16:45 -0700)
committerAlexei Starovoitov <ast@kernel.org>
Thu, 28 Oct 2021 20:22:49 +0000 (13:22 -0700)
commit57fd1c63c9a687c5fdc86fa628c490d6733e8d0b
treeb25ea789daa0fd4bb5d5bfebb72a16de843ffbc4tree | snapshot
parented9109ad643cfbe69670a37cdbaf2da9f409fed0commit | diff
bpf/benchs: Add benchmark tests for bloom filter throughput + false positive

This patch adds benchmark tests for the throughput (for lookups + updates)
and the false positive rate of bloom filter lookups, as well as some
minor refactoring of the bash script for running the benchmarks.

These benchmarks show that as the number of hash functions increases,
the throughput and the false positive rate of the bloom filter decreases.
>From the benchmark data, the approximate average false-positive rates
are roughly as follows:

1 hash function = ~30%
2 hash functions = ~15%
3 hash functions = ~5%
4 hash functions = ~2.5%
5 hash functions = ~1%
6 hash functions = ~0.5%
7 hash functions  = ~0.35%
8 hash functions = ~0.15%
9 hash functions = ~0.1%
10 hash functions = ~0%

For reference data, the benchmarks run on one thread on a machine
with one numa node for 1 to 5 hash functions for 8-byte and 64-byte
values are as follows:

1 hash function:
  50k entries
8-byte value
    Lookups - 51.1 M/s operations
    Updates - 33.6 M/s operations
    False positive rate: 24.15%
64-byte value
    Lookups - 15.7 M/s operations
    Updates - 15.1 M/s operations
    False positive rate: 24.2%
  100k entries
8-byte value
    Lookups - 51.0 M/s operations
    Updates - 33.4 M/s operations
    False positive rate: 24.04%
64-byte value
    Lookups - 15.6 M/s operations
    Updates - 14.6 M/s operations
    False positive rate: 24.06%
  500k entries
8-byte value
    Lookups - 50.5 M/s operations
    Updates - 33.1 M/s operations
    False positive rate: 27.45%
64-byte value
    Lookups - 15.6 M/s operations
    Updates - 14.2 M/s operations
    False positive rate: 27.42%
  1 mil entries
8-byte value
    Lookups - 49.7 M/s operations
    Updates - 32.9 M/s operations
    False positive rate: 27.45%
64-byte value
    Lookups - 15.4 M/s operations
    Updates - 13.7 M/s operations
    False positive rate: 27.58%
  2.5 mil entries
8-byte value
    Lookups - 47.2 M/s operations
    Updates - 31.8 M/s operations
    False positive rate: 30.94%
64-byte value
    Lookups - 15.3 M/s operations
    Updates - 13.2 M/s operations
    False positive rate: 30.95%
  5 mil entries
8-byte value
    Lookups - 41.1 M/s operations
    Updates - 28.1 M/s operations
    False positive rate: 31.01%
64-byte value
    Lookups - 13.3 M/s operations
    Updates - 11.4 M/s operations
    False positive rate: 30.98%

2 hash functions:
  50k entries
8-byte value
    Lookups - 34.1 M/s operations
    Updates - 20.1 M/s operations
    False positive rate: 9.13%
64-byte value
    Lookups - 8.4 M/s operations
    Updates - 7.9 M/s operations
    False positive rate: 9.21%
  100k entries
8-byte value
    Lookups - 33.7 M/s operations
    Updates - 18.9 M/s operations
    False positive rate: 9.13%
64-byte value
    Lookups - 8.4 M/s operations
    Updates - 7.7 M/s operations
    False positive rate: 9.19%
  500k entries
8-byte value
    Lookups - 32.7 M/s operations
    Updates - 18.1 M/s operations
    False positive rate: 12.61%
64-byte value
    Lookups - 8.4 M/s operations
    Updates - 7.5 M/s operations
    False positive rate: 12.61%
  1 mil entries
8-byte value
    Lookups - 30.6 M/s operations
    Updates - 18.9 M/s operations
    False positive rate: 12.54%
64-byte value
    Lookups - 8.0 M/s operations
    Updates - 7.0 M/s operations
    False positive rate: 12.52%
  2.5 mil entries
8-byte value
    Lookups - 25.3 M/s operations
    Updates - 16.7 M/s operations
    False positive rate: 16.77%
64-byte value
    Lookups - 7.9 M/s operations
    Updates - 6.5 M/s operations
    False positive rate: 16.88%
  5 mil entries
8-byte value
    Lookups - 20.8 M/s operations
    Updates - 14.7 M/s operations
    False positive rate: 16.78%
64-byte value
    Lookups - 7.0 M/s operations
    Updates - 6.0 M/s operations
    False positive rate: 16.78%

3 hash functions:
  50k entries
8-byte value
    Lookups - 25.1 M/s operations
    Updates - 14.6 M/s operations
    False positive rate: 7.65%
64-byte value
    Lookups - 5.8 M/s operations
    Updates - 5.5 M/s operations
    False positive rate: 7.58%
  100k entries
8-byte value
    Lookups - 24.7 M/s operations
    Updates - 14.1 M/s operations
    False positive rate: 7.71%
64-byte value
    Lookups - 5.8 M/s operations
    Updates - 5.3 M/s operations
    False positive rate: 7.62%
  500k entries
8-byte value
    Lookups - 22.9 M/s operations
    Updates - 13.9 M/s operations
    False positive rate: 2.62%
64-byte value
    Lookups - 5.6 M/s operations
    Updates - 4.8 M/s operations
    False positive rate: 2.7%
  1 mil entries
8-byte value
    Lookups - 19.8 M/s operations
    Updates - 12.6 M/s operations
    False positive rate: 2.60%
64-byte value
    Lookups - 5.3 M/s operations
    Updates - 4.4 M/s operations
    False positive rate: 2.69%
  2.5 mil entries
8-byte value
    Lookups - 16.2 M/s operations
    Updates - 10.7 M/s operations
    False positive rate: 4.49%
64-byte value
    Lookups - 4.9 M/s operations
    Updates - 4.1 M/s operations
    False positive rate: 4.41%
  5 mil entries
8-byte value
    Lookups - 18.8 M/s operations
    Updates - 9.2 M/s operations
    False positive rate: 4.45%
64-byte value
    Lookups - 5.2 M/s operations
    Updates - 3.9 M/s operations
    False positive rate: 4.54%

4 hash functions:
  50k entries
8-byte value
    Lookups - 19.7 M/s operations
    Updates - 11.1 M/s operations
    False positive rate: 1.01%
64-byte value
    Lookups - 4.4 M/s operations
    Updates - 4.0 M/s operations
    False positive rate: 1.00%
  100k entries
8-byte value
    Lookups - 19.5 M/s operations
    Updates - 10.9 M/s operations
    False positive rate: 1.00%
64-byte value
    Lookups - 4.3 M/s operations
    Updates - 3.9 M/s operations
    False positive rate: 0.97%
  500k entries
8-byte value
    Lookups - 18.2 M/s operations
    Updates - 10.6 M/s operations
    False positive rate: 2.05%
64-byte value
    Lookups - 4.3 M/s operations
    Updates - 3.7 M/s operations
    False positive rate: 2.05%
  1 mil entries
8-byte value
    Lookups - 15.5 M/s operations
    Updates - 9.6 M/s operations
    False positive rate: 1.99%
64-byte value
    Lookups - 4.0 M/s operations
    Updates - 3.4 M/s operations
    False positive rate: 1.99%
  2.5 mil entries
8-byte value
    Lookups - 13.8 M/s operations
    Updates - 7.7 M/s operations
    False positive rate: 3.91%
64-byte value
    Lookups - 3.7 M/s operations
    Updates - 3.6 M/s operations
    False positive rate: 3.78%
  5 mil entries
8-byte value
    Lookups - 13.0 M/s operations
    Updates - 6.9 M/s operations
    False positive rate: 3.93%
64-byte value
    Lookups - 3.5 M/s operations
    Updates - 3.7 M/s operations
    False positive rate: 3.39%

5 hash functions:
  50k entries
8-byte value
    Lookups - 16.4 M/s operations
    Updates - 9.1 M/s operations
    False positive rate: 0.78%
64-byte value
    Lookups - 3.5 M/s operations
    Updates - 3.2 M/s operations
    False positive rate: 0.77%
  100k entries
8-byte value
    Lookups - 16.3 M/s operations
    Updates - 9.0 M/s operations
    False positive rate: 0.79%
64-byte value
    Lookups - 3.5 M/s operations
    Updates - 3.2 M/s operations
    False positive rate: 0.78%
  500k entries
8-byte value
    Lookups - 15.1 M/s operations
    Updates - 8.8 M/s operations
    False positive rate: 1.82%
64-byte value
    Lookups - 3.4 M/s operations
    Updates - 3.0 M/s operations
    False positive rate: 1.78%
  1 mil entries
8-byte value
    Lookups - 13.2 M/s operations
    Updates - 7.8 M/s operations
    False positive rate: 1.81%
64-byte value
    Lookups - 3.2 M/s operations
    Updates - 2.8 M/s operations
    False positive rate: 1.80%
  2.5 mil entries
8-byte value
    Lookups - 10.5 M/s operations
    Updates - 5.9 M/s operations
    False positive rate: 0.29%
64-byte value
    Lookups - 3.2 M/s operations
    Updates - 2.4 M/s operations
    False positive rate: 0.28%
  5 mil entries
8-byte value
    Lookups - 9.6 M/s operations
    Updates - 5.7 M/s operations
    False positive rate: 0.30%
64-byte value
    Lookups - 3.2 M/s operations
    Updates - 2.7 M/s operations
    False positive rate: 0.30%

Signed-off-by: Joanne Koong <joannekoong@fb.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Andrii Nakryiko <andrii@kernel.org>
Link: https://lore.kernel.org/bpf/20211027234504.30744-5-joannekoong@fb.com
tools/testing/selftests/bpf/Makefile diff | blob | history
tools/testing/selftests/bpf/bench.c diff | blob | history
tools/testing/selftests/bpf/bench.h diff | blob | history
tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c [new file with mode: 0644] blob
tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh [new file with mode: 0755] blob
tools/testing/selftests/bpf/benchs/run_bench_ringbufs.sh diff | blob | history
tools/testing/selftests/bpf/benchs/run_common.sh [new file with mode: 0644] blob
tools/testing/selftests/bpf/progs/bloom_filter_bench.c [new file with mode: 0644] blob
Domain: System / Kernel;