From: Andrii Nakryiko <andrii.nakryiko@gmail.com>
To: Joanne Koong <joannekoong@fb.com>
Cc: bpf <bpf@vger.kernel.org>, Andrii Nakryiko <andrii@kernel.org>,
Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>, Martin Lau <kafai@fb.com>,
Kernel Team <Kernel-team@fb.com>
Subject: Re: [PATCH v6 bpf-next 4/5] bpf/benchs: Add benchmark tests for bloom filter throughput + false positive
Date: Thu, 28 Oct 2021 11:26:17 -0700 [thread overview]
Message-ID: <CAEf4BzZFZTt5eOC7VW9UyWkN=EdgOH6uZxODDch8GZmGAibfWg@mail.gmail.com> (raw)
In-Reply-To: <20211027234504.30744-5-joannekoong@fb.com>
On Wed, Oct 27, 2021 at 4:45 PM Joanne Koong <joannekoong@fb.com> wrote:
>
> 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>
> ---
LGTM.
Acked-by: Andrii Nakryiko <andrii@kernel.org>
> tools/testing/selftests/bpf/Makefile | 6 +-
> tools/testing/selftests/bpf/bench.c | 37 ++
> tools/testing/selftests/bpf/bench.h | 3 +
> .../bpf/benchs/bench_bloom_filter_map.c | 420 ++++++++++++++++++
> .../bpf/benchs/run_bench_bloom_filter_map.sh | 28 ++
> .../bpf/benchs/run_bench_ringbufs.sh | 30 +-
> .../selftests/bpf/benchs/run_common.sh | 48 ++
> .../selftests/bpf/progs/bloom_filter_bench.c | 153 +++++++
> 8 files changed, 695 insertions(+), 30 deletions(-)
> create mode 100644 tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c
> create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh
> create mode 100644 tools/testing/selftests/bpf/benchs/run_common.sh
> create mode 100644 tools/testing/selftests/bpf/progs/bloom_filter_bench.c
>
[...]
next prev parent reply other threads:[~2021-10-28 18:26 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-27 23:44 [PATCH v6 bpf-next 0/5] Implement bloom filter map Joanne Koong
2021-10-27 23:45 ` [PATCH v6 bpf-next 1/5] bpf: Add bloom filter map implementation Joanne Koong
2021-10-28 18:15 ` Andrii Nakryiko
2021-10-29 0:15 ` Joanne Koong
2021-10-29 0:44 ` Andrii Nakryiko
2021-10-28 20:35 ` Alexei Starovoitov
2021-10-28 21:14 ` Martin KaFai Lau
2021-10-29 3:17 ` Joanne Koong
2021-10-29 4:49 ` Martin KaFai Lau
[not found] ` <6d930e97-424d-393d-4731-ac8eda9e5156@fb.com>
2021-10-29 6:40 ` Martin KaFai Lau
2021-10-27 23:45 ` [PATCH v6 bpf-next 2/5] libbpf: Add "map_extra" as a per-map-type extra flag Joanne Koong
2021-10-28 18:14 ` Andrii Nakryiko
2021-10-27 23:45 ` [PATCH v6 bpf-next 3/5] selftests/bpf: Add bloom filter map test cases Joanne Koong
2021-10-28 18:16 ` Andrii Nakryiko
2021-10-27 23:45 ` [PATCH v6 bpf-next 4/5] bpf/benchs: Add benchmark tests for bloom filter throughput + false positive Joanne Koong
2021-10-28 18:26 ` Andrii Nakryiko [this message]
2021-10-27 23:45 ` [PATCH v6 bpf-next 5/5] bpf/benchs: Add benchmarks for comparing hashmap lookups w/ vs. w/out bloom filter Joanne Koong
2021-10-28 22:10 ` [PATCH v6 bpf-next 0/5] Implement bloom filter map Martin KaFai Lau
2021-10-28 23:05 ` Alexei Starovoitov
2021-10-29 0:23 ` Joanne Koong
2021-10-29 0:30 ` Alexei Starovoitov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAEf4BzZFZTt5eOC7VW9UyWkN=EdgOH6uZxODDch8GZmGAibfWg@mail.gmail.com' \
--to=andrii.nakryiko@gmail.com \
--cc=Kernel-team@fb.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=joannekoong@fb.com \
--cc=kafai@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).