selftests/bpf: Add benchmark for local_storage get
Subsystems (3)
PATCH v3 1/1 selftests/bpf: Add benchmark for local_storage get
Add a benchmarks to demonstrate the performance cliff for local_storage get as the number of local_storage maps increases beyond current local_storage implementation's cache size.
"sequential get" and "interleaved get" benchmarks are added, both of which do many bpf_task_storage_get calls on sets of task local_storage maps of various counts, while considering a single specific map to be 'important' and counting task_storage_gets to the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many other local_storage maps exist and are accessed often.
While "sequential get" benchmark does bpf_task_storage_get for map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4 bpf_task_storage_gets for the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.
A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs local_storage get. The benchmark is identical to "sequential get", but creates and uses BPF_MAP_TYPE_HASH instead of local storage.
Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to local_storage implementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.
Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 69.649 ± 1.207 M ops/s, hits latency: 14.358 ns/op, important_hits throughput: 0.139 ± 0.002 M ops/s
num_maps: 1
local_storage cache sequential get: hits throughput: 3.849 ± 0.035 M ops/s, hits latency: 259.803 ns/op, important_hits throughput: 3.849 ± 0.035 M ops/s local_storage cache interleaved get: hits throughput: 6.881 ± 0.110 M ops/s, hits latency: 145.324 ns/op, important_hits throughput: 6.881 ± 0.110 M ops/s
num_maps: 10
local_storage cache sequential get: hits throughput: 20.339 ± 0.442 M ops/s, hits latency: 49.167 ns/op, important_hits throughput: 2.034 ± 0.044 M ops/s local_storage cache interleaved get: hits throughput: 22.408 ± 0.606 M ops/s, hits latency: 44.627 ns/op, important_hits throughput: 8.003 ± 0.217 M ops/s
num_maps: 16
local_storage cache sequential get: hits throughput: 24.428 ± 1.120 M ops/s, hits latency: 40.937 ns/op, important_hits throughput: 1.527 ± 0.070 M ops/s local_storage cache interleaved get: hits throughput: 26.853 ± 0.825 M ops/s, hits latency: 37.240 ns/op, important_hits throughput: 8.544 ± 0.262 M ops/s
num_maps: 17
local_storage cache sequential get: hits throughput: 24.158 ± 0.222 M ops/s, hits latency: 41.394 ns/op, important_hits throughput: 1.421 ± 0.013 M ops/s local_storage cache interleaved get: hits throughput: 26.223 ± 0.201 M ops/s, hits latency: 38.134 ns/op, important_hits throughput: 7.981 ± 0.061 M ops/s
num_maps: 24
local_storage cache sequential get: hits throughput: 16.820 ± 0.294 M ops/s, hits latency: 59.451 ns/op, important_hits throughput: 0.701 ± 0.012 M ops/s local_storage cache interleaved get: hits throughput: 19.185 ± 0.212 M ops/s, hits latency: 52.125 ns/op, important_hits throughput: 5.396 ± 0.060 M ops/s
num_maps: 32
local_storage cache sequential get: hits throughput: 11.998 ± 0.310 M ops/s, hits latency: 83.347 ns/op, important_hits throughput: 0.375 ± 0.010 M ops/s local_storage cache interleaved get: hits throughput: 14.233 ± 0.265 M ops/s, hits latency: 70.259 ns/op, important_hits throughput: 3.972 ± 0.074 M ops/s
num_maps: 100
local_storage cache sequential get: hits throughput: 5.780 ± 0.250 M ops/s, hits latency: 173.003 ns/op, important_hits throughput: 0.058 ± 0.002 M ops/s local_storage cache interleaved get: hits throughput: 7.175 ± 0.312 M ops/s, hits latency: 139.381 ns/op, important_hits throughput: 1.874 ± 0.081 M ops/s
num_maps: 1000
local_storage cache sequential get: hits throughput: 0.456 ± 0.011 M ops/s, hits latency: 2192.982 ns/op, important_hits throughput: 0.000 ± 0.000 M ops/s local_storage cache interleaved get: hits throughput: 0.539 ± 0.005 M ops/s, hits latency: 1855.508 ns/op, important_hits throughput: 0.135 ± 0.001 M ops/s
Looking at the "sequential get" results, it's clear that as the number of task local_storage maps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that current local_storage implementation assigns a cache_idx to maps as they are created. Since "sequential get" is creating maps 0..n in order and then doing bpf_task_storage_get calls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.
For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
As evidenced by the unintuitive-looking results for smaller num_maps benchmark runs, overhead which is amortized across larger num_maps runs dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem in local_storage_bench.h and ran the benchmark on the same host as the 'real' run. Results:
Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 128.699 ± 1.267 M ops/s, hits latency: 7.770 ns/op, important_hits throughput: 0.257 ± 0.003 M ops/s
num_maps: 1
local_storage cache sequential get: hits throughput: 4.135 ± 0.069 M ops/s, hits latency: 241.831 ns/op, important_hits throughput: 4.135 ± 0.069 M ops/s local_storage cache interleaved get: hits throughput: 7.693 ± 0.039 M ops/s, hits latency: 129.982 ns/op, important_hits throughput: 7.693 ± 0.039 M ops/s
num_maps: 10
local_storage cache sequential get: hits throughput: 33.044 ± 0.232 M ops/s, hits latency: 30.262 ns/op, important_hits throughput: 3.304 ± 0.023 M ops/s local_storage cache interleaved get: hits throughput: 36.525 ± 1.545 M ops/s, hits latency: 27.378 ns/op, important_hits throughput: 13.045 ± 0.552 M ops/s
num_maps: 16
local_storage cache sequential get: hits throughput: 45.502 ± 1.429 M ops/s, hits latency: 21.977 ns/op, important_hits throughput: 2.844 ± 0.089 M ops/s local_storage cache interleaved get: hits throughput: 47.741 ± 1.115 M ops/s, hits latency: 20.946 ns/op, important_hits throughput: 15.190 ± 0.355 M ops/s
num_maps: 17
local_storage cache sequential get: hits throughput: 47.177 ± 0.617 M ops/s, hits latency: 21.197 ns/op, important_hits throughput: 2.775 ± 0.036 M ops/s local_storage cache interleaved get: hits throughput: 50.005 ± 0.463 M ops/s, hits latency: 19.998 ns/op, important_hits throughput: 15.219 ± 0.141 M ops/s
num_maps: 24
local_storage cache sequential get: hits throughput: 58.076 ± 0.507 M ops/s, hits latency: 17.219 ns/op, important_hits throughput: 2.420 ± 0.021 M ops/s local_storage cache interleaved get: hits throughput: 57.731 ± 0.500 M ops/s, hits latency: 17.322 ns/op, important_hits throughput: 16.237 ± 0.141 M ops/s
num_maps: 32
local_storage cache sequential get: hits throughput: 68.266 ± 0.234 M ops/s, hits latency: 14.649 ns/op, important_hits throughput: 2.133 ± 0.007 M ops/s local_storage cache interleaved get: hits throughput: 62.138 ± 2.695 M ops/s, hits latency: 16.093 ns/op, important_hits throughput: 17.341 ± 0.752 M ops/s
num_maps: 100
local_storage cache sequential get: hits throughput: 103.735 ± 2.874 M ops/s, hits latency: 9.640 ns/op, important_hits throughput: 1.037 ± 0.029 M ops/s local_storage cache interleaved get: hits throughput: 85.950 ± 1.619 M ops/s, hits latency: 11.635 ns/op, important_hits throughput: 22.450 ± 0.423 M ops/s
num_maps: 1000
local_storage cache sequential get: hits throughput: 133.551 ± 1.915 M ops/s, hits latency: 7.488 ns/op, important_hits throughput: 0.134 ± 0.002 M ops/s local_storage cache interleaved get: hits throughput: 97.579 ± 1.415 M ops/s, hits latency: 10.248 ns/op, important_hits throughput: 24.505 ± 0.355 M ops/s
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.6ns sequential_get_1: ~17.9ns sequential_get_10: ~18.9ns sequential_get_16: ~19.0ns sequential_get_17: ~20.2ns sequential_get_24: ~42.2ns sequential_get_32: ~68.7ns sequential_get_100: ~163.3ns sequential_get_1000: ~2200ns
Clearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
---
Changelog:
v2 -> v3:
* Accessing 1k maps in ARRAY_OF_MAPS doesn't hit MAX_USED_MAPS limit, so just use 1 program (Alexei)
v1 -> v2:
* Adopt ARRAY_OF_MAPS approach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overhead
tools/testing/selftests/bpf/Makefile | 6 +- tools/testing/selftests/bpf/bench.c | 57 +++ tools/testing/selftests/bpf/bench.h | 5 + .../bpf/benchs/bench_local_storage.c | 332 ++++++++++++++++++ .../bpf/benchs/run_bench_local_storage.sh | 21 ++ .../selftests/bpf/benchs/run_common.sh | 17 + .../selftests/bpf/progs/local_storage_bench.h | 63 ++++ .../bpf/progs/local_storage_bench__get_int.c | 12 + .../bpf/progs/local_storage_bench__get_seq.c | 12 + .../bpf/progs/local_storage_bench__hashmap.c | 13 + 10 files changed, 537 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_local_storage.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_local_storage.sh create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench.h create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_seq.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__hashmap.c
tools/testing/selftests/bpf/Makefile +5 -1
@@ -560,6 +560,9 @@ $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h $(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h +$(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench__get_seq.skel.h \ + $(OUTPUT)/local_storage_bench__get_int.skel.h \ + $(OUTPUT)/local_storage_bench__hashmap.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -571,7 +574,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ - $(OUTPUT)/bench_strncmp.o + $(OUTPUT)/bench_strncmp.o \ + $(OUTPUT)/bench_local_storage.o $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +57 -0
92 lines not on this page · raw message
tools/testing/selftests/bpf/bench.h +5 -0
@@ -34,12 +34,14 @@ struct bench_res {long hits;long drops;long false_hits; +long important_hits; };struct bench {const char *name;void (*validate)(void );void (*setup)(void ); +void (*teardown)(void );void *(*producer_thread)(void *ctx);void *(*consumer_thread)(void *ctx);void (*measure)(struct bench_res * res);
@@ -61,6 +63,9 @@ void false_hits_report_progress(int iter, struct bench_res *res, long delta_ns);void false_hits_report_final (struct bench_res res[],int res_cnt);void ops_report_progress (int iter,struct bench_res *res,long delta_ns);void ops_report_final (struct bench_res res[],int res_cnt); +void local_storage_report_progress (int iter,struct bench_res *res, +long delta_ns); +void local_storage_report_final (struct bench_res res[],int res_cnt);static inline __u64 get_time_ns (void ) {
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +332 -0
332 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_local_storage.sh new file +21 -0
@@ -0,0 +1,21 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +header "Local Storage" +subtitle "Hashmap Control w/ 500 maps" + summarize_local_storage "hashmap (control) sequential get: "\ + "$(./bench --nr_maps 500 local-storage-cache-hashmap-control)" + printf "\n" + +for i in 1 10 16 17 24 32 100 1000; do +subtitle "num_maps: $i" + summarize_local_storage "local_storage cache sequential get: "\ + "$(./bench --nr_maps $i local-storage-cache-seq-get)" + summarize_local_storage "local_storage cache interleaved get: "\ + "$(./bench --nr_maps $i local-storage-cache-int-get)" + printf "\n" +done
tools/testing/selftests/bpf/benchs/run_common.sh +17 -0
@@ -41,6 +41,16 @@ function ops() echo "$*" | sed -E "s/.*latency\s+([0-9]+\.[0-9]+\sns\/op).*/\1/" } +function local_storage() +{ + echo -n "hits throughput: " + echo -n "$*" | sed -E "s/.* hits throughput\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+\sM\sops\/s).*/\1/" + echo -n -e ", hits latency: " + echo -n "$*" | sed -E "s/.* hits latency\s+([0-9]+\.[0-9]+\sns\/op).*/\1/" + echo -n ", important_hits throughput: " + echo "$*" | sed -E "s/.*important_hits throughput\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+\sM\sops\/s).*/\1/" +} + function total() { echo "$*" | sed -E "s/.*total operations\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/"
@@ -67,6 +77,13 @@ function summarize_ops() printf "%-20s %s\n" "$bench" "$(ops $summary)" } +function summarize_local_storage() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s\n" "$bench" "$(local_storage $summary)" +} + function summarize_total() { bench="$1"
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +63 -0
63 lines not on this page · raw message
tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c new file +12 -0
@@ -0,0 +1,12 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#include "local_storage_bench.h" + +TASK_STORAGE_GET_LOOP_PROG (true); + +char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/local_storage_bench__get_seq.c new file +12 -0
@@ -0,0 +1,12 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#include "local_storage_bench.h" + +TASK_STORAGE_GET_LOOP_PROG (false); + +char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/local_storage_bench__hashmap.c new file +13 -0
@@ -0,0 +1,13 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#define LOOKUP_HASHMAP +#include "local_storage_bench.h" + +TASK_STORAGE_GET_LOOP_PROG (false); + +char _license[] SEC("license") = "GPL";
Signature · 1 line
2.30.2
Quoted 38 lines · Dave Marchevsky
Add a benchmarks to demonstrate the performance cliff for
local_storageget as the number oflocal_storagemaps increases beyond currentlocal_storageimplementation's cache size."sequential get" and "interleaved get" benchmarks are added, both of which do many
bpf_task_storage_getcalls on sets of tasklocal_storagemaps of various counts, while considering a single specific map to be 'important' and countingtask_storage_getsto the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many otherlocal_storagemaps exist and are accessed often.While "sequential get" benchmark does
bpf_task_storage_getfor map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4bpf_task_storage_getsfor the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs
local_storageget. The benchmark is identical to "sequential get", but creates and usesBPF_MAP_TYPE_HASHinstead of local storage.Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to
local_storageimplementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Quoted 8 lines
Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 69.649 ± 1.207 M ops/s, hits latency: 14.358 ns/op,important_hitsthroughput: 0.139 ± 0.002 M ops/snum_maps: 1
local_storagecache sequential get: hits throughput: 3.849 ± 0.035 M ops/s, hits latency: 259.803 ns/op,important_hitsthroughput: 3.849 ± 0.035 M ops/slocal_storagecache interleaved get: hits throughput: 6.881 ± 0.110 M ops/s, hits latency: 145.324 ns/op,important_hitsthroughput: 6.881 ± 0.110 M ops/s
this is huge drop in performance for num_maps is due to syscall and fentry overhead, is that right? How about making each syscall invocation do (roughly) the same amount of map/storage lookups per invocation to neutralize this overhead? Something like:
const volatile int map_cnt;
const volatile int iter_cnt;
...
for (i = 0; i < iter_cnt; i++) {
int map_idx = i % map_cnt;
do_lookup(map_idx, task);...
}
User-space can calculate iter_cnt to be closest exact multiple of map_cnt or you can just hard-code iter_cnt to fixed number (something like 10000 or some high enough value) and just leave with slightly uneven pattern for last round of looping.
But this way you make syscall/fentry overhead essentially fixed, which will avoid these counter-intuitive numbers.
Quoted 55 lines
num_maps: 10
local_storagecache sequential get: hits throughput: 20.339 ± 0.442 M ops/s, hits latency: 49.167 ns/op,important_hitsthroughput: 2.034 ± 0.044 M ops/slocal_storagecache interleaved get: hits throughput: 22.408 ± 0.606 M ops/s, hits latency: 44.627 ns/op,important_hitsthroughput: 8.003 ± 0.217 M ops/snum_maps: 16
local_storagecache sequential get: hits throughput: 24.428 ± 1.120 M ops/s, hits latency: 40.937 ns/op,important_hitsthroughput: 1.527 ± 0.070 M ops/slocal_storagecache interleaved get: hits throughput: 26.853 ± 0.825 M ops/s, hits latency: 37.240 ns/op,important_hitsthroughput: 8.544 ± 0.262 M ops/snum_maps: 17
local_storagecache sequential get: hits throughput: 24.158 ± 0.222 M ops/s, hits latency: 41.394 ns/op,important_hitsthroughput: 1.421 ± 0.013 M ops/slocal_storagecache interleaved get: hits throughput: 26.223 ± 0.201 M ops/s, hits latency: 38.134 ns/op,important_hitsthroughput: 7.981 ± 0.061 M ops/snum_maps: 24
local_storagecache sequential get: hits throughput: 16.820 ± 0.294 M ops/s, hits latency: 59.451 ns/op,important_hitsthroughput: 0.701 ± 0.012 M ops/slocal_storagecache interleaved get: hits throughput: 19.185 ± 0.212 M ops/s, hits latency: 52.125 ns/op,important_hitsthroughput: 5.396 ± 0.060 M ops/snum_maps: 32
local_storagecache sequential get: hits throughput: 11.998 ± 0.310 M ops/s, hits latency: 83.347 ns/op,important_hitsthroughput: 0.375 ± 0.010 M ops/slocal_storagecache interleaved get: hits throughput: 14.233 ± 0.265 M ops/s, hits latency: 70.259 ns/op,important_hitsthroughput: 3.972 ± 0.074 M ops/snum_maps: 100
local_storagecache sequential get: hits throughput: 5.780 ± 0.250 M ops/s, hits latency: 173.003 ns/op,important_hitsthroughput: 0.058 ± 0.002 M ops/slocal_storagecache interleaved get: hits throughput: 7.175 ± 0.312 M ops/s, hits latency: 139.381 ns/op,important_hitsthroughput: 1.874 ± 0.081 M ops/snum_maps: 1000
local_storagecache sequential get: hits throughput: 0.456 ± 0.011 M ops/s, hits latency: 2192.982 ns/op,important_hitsthroughput: 0.000 ± 0.000 M ops/slocal_storagecache interleaved get: hits throughput: 0.539 ± 0.005 M ops/s, hits latency: 1855.508 ns/op,important_hitsthroughput: 0.135 ± 0.001 M ops/sLooking at the "sequential get" results, it's clear that as the number of task
local_storagemaps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that currentlocal_storageimplementation assigns acache_idxto maps as they are created. Since "sequential get" is creating maps 0..n in order and then doingbpf_task_storage_getcalls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
As evidenced by the unintuitive-looking results for smaller
num_mapsbenchmark runs, overhead which is amortized across largernum_mapsruns dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem inlocal_storage_bench.hand ran the benchmark on the same host as the 'real' run. Results:Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 128.699 ± 1.267 M ops/s, hits latency: 7.770 ns/op,important_hitsthroughput: 0.257 ± 0.003 M ops/s
[...]
Quoted 57 lines
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.6ns sequential_get_1: ~17.9ns sequential_get_10: ~18.9ns sequential_get_16: ~19.0ns sequential_get_17: ~20.2ns sequential_get_24: ~42.2ns sequential_get_32: ~68.7ns sequential_get_100: ~163.3ns sequential_get_1000: ~2200nsClearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
Signed-off-by Dave Marchevsky <[email protected]>---
Changelog:v2 -> v3:
* Accessing 1k maps inARRAY_OF_MAPSdoesn't hitMAX_USED_MAPSlimit, so just use 1 program (Alexei)v1 -> v2:
* AdoptARRAY_OF_MAPSapproach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overheadtools/testing/selftests/bpf/Makefile | 6 +- tools/testing/selftests/bpf/bench.c | 57 +++ tools/testing/selftests/bpf/bench.h | 5 + .../bpf/benchs/bench_local_storage.c | 332 ++++++++++++++++++ .../bpf/benchs/run_bench_local_storage.sh | 21 ++ .../selftests/bpf/benchs/run_common.sh | 17 + .../selftests/bpf/progs/local_storage_bench.h | 63 ++++ .../bpf/progs/local_storage_bench__get_int.c | 12 + .../bpf/progs/local_storage_bench__get_seq.c | 12 + .../bpf/progs/local_storage_bench__hashmap.c | 13 + 10 files changed, 537 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_local_storage.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_local_storage.sh create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench.h create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_seq.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__hashmap.ctools/testing/selftests/bpf/Makefile +0
-0
tools/testing/selftests/bpf/Makefile $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ · line 565
Quoted 6 lines
tools/testing/selftests/bpf/Makefile +3
-0@@ -560,6 +560,9 @@ $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h $(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h +$(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench__get_seq.skel.h \ + $(OUTPUT)/local_storage_bench__get_int.skel.h \ + $(OUTPUT)/local_storage_bench__hashmap.skel.h
You really don't need 3 skeletons for this, you can parameterize everything with 2-3 .rodata variables and have fixed code and single skeleton header. It will also simplify your setup code, you won't need need those callbacks that abstract specific skeleton away. Much cleaner and simpler, IMO.
Please, try to simplify this and make it easier to maintain.
Quoted 58 lines
tools/testing/selftests/bpf/Makefile +2
-1$(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \@@ -571,7 +574,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ - $(OUTPUT)/bench_strncmp.o + $(OUTPUT)/bench_strncmp.o \ + $(OUTPUT)/bench_local_storage.o $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@tools/testing/selftests/bpf/bench.c +37
-0@@ -150,6 +150,53 @@ void ops_report_final(struct bench_res res[], int res_cnt)printf ("latency %8.3lf ns/op\n" ,1000.0 / hits_mean * env.producer_cnt); } +void local_storage_report_progress (int iter,struct bench_res *res, +long delta_ns) +{ +double important_hits_per_sec, hits_per_sec; +double delta_sec = delta_ns /1000000000.0 ; + + hits_per_sec = res->hits /1000000.0 / delta_sec; + important_hits_per_sec = res->important_hits /1000000.0 / delta_sec; + +printf ("Iter %3d (%7.3lfus): " , iter, (delta_ns -1000000000 ) /1000.0 ); + +printf ("hits %8.3lfM/s " , hits_per_sec); +printf ("important_hits %8.3lfM/s\n" , important_hits_per_sec); +} + +void local_storage_report_final (struct bench_res res[],int res_cnt) +{ +double important_hits_mean =0.0 , important_hits_stddev =0.0 ; +double hits_mean =0.0 , hits_stddev =0.0 ; +int i; + +for (i =0 ; i < res_cnt; i++) { + hits_mean += res[i].hits /1000000.0 / (0.0 + res_cnt); + important_hits_mean += res[i].important_hits /1000000.0 / (0.0 + res_cnt); + } + +if (res_cnt >1 ) { +for (i =0 ; i < res_cnt; i++) { + hits_stddev += (hits_mean - res[i].hits /1000000.0 ) * + (hits_mean - res[i].hits /1000000.0 ) / + (res_cnt -1.0 ); + important_hits_stddev += + (important_hits_mean - res[i].important_hits /1000000.0 ) * + (important_hits_mean - res[i].important_hits /1000000.0 ) / + (res_cnt -1.0 ); + } +
tools/testing/selftests/bpf/bench.c void ops_report_final(struct bench_res res[], int res_cnt) · line 199
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+ hits_stddev =sqrt (hits_stddev); + important_hits_stddev =sqrt (important_hits_stddev); + } +printf ("Summary: hits throughput %8.3lf \u00B1 %5.3lf M ops/s, " , + hits_mean, hits_stddev); +printf ("hits latency %8.3lf ns/op, " ,1000.0 / hits_mean); +printf ("important_hits throughput %8.3lf \u00B1 %5.3lf M ops/s\n" , + important_hits_mean, important_hits_stddev); +} +
We have hits_drops_report_progress/hits_drops_report_final which uses "hit" and "drop" terminology (admittedly confusing for this set of benchmarks), but if you ignore the "drop" part, it's exactly what you need - to track two independent values (in your case hit and important hit). You'll get rid of a good chunk of repetitive code with some statistics in it. You post-processing scripts will further hide this detail.
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +1
-0const char *argp_program_version ="benchmark" ;const char *argp_program_bug_address ="<[email protected]>" ; const char argp_program_doc[] =@@ -188,12 +235,14 @@ static const struct argp_option opts[] = {extern struct argp bench_ringbufs_argp;extern struct argp bench_bloom_map_argp;extern struct argp bench_bpf_loop_argp; +extern struct argp bench_local_storage_argp;extern struct argp bench_strncmp_argp;
[...]
Quoted 36 lines
tools/testing/selftests/bpf/bench.c +36
-0+ +static int setup_inner_map_and_load (int inner_fd) +{ +int err, mim_fd; + + err =bpf_map__set_inner_map_fd (ctx.array_of_maps, inner_fd); +if (err) +return -1 ; + + err = ctx.load_skel (ctx.skel); +if (err) +return -1 ; + + mim_fd =bpf_map__fd (ctx.array_of_maps); +if (mim_fd <0 ) +return -1 ; + +return mim_fd; +} + +static int load_btf (void ) +{ +static const char btf_str_sec[] ="\0" ; +__u32 btf_raw_types[] = { +/* int */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [1] */ + }; +struct btf_header btf_hdr = { + .magic =BTF_MAGIC , + .version =BTF_VERSION , + .hdr_len =sizeof (struct btf_header ), + .type_len =sizeof (btf_raw_types), + .str_off =sizeof (btf_raw_types), + .str_len =sizeof (btf_str_sec), + }; + __u8 raw_btf[sizeof(struct btf_header) + sizeof(btf_raw_types) +
tools/testing/selftests/bpf/bench.c
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+ sizeof(btf_str_sec)]; + +memcpy (raw_btf, &btf_hdr,sizeof (btf_hdr)); +memcpy (raw_btf +sizeof (btf_hdr), btf_raw_types,sizeof (btf_raw_types)); +memcpy (raw_btf +sizeof (btf_hdr) +sizeof (btf_raw_types), + btf_str_sec,sizeof (btf_str_sec)); + +return bpf_btf_load (raw_btf,sizeof (raw_btf),NULL ); +} +
please try using declarative map-in-map definition, hopefully it doesn't influence benchmark results. It will allow to avoid this low-level setup code completely.
Quoted 7 lines
tools/testing/selftests/bpf/bench.c +7
-0+static void __setup (struct bpf_program *prog,bool hashmap) +{ +int i, fd, mim_fd, err; +int btf_fd =0 ; + +LIBBPF_OPTS (bpf_map_create_opts, create_opts); +
[...]
tools/testing/selftests/bpf/bench.c
Quoted 6 lines
tools/testing/selftests/bpf/bench.c +6
-0+ +static void measure (struct bench_res *res) +{ +if (ctx.hits) + res->hits =atomic_swap (ctx.hits,0 ); +if (ctx.important_hits)
why these ifs? just swap, measure is called once a second, there is no need to optimize this
Quoted 8 lines
tools/testing/selftests/bpf/bench.c +8
-0+ res->important_hits =atomic_swap (ctx.important_hits,0 ); +} + +static inline void trigger_bpf_program (void ) +{ +syscall (__NR_getpgid); +} +
[...]
tools/testing/selftests/bpf/bench.c
Quoted 11 lines
tools/testing/selftests/bpf/bench.c +11
-0+#ifdef LOOKUP_HASHMAP +static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_map_lookup_elem (map, &zero);
shouldn't you use elem here as well to make it a bit more in line with bpf_task_storage_get()? This fixed zero is too optimistic and minimizes CPU cache usage, skewing results towards hashmap. It's cheaper to go access same location in hashmap over and over again, vs randomly jumping over N elements
Quoted 29 lines
tools/testing/selftests/bpf/bench.c +29
-0+__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#else +static int do_lookup (unsigned int elem,struct task_struct *task) +{ +void *map; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_task_storage_get (map, task,0 ,BPF_LOCAL_STORAGE_GET_F_CREATE ); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#endif /* LOOKUP_HASHMAP */ + +#define TASK_STORAGE_GET_LOOP_PROG (interleave) \ +SEC("fentry/" SYS_PREFIX "sys_getpgid") \ +int get_local(void *ctx) \ +{ \ + struct task_struct *task; \ + unsigned int i; \ + void *map; \
tools/testing/selftests/bpf/bench.c
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+ \ + task =bpf_get_current_task_btf (); \ +for (i =0 ; i <1000 ; i++) { \ +if (do_lookup (i, task)) \ +return 0 ; \ +if (interleave && i %3 ==0 ) \ +do_lookup (0 , task); \ + } \ +return 0 ; \ +}
I think
const volatile use_local_storage; /* set from user-space */
if (use_local_storage) {
do_lookup_storage()
} else {
do_lookup_hashmap()
}
is as clear (if not clearer) than having three separate skeletons built from single #include header parameterized by extra #defines.
Quoted 2 lines
tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c new file +0
-0
[...]
Quoted 69 lines · Andrii Nakryiko
Quoted 38 lines · Dave Marchevsky
Add a benchmarks to demonstrate the performance cliff for
local_storageget as the number oflocal_storagemaps increases beyond currentlocal_storageimplementation's cache size."sequential get" and "interleaved get" benchmarks are added, both of which do many
bpf_task_storage_getcalls on sets of tasklocal_storagemaps of various counts, while considering a single specific map to be 'important' and countingtask_storage_getsto the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many otherlocal_storagemaps exist and are accessed often.While "sequential get" benchmark does
bpf_task_storage_getfor map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4bpf_task_storage_getsfor the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs
local_storageget. The benchmark is identical to "sequential get", but creates and usesBPF_MAP_TYPE_HASHinstead of local storage.Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to
local_storageimplementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Quoted 8 lines
Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 69.649 ± 1.207 M ops/s, hits latency: 14.358 ns/op,important_hitsthroughput: 0.139 ± 0.002 M ops/snum_maps: 1
local_storagecache sequential get: hits throughput: 3.849 ± 0.035 M ops/s, hits latency: 259.803 ns/op,important_hitsthroughput: 3.849 ± 0.035 M ops/slocal_storagecache interleaved get: hits throughput: 6.881 ± 0.110 M ops/s, hits latency: 145.324 ns/op,important_hitsthroughput: 6.881 ± 0.110 M ops/sthis is huge drop in performance for
num_mapsis due to syscall and fentry overhead, is that right? How about making each syscall invocation do (roughly) the same amount of map/storage lookups per invocation to neutralize this overhead? Something like:const volatile int
map_cnt;
const volatile intiter_cnt;...
for (i = 0; i < iter_cnt; i++) { int map_idx = i % map_cnt; do_lookup(map_idx, task);...
}
Quoted 9 lines
User-space can calculate
iter_cntto be closest exact multiple ofmap_cntor you can just hard-codeiter_cntto fixed number (something like 10000 or some high enough value) and just leave with slightly uneven pattern for last round of looping.But this way you make syscall/fentry overhead essentially fixed, which will avoid these counter-intuitive numbers.
This worked! But had to use bpf_loop as verifier didn't like various attempts to loop 10k times. Overhead is much more consistent now (see v4 for numbers).
Quoted 200 lines
Quoted 55 lines
num_maps: 10
local_storagecache sequential get: hits throughput: 20.339 ± 0.442 M ops/s, hits latency: 49.167 ns/op,important_hitsthroughput: 2.034 ± 0.044 M ops/slocal_storagecache interleaved get: hits throughput: 22.408 ± 0.606 M ops/s, hits latency: 44.627 ns/op,important_hitsthroughput: 8.003 ± 0.217 M ops/snum_maps: 16
local_storagecache sequential get: hits throughput: 24.428 ± 1.120 M ops/s, hits latency: 40.937 ns/op,important_hitsthroughput: 1.527 ± 0.070 M ops/slocal_storagecache interleaved get: hits throughput: 26.853 ± 0.825 M ops/s, hits latency: 37.240 ns/op,important_hitsthroughput: 8.544 ± 0.262 M ops/snum_maps: 17
local_storagecache sequential get: hits throughput: 24.158 ± 0.222 M ops/s, hits latency: 41.394 ns/op,important_hitsthroughput: 1.421 ± 0.013 M ops/slocal_storagecache interleaved get: hits throughput: 26.223 ± 0.201 M ops/s, hits latency: 38.134 ns/op,important_hitsthroughput: 7.981 ± 0.061 M ops/snum_maps: 24
local_storagecache sequential get: hits throughput: 16.820 ± 0.294 M ops/s, hits latency: 59.451 ns/op,important_hitsthroughput: 0.701 ± 0.012 M ops/slocal_storagecache interleaved get: hits throughput: 19.185 ± 0.212 M ops/s, hits latency: 52.125 ns/op,important_hitsthroughput: 5.396 ± 0.060 M ops/snum_maps: 32
local_storagecache sequential get: hits throughput: 11.998 ± 0.310 M ops/s, hits latency: 83.347 ns/op,important_hitsthroughput: 0.375 ± 0.010 M ops/slocal_storagecache interleaved get: hits throughput: 14.233 ± 0.265 M ops/s, hits latency: 70.259 ns/op,important_hitsthroughput: 3.972 ± 0.074 M ops/snum_maps: 100
local_storagecache sequential get: hits throughput: 5.780 ± 0.250 M ops/s, hits latency: 173.003 ns/op,important_hitsthroughput: 0.058 ± 0.002 M ops/slocal_storagecache interleaved get: hits throughput: 7.175 ± 0.312 M ops/s, hits latency: 139.381 ns/op,important_hitsthroughput: 1.874 ± 0.081 M ops/snum_maps: 1000
local_storagecache sequential get: hits throughput: 0.456 ± 0.011 M ops/s, hits latency: 2192.982 ns/op,important_hitsthroughput: 0.000 ± 0.000 M ops/slocal_storagecache interleaved get: hits throughput: 0.539 ± 0.005 M ops/s, hits latency: 1855.508 ns/op,important_hitsthroughput: 0.135 ± 0.001 M ops/sLooking at the "sequential get" results, it's clear that as the number of task
local_storagemaps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that currentlocal_storageimplementation assigns acache_idxto maps as they are created. Since "sequential get" is creating maps 0..n in order and then doingbpf_task_storage_getcalls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
As evidenced by the unintuitive-looking results for smaller
num_mapsbenchmark runs, overhead which is amortized across largernum_mapsruns dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem inlocal_storage_bench.hand ran the benchmark on the same host as the 'real' run. Results:Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 128.699 ± 1.267 M ops/s, hits latency: 7.770 ns/op,important_hitsthroughput: 0.257 ± 0.003 M ops/s[...]
Quoted 57 lines
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.6ns sequential_get_1: ~17.9ns sequential_get_10: ~18.9ns sequential_get_16: ~19.0ns sequential_get_17: ~20.2ns sequential_get_24: ~42.2ns sequential_get_32: ~68.7ns sequential_get_100: ~163.3ns sequential_get_1000: ~2200nsClearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
Signed-off-by Dave Marchevsky <[email protected]>---
Changelog:v2 -> v3:
* Accessing 1k maps inARRAY_OF_MAPSdoesn't hitMAX_USED_MAPSlimit, so just use 1 program (Alexei)v1 -> v2:
* AdoptARRAY_OF_MAPSapproach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overheadtools/testing/selftests/bpf/Makefile | 6 +- tools/testing/selftests/bpf/bench.c | 57 +++ tools/testing/selftests/bpf/bench.h | 5 + .../bpf/benchs/bench_local_storage.c | 332 ++++++++++++++++++ .../bpf/benchs/run_bench_local_storage.sh | 21 ++ .../selftests/bpf/benchs/run_common.sh | 17 + .../selftests/bpf/progs/local_storage_bench.h | 63 ++++ .../bpf/progs/local_storage_bench__get_int.c | 12 + .../bpf/progs/local_storage_bench__get_seq.c | 12 + .../bpf/progs/local_storage_bench__hashmap.c | 13 + 10 files changed, 537 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_local_storage.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_local_storage.sh create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench.h create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_seq.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__hashmap.ctools/testing/selftests/bpf/Makefile +0
-0tools/testing/selftests/bpf/Makefile $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ · line 565
Quoted 6 lines
tools/testing/selftests/bpf/Makefile +3
-0@@ -560,6 +560,9 @@ $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h $(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h +$(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench__get_seq.skel.h \ + $(OUTPUT)/local_storage_bench__get_int.skel.h \ + $(OUTPUT)/local_storage_bench__hashmap.skel.hYou really don't need 3 skeletons for this, you can parameterize everything with 2-3 .rodata variables and have fixed code and single skeleton header. It will also simplify your setup code, you won't need need those callbacks that abstract specific skeleton away. Much cleaner and simpler, IMO.
Please, try to simplify this and make it easier to maintain.
Quoted 58 lines
tools/testing/selftests/bpf/Makefile +2
-1$(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \@@ -571,7 +574,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ - $(OUTPUT)/bench_strncmp.o + $(OUTPUT)/bench_strncmp.o \ + $(OUTPUT)/bench_local_storage.o $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@tools/testing/selftests/bpf/bench.c +37
-0@@ -150,6 +150,53 @@ void ops_report_final(struct bench_res res[], int res_cnt)printf ("latency %8.3lf ns/op\n" ,1000.0 / hits_mean * env.producer_cnt); } +void local_storage_report_progress (int iter,struct bench_res *res, +long delta_ns) +{ +double important_hits_per_sec, hits_per_sec; +double delta_sec = delta_ns /1000000000.0 ; + + hits_per_sec = res->hits /1000000.0 / delta_sec; + important_hits_per_sec = res->important_hits /1000000.0 / delta_sec; + +printf ("Iter %3d (%7.3lfus): " , iter, (delta_ns -1000000000 ) /1000.0 ); + +printf ("hits %8.3lfM/s " , hits_per_sec); +printf ("important_hits %8.3lfM/s\n" , important_hits_per_sec); +} + +void local_storage_report_final (struct bench_res res[],int res_cnt) +{ +double important_hits_mean =0.0 , important_hits_stddev =0.0 ; +double hits_mean =0.0 , hits_stddev =0.0 ; +int i; + +for (i =0 ; i < res_cnt; i++) { + hits_mean += res[i].hits /1000000.0 / (0.0 + res_cnt); + important_hits_mean += res[i].important_hits /1000000.0 / (0.0 + res_cnt); + } + +if (res_cnt >1 ) { +for (i =0 ; i < res_cnt; i++) { + hits_stddev += (hits_mean - res[i].hits /1000000.0 ) * + (hits_mean - res[i].hits /1000000.0 ) / + (res_cnt -1.0 ); + important_hits_stddev += + (important_hits_mean - res[i].important_hits /1000000.0 ) * + (important_hits_mean - res[i].important_hits /1000000.0 ) / + (res_cnt -1.0 ); + } +tools/testing/selftests/bpf/bench.c void ops_report_final(struct bench_res res[], int res_cnt) · line 199
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+ hits_stddev =sqrt (hits_stddev); + important_hits_stddev =sqrt (important_hits_stddev); + } +printf ("Summary: hits throughput %8.3lf \u00B1 %5.3lf M ops/s, " , + hits_mean, hits_stddev); +printf ("hits latency %8.3lf ns/op, " ,1000.0 / hits_mean); +printf ("important_hits throughput %8.3lf \u00B1 %5.3lf M ops/s\n" , + important_hits_mean, important_hits_stddev); +} +
Quoted 8 lines
We have hits_drops_report_progress/hits_drops_report_final which uses "hit" and "drop" terminology (admittedly confusing for this set of benchmarks), but if you ignore the "drop" part, it's exactly what you need - to track two independent values (in your case hit and important hit). You'll get rid of a good chunk of repetitive code with some statistics in it. You post-processing scripts will further hide this detail.
I considered doing this when working on v1 of the patch, but decided against it because 'drop' and 'hit' are independent while 'important_hit' and 'hit' are not. Every important_hit is also a hit.
The repetitive mean / stddev calculations are annoying, though. Added a 2nd commit to v4 which refactors them.
Quoted 55 lines
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +1
-0const char *argp_program_version ="benchmark" ;const char *argp_program_bug_address ="<[email protected]>" ; const char argp_program_doc[] =@@ -188,12 +235,14 @@ static const struct argp_option opts[] = {extern struct argp bench_ringbufs_argp;extern struct argp bench_bloom_map_argp;extern struct argp bench_bpf_loop_argp; +extern struct argp bench_local_storage_argp;extern struct argp bench_strncmp_argp;[...]
Quoted 42 lines
tools/testing/selftests/bpf/bench.c +42
-0+ +static int setup_inner_map_and_load (int inner_fd) +{ +int err, mim_fd; + + err =bpf_map__set_inner_map_fd (ctx.array_of_maps, inner_fd); +if (err) +return -1 ; + + err = ctx.load_skel (ctx.skel); +if (err) +return -1 ; + + mim_fd =bpf_map__fd (ctx.array_of_maps); +if (mim_fd <0 ) +return -1 ; + +return mim_fd; +} + +static int load_btf (void ) +{ +static const char btf_str_sec[] ="\0" ; +__u32 btf_raw_types[] = { +/* int */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [1] */ + }; +struct btf_header btf_hdr = { + .magic =BTF_MAGIC , + .version =BTF_VERSION , + .hdr_len =sizeof (struct btf_header ), + .type_len =sizeof (btf_raw_types), + .str_off =sizeof (btf_raw_types), + .str_len =sizeof (btf_str_sec), + }; +__u8 raw_btf[sizeof (struct btf_header ) +sizeof (btf_raw_types) + +sizeof (btf_str_sec)]; + +memcpy (raw_btf, &btf_hdr,sizeof (btf_hdr)); +memcpy (raw_btf +sizeof (btf_hdr), btf_raw_types,sizeof (btf_raw_types)); +memcpy (raw_btf +sizeof (btf_hdr) +sizeof (btf_raw_types), + btf_str_sec,sizeof (btf_str_sec));
Quoted 9 lines
tools/testing/selftests/bpf/bench.c
Quoted 4 lines
tools/testing/selftests/bpf/bench.c +4
-0+ +return bpf_btf_load (raw_btf,sizeof (raw_btf),NULL ); +} +please try using declarative map-in-map definition, hopefully it doesn't influence benchmark results. It will allow to avoid this low-level setup code completely.
Forgot to call this out in v4 changelog, but made this change.
It was more frustrating than expected, though, as it was necessary to grab btf_key_type_id / value_type_id from the inner map still, and the helpers would only return valid type_id if called before prog load.
Quoted 40 lines
Quoted 7 lines
tools/testing/selftests/bpf/bench.c +7
-0+static void __setup (struct bpf_program *prog,bool hashmap) +{ +int i, fd, mim_fd, err; +int btf_fd =0 ; + +LIBBPF_OPTS (bpf_map_create_opts, create_opts); +[...]
tools/testing/selftests/bpf/bench.c
Quoted 6 lines
tools/testing/selftests/bpf/bench.c +6
-0+ +static void measure (struct bench_res *res) +{ +if (ctx.hits) + res->hits =atomic_swap (ctx.hits,0 ); +if (ctx.important_hits)why these ifs? just swap, measure is called once a second, there is no need to optimize this
Quoted 8 lines
tools/testing/selftests/bpf/bench.c +8
-0+ res->important_hits =atomic_swap (ctx.important_hits,0 ); +} + +static inline void trigger_bpf_program (void ) +{ +syscall (__NR_getpgid); +} +[...]
Quoted 9 lines
tools/testing/selftests/bpf/bench.c +9
-0+#ifdef LOOKUP_HASHMAP +static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ;
Quoted 9 lines
tools/testing/selftests/bpf/bench.c
Quoted 2 lines
tools/testing/selftests/bpf/bench.c +2
-0+ +bpf_map_lookup_elem (map, &zero);shouldn't you use elem here as well to make it a bit more in line with
bpf_task_storage_get()? This fixed zero is too optimistic and minimizes CPU cache usage, skewing results towards hashmap. It's cheaper to go access same location in hashmap over and over again, vs randomly jumping over N elements
Both hashmap and local_storage benchmarks are always grabbing key 0 from the map. v4 makes this more clear. Intent is to measure how long it takes to access local_storage map, not random element within it.
Every other comment here that wasn't responded to was addressed in v4.
Quoted 59 lines
Quoted 29 lines
tools/testing/selftests/bpf/bench.c +29
-0+__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#else +static int do_lookup (unsigned int elem,struct task_struct *task) +{ +void *map; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_task_storage_get (map, task,0 ,BPF_LOCAL_STORAGE_GET_F_CREATE ); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#endif /* LOOKUP_HASHMAP */ + +#define TASK_STORAGE_GET_LOOP_PROG (interleave) \ +SEC("fentry/" SYS_PREFIX "sys_getpgid") \ +int get_local(void *ctx) \ +{ \ + struct task_struct *task; \ + unsigned int i; \ + void *map; \tools/testing/selftests/bpf/bench.c
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+ \ + task =bpf_get_current_task_btf (); \ +for (i =0 ; i <1000 ; i++) { \ +if (do_lookup (i, task)) \ +return 0 ; \ +if (interleave && i %3 ==0 ) \ +do_lookup (0 , task); \ + } \ +return 0 ; \ +}I think
const volatile
use_local_storage; /* set from user-space */if (
use_local_storage) {
do_lookup_storage()
} else {
do_lookup_hashmap()
}is as clear (if not clearer) than having three separate skeletons built from single #include header parameterized by extra #defines.
Quoted 2 lines
tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c new file +0
-0[...]