New benchmark for hashmap lookups
Subsystems (3)
cover New benchmark for hashmap lookups
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).
Anton Protopopov (6):
selftest/bpf/benchs: fix a typo in bpf_hashmap_full_update selftest/bpf/benchs: make a function static in bpf_hashmap_full_update selftest/bpf/benchs: enhance argp parsing selftest/bpf/benchs: make quiet option common selftest/bpf/benchs: print less if the quiet option is set selftest/bpf/benchs: Add benchmark for hashmap lookups
tools/testing/selftests/bpf/Makefile | 5 +- tools/testing/selftests/bpf/bench.c | 126 +++++++- tools/testing/selftests/bpf/bench.h | 24 ++ .../bpf/benchs/bench_bloom_filter_map.c | 6 - .../benchs/bench_bpf_hashmap_full_update.c | 4 +- .../bpf/benchs/bench_bpf_hashmap_lookup.c | 277 ++++++++++++++++++ .../selftests/bpf/benchs/bench_bpf_loop.c | 4 - .../bpf/benchs/bench_local_storage.c | 5 - .../bench_local_storage_rcu_tasks_trace.c | 20 +- .../selftests/bpf/benchs/bench_ringbufs.c | 8 - .../selftests/bpf/benchs/bench_strncmp.c | 4 - .../run_bench_bpf_hashmap_full_update.sh | 2 +- .../selftests/bpf/progs/bpf_hashmap_lookup.c | 61 ++++ 13 files changed, 486 insertions(+), 60 deletions(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c
Signature · 1 line
2.34.1
PATCH 1/6 selftest/bpf/benchs: fix a typo in bpf_hashmap_full_update
To call the bpf_hashmap_full_update benchmark, one should say:
bench bpf-hashmap-ful-update
The patch adds a missing 'l' to the benchmark name.
--- .../selftests/bpf/benchs/bench_bpf_hashmap_full_update.c | 2 +- .../selftests/bpf/benchs/run_bench_bpf_hashmap_full_update.sh | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_full_update.c +1 -1
@@ -85,7 +85,7 @@ void hashmap_report_final(struct bench_res res[], int res_cnt) }const struct bench bench_bpf_hashmap_full_update = { - .name ="bpf-hashmap-ful-update" , + .name ="bpf-hashmap-full-update" , .validate = validate, .setup = setup, .producer_thread = producer,
tools/testing/selftests/bpf/benchs/run_bench_bpf_hashmap_full_update.sh +1 -1
@@ -6,6 +6,6 @@ source ./benchs/run_common.sh set -eufo pipefail nr_threads=`expr $(cat /proc/cpuinfo | grep "processor"| wc -l) - 1` -summary=$($RUN_BENCH -p $nr_threads bpf-hashmap-ful-update) +summary=$($RUN_BENCH -p $nr_threads bpf-hashmap-full-update) printf "$summary" printf "\n"
Signature · 1 line
2.34.1
PATCH 2/6 selftest/bpf/benchs: make a function static in bpf_hashmap_full_update
In reply to Anton ProtopopovThe hashmap_report_final callback function defined in the benchs/bench_bpf_hashmap_full_update.c file should be static.
--- .../selftests/bpf/benchs/bench_bpf_hashmap_full_update.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_full_update.c +1 -1
@@ -68,7 +68,7 @@ static void setup(void)bpf_map_update_elem (map_fd, &i, &i,BPF_ANY ); } -void hashmap_report_final (struct bench_res res[],int res_cnt) +static void hashmap_report_final (struct bench_res res[],int res_cnt) {unsigned int nr_cpus =bpf_num_possible_cpus ();int i;
Signature · 1 line
2.34.1
PATCH 3/6 selftest/bpf/benchs: enhance argp parsing
In reply to Anton ProtopopovTo parse command line the bench utility uses the argp_parse() function. This function takes as an argument a parent 'struct argp' structure which defines common command line options and an array of children 'struct argp' structures which defines additional command line options for particular benchmarks. This implementation doesn't allow benchmarks to share option names, e.g., if two benchmarks want to use, say, the --option option, then only one of them will succeed (the first one encountered in the array). This will be convenient if we could use the same option names in different benchmarks (with the same semantics, e.g., --nr_loops=N).
Fix this by calling the argp_parse() function twice. The first call is needed to find the benchmark name. Given the name, we can patch the list of argp children to only include the correct list of option. This way the right parser will be executed. (If there's no a specific list of arguments, then only one call is enough.) As was mentioned above, arguments with same names should have the same semantics (which means in this case "taking a parameter or not"), but can have different description and will have different parsers.
As we now can share option names, this also makes sense to share the option ids. Previously every benchmark defined a separate enum, like
enum {
ARG_SMTH = 9000,
ARG_SMTH_ELSE = 9001,
};These ids were later used to distinguish between command line options:
static const struct argp_option opts[] = {
{ "smth", ARG_SMTH, "SMTH", 0,
"Set number of smth to configure smth"},
{ "smth_else", ARG_SMTH_ELSE, "SMTH_ELSE", 0,
"Set number of smth_else to configure smth else"},
...Move arguments id definitions to bench.h such that they are visible to every benchmark (and such that there's no need to grep if this number is defined already or not).
--- tools/testing/selftests/bpf/bench.c | 98 +++++++++++++++++-- tools/testing/selftests/bpf/bench.h | 20 ++++ .../bpf/benchs/bench_bloom_filter_map.c | 6 -- .../selftests/bpf/benchs/bench_bpf_loop.c | 4 - .../bpf/benchs/bench_local_storage.c | 5 - .../bench_local_storage_rcu_tasks_trace.c | 6 -- .../selftests/bpf/benchs/bench_ringbufs.c | 8 -- .../selftests/bpf/benchs/bench_strncmp.c | 4 - 8 files changed, 110 insertions(+), 41 deletions(-)
tools/testing/selftests/bpf/bench.c +90 -8
@@ -249,11 +249,6 @@ const char argp_program_doc[] =" # run 'count-local' with 16 producer and 8 consumer thread, pinned to CPUs\n" " benchmark -p16 -c8 -a count-local\n" ; -enum { -ARG_PROD_AFFINITY_SET =1000 , -ARG_CONS_AFFINITY_SET =1001 , -}; -static const struct argp_option opts[] = { {"list" ,'l' ,NULL ,0 ,"List available benchmarks" }, {"duration" ,'d' ,"SEC" ,0 ,"Duration of benchmark, seconds" },
@@ -276,7 +271,7 @@ extern struct argp bench_local_storage_argp;extern struct argp bench_local_storage_rcu_tasks_trace_argp;extern struct argp bench_strncmp_argp; -static const struct argp_child bench_parsers[] = { +static struct argp_child bench_parsers[] = { { &bench_ringbufs_argp,0 ,"Ring buffers benchmark" ,0 }, { &bench_bloom_map_argp,0 ,"Bloom filter map benchmark" ,0 }, { &bench_bpf_loop_argp,0 ,"bpf_loop helper benchmark" ,0 },
@@ -287,9 +282,10 @@ static const struct argp_child bench_parsers[] = { {}, }; +static int pos_args; +static error_t parse_arg (int key,char *arg,struct argp_state *state) { -static int pos_args;switch (key) {case 'v' :
@@ -359,6 +355,69 @@ static error_t parse_arg(int key, char *arg, struct argp_state *state)return 0 ; } +struct argp *bench_name_to_argp (const char *bench_name) +{ + +#define _SCMP (NAME ) (!strcmp(bench_name, NAME)) + +if (_SCMP ("bloom-lookup" ) || +_SCMP ("bloom-update" ) || +_SCMP ("bloom-false-positive" ) || +_SCMP ("hashmap-without-bloom" ) || +_SCMP ("hashmap-with-bloom" )) +return &bench_bloom_map_argp; + +if (_SCMP ("rb-libbpf" ) || +_SCMP ("rb-custom" ) || +_SCMP ("pb-libbpf" ) || +_SCMP ("pb-custom" )) +return &bench_ringbufs_argp; + +if (_SCMP ("local-storage-cache-seq-get" ) || +_SCMP ("local-storage-cache-int-get" ) || +_SCMP ("local-storage-cache-hashmap-control" )) +return &bench_local_storage_argp; + +if (_SCMP ("local-storage-tasks-trace" )) +return &bench_local_storage_rcu_tasks_trace_argp; + +if (_SCMP ("strncmp-no-helper" ) || +_SCMP ("strncmp-helper" )) +return &bench_strncmp_argp; + +if (_SCMP ("bpf-loop" )) +return &bench_bpf_loop_argp; + +/* no extra arguments */ +if (_SCMP ("count-global" ) || +_SCMP ("count-local" ) || +_SCMP ("rename-base" ) || +_SCMP ("rename-kprobe" ) || +_SCMP ("rename-kretprobe" ) || +_SCMP ("rename-rawtp" ) || +_SCMP ("rename-fentry" ) || +_SCMP ("rename-fexit" ) || +_SCMP ("trig-base" ) || +_SCMP ("trig-tp" ) || +_SCMP ("trig-rawtp" ) || +_SCMP ("trig-kprobe" ) || +_SCMP ("trig-fentry" ) || +_SCMP ("trig-fentry-sleep" ) || +_SCMP ("trig-fmodret" ) || +_SCMP ("trig-uprobe-base" ) || +_SCMP ("trig-uprobe-with-nop" ) || +_SCMP ("trig-uretprobe-with-nop" ) || +_SCMP ("trig-uprobe-without-nop" ) || +_SCMP ("trig-uretprobe-without-nop" ) || +_SCMP ("bpf-hashmap-full-update" )) +return NULL ; + +#undef _SCMP + +fprintf (stderr,"%s: bench %s is unknown\n" , __func__, bench_name); +exit (1 ); +} +static void parse_cmdline_args (int argc,char **argv) {static const struct argp argp = {
@@ -367,12 +426,35 @@ static void parse_cmdline_args(int argc, char **argv) .doc = argp_program_doc, .children = bench_parsers, }; +static struct argp *bench_argp; + +/* Parse args for the first time to get bench name */ if (argp_parse (&argp, argc, argv,0 ,NULL ,NULL ))exit (1 ); -if (!env.list && !env.bench_name) { + +if (env.list) +return ; + +if (!env.bench_name) {argp_help (&argp, stderr,ARGP_HELP_DOC ,"bench" );exit (1 ); } + +/* Now check if there are custom options available. If not, then +* everything is done, if yes, then we need to patch bench_parsers +* so that bench_parsers[0] points to the right 'struct argp', and +* bench_parsers[1] terminates the list. +*/ + bench_argp =bench_name_to_argp (env.bench_name); +if (bench_argp) { + bench_parsers[0 ].argp = bench_argp; + bench_parsers[0 ].header = env.bench_name; +memset (&bench_parsers[1 ],0 ,sizeof (bench_parsers[1 ])); + + pos_args =0 ; +if (argp_parse (&argp, argc, argv,0 ,NULL ,NULL )) +exit (1 ); + } }static void collect_measurements (long delta_ns);
tools/testing/selftests/bpf/bench.h +20 -0
@@ -101,3 +101,23 @@ static inline long atomic_swap(long *value, long n) {return __atomic_exchange_n (value, n, __ATOMIC_RELAXED); } + +enum { +ARG_PROD_AFFINITY_SET =1000 , +ARG_CONS_AFFINITY_SET , +ARG_RB_BACK2BACK , +ARG_RB_USE_OUTPUT , +ARG_RB_BATCH_CNT , +ARG_RB_SAMPLED , +ARG_RB_SAMPLE_RATE , +ARG_NR_ENTRIES , +ARG_NR_HASH_FUNCS , +ARG_VALUE_SIZE , +ARG_NR_LOOPS , +ARG_CMP_STR_LEN , +ARG_NR_MAPS , +ARG_HASHMAP_NR_KEYS_USED , +ARG_NR_PROCS , +ARG_KTHREAD_PID , +ARG_QUIET , +};
tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +0 -6
@@ -45,12 +45,6 @@ static struct { .value_size = 8, }; -enum { -ARG_NR_ENTRIES =3000 , -ARG_NR_HASH_FUNCS =3001 , -ARG_VALUE_SIZE =3002 , -}; -static const struct argp_option opts[] = { {"nr_entries" ,ARG_NR_ENTRIES ,"NR_ENTRIES" ,0 ,"Set number of expected unique entries in the bloom filter" },
tools/testing/selftests/bpf/benchs/bench_bpf_loop.c +0 -4
@@ -16,10 +16,6 @@ static struct { .nr_loops = 10, }; -enum { -ARG_NR_LOOPS =4000 , -}; -static const struct argp_option opts[] = { {"nr_loops" ,ARG_NR_LOOPS ,"nr_loops" ,0 ,"Set number of loops for the bpf_loop helper" },
tools/testing/selftests/bpf/benchs/bench_local_storage.c +0 -5
@@ -17,11 +17,6 @@ static struct { .hashmap_nr_keys_used = 1000, }; -enum { -ARG_NR_MAPS =6000 , -ARG_HASHMAP_NR_KEYS_USED =6001 , -}; -static const struct argp_option opts[] = { {"nr_maps" ,ARG_NR_MAPS ,"NR_MAPS" ,0 ,"Set number of local_storage maps" },
tools/testing/selftests/bpf/benchs/bench_local_storage_rcu_tasks_trace.c +0 -6
@@ -19,12 +19,6 @@ static struct { .quiet = false, }; -enum { -ARG_NR_PROCS =7000 , -ARG_KTHREAD_PID =7001 , -ARG_QUIET =7002 , -}; -static const struct argp_option opts[] = { {"nr_procs" ,ARG_NR_PROCS ,"NR_PROCS" ,0 ,"Set number of user processes to spin up" },
tools/testing/selftests/bpf/benchs/bench_ringbufs.c +0 -8
@@ -29,14 +29,6 @@ static struct { .perfbuf_sz = 128, }; -enum { -ARG_RB_BACK2BACK =2000 , -ARG_RB_USE_OUTPUT =2001 , -ARG_RB_BATCH_CNT =2002 , -ARG_RB_SAMPLED =2003 , -ARG_RB_SAMPLE_RATE =2004 , -}; -static const struct argp_option opts[] = { {"rb-b2b" ,ARG_RB_BACK2BACK ,NULL ,0 ,"Back-to-back mode" }, {"rb-use-output" ,ARG_RB_USE_OUTPUT ,NULL ,0 ,"Use bpf_ringbuf_output() instead of bpf_ringbuf_reserve()" },
tools/testing/selftests/bpf/benchs/bench_strncmp.c +0 -4
@@ -14,10 +14,6 @@ static struct strncmp_args { .cmp_str_len = 32, }; -enum { -ARG_CMP_STR_LEN =5000 , -}; -static const struct argp_option opts[] = { {"cmp-str-len" ,ARG_CMP_STR_LEN ,"CMP_STR_LEN" ,0 ,"Set the length of compared string" },
Signature · 1 line
2.34.1
Re: [PATCH bpf-next 3/6] selftest/bpf/benchs: enhance argp parsing
Quoted 36 lines · Anton Protopopov
To parse command line the bench utility uses the
argp_parse()function. This function takes as an argument a parent 'struct argp' structure which defines common command line options and an array of children 'struct argp' structures which defines additional command line options for particular benchmarks. This implementation doesn't allow benchmarks to share option names, e.g., if two benchmarks want to use, say, the --option option, then only one of them will succeed (the first one encountered in the array). This will be convenient if we could use the same option names in different benchmarks (with the same semantics, e.g., --nr_loops=N).Fix this by calling the
argp_parse()function twice. The first call is needed to find the benchmark name. Given the name, we can patch the list of argp children to only include the correct list of option. This way the right parser will be executed. (If there's no a specific list of arguments, then only one call is enough.) As was mentioned above, arguments with same names should have the same semantics (which means in this case "taking a parameter or not"), but can have different description and will have different parsers.As we now can share option names, this also makes sense to share the option ids. Previously every benchmark defined a separate enum, like
enum { ARG_SMTH = 9000, ARG_SMTH_ELSE = 9001, };These ids were later used to distinguish between command line options:
static const struct argp_option opts[] = { { "smth", ARG_SMTH, "SMTH", 0, "Set number of smth to configure smth"}, { "smth_else", ARG_SMTH_ELSE, "SMTH_ELSE", 0, "Set number of smth_else to configure smth else"}, ...
Quoted 3 lines
Move arguments id definitions to
bench.hsuch that they are visible to every benchmark (and such that there's no need to grep if this number is defined already or not).
On the other hand, if each benchmark defines their own set of IDs and parser, that keeps benchmarks more self-contained. Is there a real need to centralize everything? I don't see much benefit, tbh.
If we want to centralize, then we can just bypass all the child parser machinery and have one centralized list of arguments. But I think it's good to have each benchmark self-contained and independent from other benchmarks.
Quoted 13 lines
Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/bench.c | 98 +++++++++++++++++-- tools/testing/selftests/bpf/bench.h | 20 ++++ .../bpf/benchs/bench_bloom_filter_map.c | 6 -- .../selftests/bpf/benchs/bench_bpf_loop.c | 4 - .../bpf/benchs/bench_local_storage.c | 5 - .../bench_local_storage_rcu_tasks_trace.c | 6 -- .../selftests/bpf/benchs/bench_ringbufs.c | 8 -- .../selftests/bpf/benchs/bench_strncmp.c | 4 - 8 files changed, 110 insertions(+), 41 deletions(-)
[...]
Quoted 49 lines
tools/testing/selftests/bpf/bench.c +49
-0+struct argp *bench_name_to_argp (const char *bench_name) +{ + +#define _SCMP (NAME ) (!strcmp(bench_name, NAME)) + +if (_SCMP ("bloom-lookup" ) || +_SCMP ("bloom-update" ) || +_SCMP ("bloom-false-positive" ) || +_SCMP ("hashmap-without-bloom" ) || +_SCMP ("hashmap-with-bloom" )) +return &bench_bloom_map_argp; + +if (_SCMP ("rb-libbpf" ) || +_SCMP ("rb-custom" ) || +_SCMP ("pb-libbpf" ) || +_SCMP ("pb-custom" )) +return &bench_ringbufs_argp; + +if (_SCMP ("local-storage-cache-seq-get" ) || +_SCMP ("local-storage-cache-int-get" ) || +_SCMP ("local-storage-cache-hashmap-control" )) +return &bench_local_storage_argp; + +if (_SCMP ("local-storage-tasks-trace" )) +return &bench_local_storage_rcu_tasks_trace_argp; + +if (_SCMP ("strncmp-no-helper" ) || +_SCMP ("strncmp-helper" )) +return &bench_strncmp_argp; + +if (_SCMP ("bpf-loop" )) +return &bench_bpf_loop_argp; + +/* no extra arguments */ + if (_SCMP("count-global") || + _SCMP("count-local") || + _SCMP("rename-base") || + _SCMP("rename-kprobe") || + _SCMP("rename-kretprobe") || + _SCMP("rename-rawtp") || + _SCMP("rename-fentry") || + _SCMP("rename-fexit") || + _SCMP("trig-base") || + _SCMP("trig-tp") || + _SCMP("trig-rawtp") || + _SCMP("trig-kprobe") || + _SCMP("trig-fentry") || + _SCMP("trig-fentry-sleep") || + _SCMP("trig-fmodret") ||
tools/testing/selftests/bpf/bench.c static error_t parse_arg(int key, char *arg, struct argp_state *state) · line 416
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+_SCMP ("trig-uprobe-base" ) || +_SCMP ("trig-uprobe-with-nop" ) || +_SCMP ("trig-uretprobe-with-nop" ) || +_SCMP ("trig-uprobe-without-nop" ) || +_SCMP ("trig-uretprobe-without-nop" ) || + _SCMP("bpf-hashmap-full-update")) + return NULL; + +#undef _SCMP +
it's not good to have to maintain a separate list of benchmark names here. Let's maybe extend struct bench to specify extra parser and use that to figure out if we need to run nested child parser?
tools/testing/selftests/bpf/bench.c static void parse_cmdline_args(int argc, char **argv) · line 429
Quoted 12 lines
tools/testing/selftests/bpf/bench.c +5
-0+fprintf (stderr,"%s: bench %s is unknown\n" , __func__, bench_name); +exit (1 ); +} +static void parse_cmdline_args (int argc,char **argv) {static const struct argp argp = {@@ -367,12 +426,35 @@ static void parse_cmdline_args(int argc, char **argv) .doc = argp_program_doc, .children = bench_parsers, }; +static struct argp *bench_argp;
nit: do you need static?
Quoted 19 lines
tools/testing/selftests/bpf/bench.c +13
-1+ +/* Parse args for the first time to get bench name */ if (argp_parse (&argp, argc, argv,0 ,NULL ,NULL ))exit (1 ); -if (!env.list && !env.bench_name) { + +if (env.list) +return ; + +if (!env.bench_name) {argp_help (&argp, stderr,ARGP_HELP_DOC ,"bench" );exit (1 ); } + +/* Now check if there are custom options available. If not, then +* everything is done, if yes, then we need to patch bench_parsers +* so that bench_parsers[0] points to the right 'struct argp', and +* bench_parsers[1] terminates the list. +*/
tools/testing/selftests/bpf/bench.c static void parse_cmdline_args(int argc, char **argv) · line 457
Quoted 10 lines
tools/testing/selftests/bpf/bench.c +10
-0+ bench_argp =bench_name_to_argp (env.bench_name); +if (bench_argp) { + bench_parsers[0 ].argp = bench_argp; + bench_parsers[0 ].header = env.bench_name; +memset (&bench_parsers[1 ],0 ,sizeof (bench_parsers[1 ])); + + pos_args =0 ; +if (argp_parse (&argp, argc, argv,0 ,NULL ,NULL )) +exit (1 ); + }
this also feels like a big hack, why can't you just construct a single-item array based on child parser, instead of overwriting global array?
Quoted 3 lines
tools/testing/selftests/bpf/bench.c +0
-0}static void collect_measurements (long delta_ns);
[...]
Re: [PATCH bpf-next 3/6] selftest/bpf/benchs: enhance argp parsing
Quoted 41 lines · Andrii Nakryiko
Quoted 36 lines · Anton Protopopov
To parse command line the bench utility uses the
argp_parse()function. This function takes as an argument a parent 'struct argp' structure which defines common command line options and an array of children 'struct argp' structures which defines additional command line options for particular benchmarks. This implementation doesn't allow benchmarks to share option names, e.g., if two benchmarks want to use, say, the --option option, then only one of them will succeed (the first one encountered in the array). This will be convenient if we could use the same option names in different benchmarks (with the same semantics, e.g., --nr_loops=N).Fix this by calling the
argp_parse()function twice. The first call is needed to find the benchmark name. Given the name, we can patch the list of argp children to only include the correct list of option. This way the right parser will be executed. (If there's no a specific list of arguments, then only one call is enough.) As was mentioned above, arguments with same names should have the same semantics (which means in this case "taking a parameter or not"), but can have different description and will have different parsers.As we now can share option names, this also makes sense to share the option ids. Previously every benchmark defined a separate enum, like
enum { ARG_SMTH = 9000, ARG_SMTH_ELSE = 9001, };These ids were later used to distinguish between command line options:
static const struct argp_option opts[] = { { "smth", ARG_SMTH, "SMTH", 0, "Set number of smth to configure smth"}, { "smth_else", ARG_SMTH_ELSE, "SMTH_ELSE", 0, "Set number of smth_else to configure smth else"}, ...Quoted 3 lines
Move arguments id definitions to
bench.hsuch that they are visible to every benchmark (and such that there's no need to grep if this number is defined already or not).
Quoted 8 lines
On the other hand, if each benchmark defines their own set of IDs and parser, that keeps benchmarks more self-contained. Is there a real need to centralize everything? I don't see much benefit, tbh.
If we want to centralize, then we can just bypass all the child parser machinery and have one centralized list of arguments. But I think it's good to have each benchmark self-contained and independent from other benchmarks.
When I was adding a new bench, it looked simpler to just add IDs to a global list than to grep for what ID is not defined yet. This doesn't matter much though, I can switch back to local IDs.
Quoted 71 lines
Quoted 13 lines
Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/bench.c | 98 +++++++++++++++++-- tools/testing/selftests/bpf/bench.h | 20 ++++ .../bpf/benchs/bench_bloom_filter_map.c | 6 -- .../selftests/bpf/benchs/bench_bpf_loop.c | 4 - .../bpf/benchs/bench_local_storage.c | 5 - .../bench_local_storage_rcu_tasks_trace.c | 6 -- .../selftests/bpf/benchs/bench_ringbufs.c | 8 -- .../selftests/bpf/benchs/bench_strncmp.c | 4 - 8 files changed, 110 insertions(+), 41 deletions(-)[...]
Quoted 55 lines
tools/testing/selftests/bpf/bench.c +55
-0+struct argp *bench_name_to_argp (const char *bench_name) +{ + +#define _SCMP (NAME ) (!strcmp(bench_name, NAME)) + +if (_SCMP ("bloom-lookup" ) || +_SCMP ("bloom-update" ) || +_SCMP ("bloom-false-positive" ) || +_SCMP ("hashmap-without-bloom" ) || +_SCMP ("hashmap-with-bloom" )) +return &bench_bloom_map_argp; + +if (_SCMP ("rb-libbpf" ) || +_SCMP ("rb-custom" ) || +_SCMP ("pb-libbpf" ) || +_SCMP ("pb-custom" )) +return &bench_ringbufs_argp; + +if (_SCMP ("local-storage-cache-seq-get" ) || +_SCMP ("local-storage-cache-int-get" ) || +_SCMP ("local-storage-cache-hashmap-control" )) +return &bench_local_storage_argp; + +if (_SCMP ("local-storage-tasks-trace" )) +return &bench_local_storage_rcu_tasks_trace_argp; + +if (_SCMP ("strncmp-no-helper" ) || +_SCMP ("strncmp-helper" )) +return &bench_strncmp_argp; + +if (_SCMP ("bpf-loop" )) +return &bench_bpf_loop_argp; + +/* no extra arguments */ +if (_SCMP ("count-global" ) || +_SCMP ("count-local" ) || +_SCMP ("rename-base" ) || +_SCMP ("rename-kprobe" ) || +_SCMP ("rename-kretprobe" ) || +_SCMP ("rename-rawtp" ) || +_SCMP ("rename-fentry" ) || +_SCMP ("rename-fexit" ) || +_SCMP ("trig-base" ) || +_SCMP ("trig-tp" ) || +_SCMP ("trig-rawtp" ) || +_SCMP ("trig-kprobe" ) || +_SCMP ("trig-fentry" ) || +_SCMP ("trig-fentry-sleep" ) || +_SCMP ("trig-fmodret" ) || +_SCMP ("trig-uprobe-base" ) || +_SCMP ("trig-uprobe-with-nop" ) || +_SCMP ("trig-uretprobe-with-nop" ) || +_SCMP ("trig-uprobe-without-nop" ) || +_SCMP ("trig-uretprobe-without-nop" ) || +_SCMP ("bpf-hashmap-full-update" ))
Quoted 8 lines
tools/testing/selftests/bpf/bench.c static error_t parse_arg(int key, char *arg, struct argp_state *state) · line 416
Quoted 4 lines
tools/testing/selftests/bpf/bench.c +4
-0+return NULL ; + +#undef _SCMP +it's not good to have to maintain a separate list of benchmark names here. Let's maybe extend struct bench to specify extra parser and use that to figure out if we need to run nested child parser?
Yes, right, so then I can do something like
struct argp *bench_name_to_argp(const char *bench_name)
{
int i;
for (i = 0; i < ARRAY_SIZE(benchs); i++)
if (!strcmp(bench_name, benchs[i]->name))
return benchs[i]->argp;
fprintf(stderr, "benchmark '%s' not found\n", bench_name);
exit(1);
}Quoted 15 lines
tools/testing/selftests/bpf/bench.c static void parse_cmdline_args(int argc, char **argv) · line 429
Quoted 13 lines
tools/testing/selftests/bpf/bench.c +5
-0+fprintf (stderr,"%s: bench %s is unknown\n" , __func__, bench_name); +exit (1 ); +} +static void parse_cmdline_args (int argc,char **argv) {static const struct argp argp = {@@ -367,12 +426,35 @@ static void parse_cmdline_args(int argc, char **argv) .doc = argp_program_doc, .children = bench_parsers, }; +static struct argp *bench_argp;nit: do you need static?
No, thanks for noting.
Quoted 6 lines
tools/testing/selftests/bpf/bench.c static void parse_cmdline_args(int argc, char **argv) · line 372
Quoted 6 lines
tools/testing/selftests/bpf/bench.c +2
-1+ +/* Parse args for the first time to get bench name */ if (argp_parse (&argp, argc, argv,0 ,NULL ,NULL ))exit (1 ); -if (!env.list && !env.bench_name) {
Also, I will switch to a simpler mode here: just find the bench_name, then construct correct struct argp, then call argp_parse() once.
Quoted 20 lines
Quoted 20 lines
tools/testing/selftests/bpf/bench.c +17
-0+ +if (env.list) +return ; + +if (!env.bench_name) {argp_help (&argp, stderr,ARGP_HELP_DOC ,"bench" );exit (1 ); } + +/* Now check if there are custom options available. If not, then +* everything is done, if yes, then we need to patch bench_parsers +* so that bench_parsers[0] points to the right 'struct argp', and +* bench_parsers[1] terminates the list. +*/ + bench_argp =bench_name_to_argp (env.bench_name); +if (bench_argp) { + bench_parsers[0 ].argp = bench_argp; + bench_parsers[0 ].header = env.bench_name; +memset (&bench_parsers[1 ],0 ,sizeof (bench_parsers[1 ])); +
Quoted 8 lines
tools/testing/selftests/bpf/bench.c static void parse_cmdline_args(int argc, char **argv) · line 457
Quoted 4 lines
tools/testing/selftests/bpf/bench.c +4
-0+ pos_args =0 ; +if (argp_parse (&argp, argc, argv,0 ,NULL ,NULL )) +exit (1 ); + }this also feels like a big hack, why can't you just construct a single-item array based on child parser, instead of overwriting global array?
Sure, thanks.
Quoted 5 lines
Quoted 3 lines
tools/testing/selftests/bpf/bench.c +0
-0}static void collect_measurements (long delta_ns);[...]
PATCH 4/6 selftest/bpf/benchs: make quiet option common
In reply to Anton ProtopopovThe "local-storage-tasks-trace" benchmark has a --quiet option. Move it to the list of common options, so that the main code and other benchmarks can use (now global) env.quiet as well.
--- tools/testing/selftests/bpf/bench.c | 15 +++++++++++++++ tools/testing/selftests/bpf/bench.h | 1 + .../benchs/bench_local_storage_rcu_tasks_trace.c | 14 +------------- 3 files changed, 17 insertions(+), 13 deletions(-)
tools/testing/selftests/bpf/bench.c +15 -0
@@ -16,6 +16,7 @@ struct env env = { .warmup_sec = 1, .duration_sec = 5, .affinity = false, + .quiet = false, .consumer_cnt = 1, .producer_cnt = 1, };
@@ -257,6 +258,7 @@ static const struct argp_option opts[] = { { "consumers", 'c', "NUM", 0, "Number of consumer threads"}, { "verbose", 'v', NULL, 0, "Verbose debug output"}, { "affinity", 'a', NULL, 0, "Set consumer/producer thread affinity"}, + { "quiet", 'q', "{0,1}", OPTION_ARG_OPTIONAL, "If true, be quiet"}, { "prod-affinity", ARG_PROD_AFFINITY_SET, "CPUSET", 0, "Set of CPUs for producer threads; implies --affinity"}, { "cons-affinity", ARG_CONS_AFFINITY_SET, "CPUSET", 0,
@@ -286,6 +288,7 @@ static int pos_args;static error_t parse_arg (int key,char *arg,struct argp_state *state) { +long ret;switch (key) {case 'v' :
@@ -325,6 +328,18 @@ static error_t parse_arg(int key, char *arg, struct argp_state *state)case 'a' : env.affinity = true;break ; +case 'q' : +if (!arg) { + env.quiet = true; + }else { + ret =strtol (arg,NULL ,10 ); +if (ret <0 || ret >1 ) { +fprintf (stderr,"invalid quiet %ld\n" , ret); +argp_usage (state); + } + env.quiet = ret; + } +break ;case ARG_PROD_AFFINITY_SET : env.affinity = true; if (parse_num_list(arg, &env.prod_cpus.cpus,
tools/testing/selftests/bpf/bench.h +1 -0
@@ -24,6 +24,7 @@ struct env {bool verbose;bool list;bool affinity; +bool quiet;int consumer_cnt;int producer_cnt;struct cpu_set prod_cpus;
tools/testing/selftests/bpf/benchs/bench_local_storage_rcu_tasks_trace.c +1 -13
@@ -12,11 +12,9 @@static struct {__u32 nr_procs;__u32 kthread_pid; -bool quiet; } args = { .nr_procs =1000 , .kthread_pid =0 , - .quiet = false, };static const struct argp_option opts[] = {
@@ -24,8 +22,6 @@ static const struct argp_option opts[] = { "Set number of user processes to spin up"}, {"kthread_pid" ,ARG_KTHREAD_PID ,"PID" ,0 , "Pid of rcu_tasks_trace kthread for ticks tracking"}, - { "quiet", ARG_QUIET, "{0,1}", 0, - "If true, don't report progress"}, {}, };
@@ -50,14 +46,6 @@ static error_t parse_arg(int key, char *arg, struct argp_state *state) } args.kthread_pid = ret;break ; -case ARG_QUIET : - ret =strtol (arg,NULL ,10 ); -if (ret <0 || ret >1 ) { -fprintf (stderr,"invalid quiet %ld\n" , ret); -argp_usage (state); - } - args.quiet = ret; -break ;break ;default :return ARGP_ERR_UNKNOWN ;
@@ -224,7 +212,7 @@ static void report_progress(int iter, struct bench_res *res, long delta_ns)exit (1 ); } -if (args.quiet) +if (env.quiet)return ; printf("Iter %d\t avg tasks_trace grace period latency\t%lf ns\n",
Signature · 1 line
2.34.1
Re: [PATCH bpf-next 4/6] selftest/bpf/benchs: make quiet option common
Quoted 25 lines · Anton Protopopov
The "local-storage-tasks-trace" benchmark has a
--quietoption. Move it to the list of common options, so that the main code and other benchmarks can use (now global) env.quiet as well.Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/bench.c | 15 +++++++++++++++ tools/testing/selftests/bpf/bench.h | 1 + .../benchs/bench_local_storage_rcu_tasks_trace.c | 14 +------------- 3 files changed, 17 insertions(+), 13 deletions(-)tools/testing/selftests/bpf/bench.c +1
-0@@ -16,6 +16,7 @@ struct env env = { .warmup_sec = 1, .duration_sec = 5, .affinity = false, + .quiet = false, .consumer_cnt = 1, .producer_cnt = 1, };
tools/testing/selftests/bpf/bench.c static const struct argp_option opts[] = { · line 261
Quoted 4 lines
tools/testing/selftests/bpf/bench.c +1
-0@@ -257,6 +258,7 @@ static const struct argp_option opts[] = { { "consumers", 'c', "NUM", 0, "Number of consumer threads"}, { "verbose", 'v', NULL, 0, "Verbose debug output"}, { "affinity", 'a', NULL, 0, "Set consumer/producer thread affinity"}, + { "quiet", 'q', "{0,1}", OPTION_ARG_OPTIONAL, "If true, be quiet"},
given the default is not quiet, why add 0 or 1? -q for quiet, no "-q" for not quiet? Keeping it simple?
Quoted 3 lines
tools/testing/selftests/bpf/bench.c +0
-0{"prod-affinity" ,ARG_PROD_AFFINITY_SET ,"CPUSET" ,0 , "Set of CPUs for producer threads; implies --affinity"}, { "cons-affinity", ARG_CONS_AFFINITY_SET, "CPUSET", 0,
[...]
Re: [PATCH bpf-next 4/6] selftest/bpf/benchs: make quiet option common
Quoted 25 lines · Andrii Nakryiko
Quoted 24 lines · Anton Protopopov
The "local-storage-tasks-trace" benchmark has a
--quietoption. Move it to the list of common options, so that the main code and other benchmarks can use (now global) env.quiet as well.Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/bench.c | 15 +++++++++++++++ tools/testing/selftests/bpf/bench.h | 1 + .../benchs/bench_local_storage_rcu_tasks_trace.c | 14 +------------- 3 files changed, 17 insertions(+), 13 deletions(-)tools/testing/selftests/bpf/bench.c +1
-0@@ -16,6 +16,7 @@ struct env env = { .warmup_sec = 1, .duration_sec = 5, .affinity = false, + .quiet = false, .consumer_cnt = 1, .producer_cnt = 1, };
Quoted 8 lines
tools/testing/selftests/bpf/bench.c static const struct argp_option opts[] = { · line 261
Quoted 5 lines
tools/testing/selftests/bpf/bench.c +1
-0@@ -257,6 +258,7 @@ static const struct argp_option opts[] = { { "consumers", 'c', "NUM", 0, "Number of consumer threads"}, { "verbose", 'v', NULL, 0, "Verbose debug output"}, { "affinity", 'a', NULL, 0, "Set consumer/producer thread affinity"}, + { "quiet", 'q', "{0,1}", OPTION_ARG_OPTIONAL, "If true, be quiet"},given the default is not quiet, why add 0 or 1? -q for quiet, no "-q" for not quiet? Keeping it simple?
The local-storage-tasks-trace benchmark expected 0 or 1 there, so I didn't want to break any script which utilize this option.
The new parser accepts the old --quiet=0|1 for consistency, but also -q|--quiet without value, as you've suggested (I pass OPTION_ARG_OPTIONAL and set quiet=true if arg is NULL in the new parser).
Quoted 5 lines
Quoted 3 lines
tools/testing/selftests/bpf/bench.c +0
-0{"prod-affinity" ,ARG_PROD_AFFINITY_SET ,"CPUSET" ,0 , "Set of CPUs for producer threads; implies --affinity"}, { "cons-affinity", ARG_CONS_AFFINITY_SET, "CPUSET", 0,[...]
Re: [PATCH bpf-next 4/6] selftest/bpf/benchs: make quiet option common
Quoted 36 lines · Anton Protopopov
Quoted 25 lines · Andrii Nakryiko
Quoted 24 lines · Anton Protopopov
The "local-storage-tasks-trace" benchmark has a
--quietoption. Move it to the list of common options, so that the main code and other benchmarks can use (now global) env.quiet as well.Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/bench.c | 15 +++++++++++++++ tools/testing/selftests/bpf/bench.h | 1 + .../benchs/bench_local_storage_rcu_tasks_trace.c | 14 +------------- 3 files changed, 17 insertions(+), 13 deletions(-)tools/testing/selftests/bpf/bench.c +1
-0@@ -16,6 +16,7 @@ struct env env = { .warmup_sec = 1, .duration_sec = 5, .affinity = false, + .quiet = false, .consumer_cnt = 1, .producer_cnt = 1, };Quoted 8 lines
tools/testing/selftests/bpf/bench.c static const struct argp_option opts[] = { · line 261
Quoted 5 lines
tools/testing/selftests/bpf/bench.c +1
-0@@ -257,6 +258,7 @@ static const struct argp_option opts[] = { { "consumers", 'c', "NUM", 0, "Number of consumer threads"}, { "verbose", 'v', NULL, 0, "Verbose debug output"}, { "affinity", 'a', NULL, 0, "Set consumer/producer thread affinity"}, + { "quiet", 'q', "{0,1}", OPTION_ARG_OPTIONAL, "If true, be quiet"},given the default is not quiet, why add 0 or 1? -q for quiet, no "-q" for not quiet? Keeping it simple?
Quoted 7 lines
The local-storage-tasks-trace benchmark expected 0 or 1 there, so I didn't want to break any script which utilize this option.
The new parser accepts the old --quiet=0|1 for consistency, but also -q|--quiet without value, as you've suggested (I pass
OPTION_ARG_OPTIONALand set quiet=true if arg is NULL in the new parser).
I think it was mostly due to copy/pasting some other integer-based argument handling. We don't need that for boolean flags. Let's just fix benchs/run_bench_local_storage_rcu_tasks_trace.sh to do -q and keep it simple?
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines
tools/testing/selftests/bpf/bench.c +0
-0{"prod-affinity" ,ARG_PROD_AFFINITY_SET ,"CPUSET" ,0 , "Set of CPUs for producer threads; implies --affinity"}, { "cons-affinity", ARG_CONS_AFFINITY_SET, "CPUSET", 0,[...]
Re: [PATCH bpf-next 4/6] selftest/bpf/benchs: make quiet option common
In reply to Anton ProtopopovQuoted 35 lines · Anton Protopopov
Quoted 25 lines · Andrii Nakryiko
Quoted 24 lines · Anton Protopopov
The "local-storage-tasks-trace" benchmark has a
--quietoption. Move it to the list of common options, so that the main code and other benchmarks can use (now global) env.quiet as well.Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/bench.c | 15 +++++++++++++++ tools/testing/selftests/bpf/bench.h | 1 + .../benchs/bench_local_storage_rcu_tasks_trace.c | 14 +------------- 3 files changed, 17 insertions(+), 13 deletions(-)tools/testing/selftests/bpf/bench.c +1
-0@@ -16,6 +16,7 @@ struct env env = { .warmup_sec = 1, .duration_sec = 5, .affinity = false, + .quiet = false, .consumer_cnt = 1, .producer_cnt = 1, };Quoted 8 lines
tools/testing/selftests/bpf/bench.c static const struct argp_option opts[] = { · line 261
Quoted 5 lines
tools/testing/selftests/bpf/bench.c +1
-0@@ -257,6 +258,7 @@ static const struct argp_option opts[] = { { "consumers", 'c', "NUM", 0, "Number of consumer threads"}, { "verbose", 'v', NULL, 0, "Verbose debug output"}, { "affinity", 'a', NULL, 0, "Set consumer/producer thread affinity"}, + { "quiet", 'q', "{0,1}", OPTION_ARG_OPTIONAL, "If true, be quiet"},given the default is not quiet, why add 0 or 1? -q for quiet, no "-q" for not quiet? Keeping it simple?
Quoted 6 lines
The local-storage-tasks-trace benchmark expected 0 or 1 there, so I didn't want to break any script which utilize this option.
The new parser accepts the old --quiet=0|1 for consistency, but also -q|--quiet without value, as you've suggested (I pass
OPTION_ARG_OPTIONALand set quiet=true if arg is NULL in the new parser).
Sure will do, for me --quiet=1 looks weird as well.
Quoted 5 lines
Quoted 5 lines
Quoted 3 lines
tools/testing/selftests/bpf/bench.c +0
-0{"prod-affinity" ,ARG_PROD_AFFINITY_SET ,"CPUSET" ,0 , "Set of CPUs for producer threads; implies --affinity"}, { "cons-affinity", ARG_CONS_AFFINITY_SET, "CPUSET", 0,[...]
PATCH 5/6 selftest/bpf/benchs: print less if the quiet option is set
In reply to Anton ProtopopovThe bench utility will print
Setting up benchmark '<bench-name>'...
Benchmark '<bench-name>' started.
on startup to stdout. Suppress this output if --quiet option if given. This makes it simpler to parse benchmark output by a script.
--- tools/testing/selftests/bpf/bench.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/bench.c +4 -2
@@ -648,7 +648,8 @@ static void setup_benchmark()exit (1 ); } -printf ("Setting up benchmark '%s'...\n" , bench->name); +if (!env.quiet) +printf ("Setting up benchmark '%s'...\n" , bench->name); state.producers =calloc (env.producer_cnt,sizeof (*state.producers)); state.consumers =calloc (env.consumer_cnt,sizeof (*state.consumers));
@@ -694,7 +695,8 @@ static void setup_benchmark() next_cpu(&env.prod_cpus)); } -printf ("Benchmark '%s' started.\n" , bench->name); +if (!env.quiet) +printf ("Benchmark '%s' started.\n" , bench->name); }static pthread_mutex_t bench_done_mtx =PTHREAD_MUTEX_INITIALIZER ;
Signature · 1 line
2.34.1
PATCH 6/6 selftest/bpf/benchs: Add benchmark for hashmap lookups
In reply to Anton ProtopopovAdd a new benchmark which measures hashmap lookup operations speed. A user can control the following parameters of the benchmark:
* key_size (max 1024): the key size to use
* max_entries: the hashmap max entries
* nr_entries: the number of entries to insert/lookup
* nr_loops: the number of loops for the benchmark
* map_flags The hashmap flags passed to BPF_MAP_CREATE
The BPF program performing the benchmarks calls two nested bpf_loop:
bpf_loop(nr_loops/nr_entries)
bpf_loop(nr_entries)
bpf_map_lookup()
So the nr_loops determines the number of actual map lookups. All lookups are successful.
Example (the output is generated on a AMD Ryzen 9 3950X machine):
for nr_entries in `seq 4096 4096 65536`; do echo -n "$((nr_entries*100/65536))% full: "; sudo ./bench -d2 -a bpf-hashmap-lookup --key_size=4 --nr_entries=$nr_entries --max_entries=65536 --nr_loops=1000000 --map_flags=0x40 | grep cpu; done
6% full: cpu01: lookup 50.739M ± 0.018M events/sec (approximated from 32 samples of ~19ms)
12% full: cpu01: lookup 47.751M ± 0.015M events/sec (approximated from 32 samples of ~20ms)
18% full: cpu01: lookup 45.153M ± 0.013M events/sec (approximated from 32 samples of ~22ms)
25% full: cpu01: lookup 43.826M ± 0.014M events/sec (approximated from 32 samples of ~22ms)
31% full: cpu01: lookup 41.971M ± 0.012M events/sec (approximated from 32 samples of ~23ms)
37% full: cpu01: lookup 41.034M ± 0.015M events/sec (approximated from 32 samples of ~24ms)
43% full: cpu01: lookup 39.946M ± 0.012M events/sec (approximated from 32 samples of ~25ms)
50% full: cpu01: lookup 38.256M ± 0.014M events/sec (approximated from 32 samples of ~26ms)
56% full: cpu01: lookup 36.580M ± 0.018M events/sec (approximated from 32 samples of ~27ms)
62% full: cpu01: lookup 36.252M ± 0.012M events/sec (approximated from 32 samples of ~27ms)
68% full: cpu01: lookup 35.200M ± 0.012M events/sec (approximated from 32 samples of ~28ms)
75% full: cpu01: lookup 34.061M ± 0.009M events/sec (approximated from 32 samples of ~29ms)
81% full: cpu01: lookup 34.374M ± 0.010M events/sec (approximated from 32 samples of ~29ms)
87% full: cpu01: lookup 33.244M ± 0.011M events/sec (approximated from 32 samples of ~30ms)
93% full: cpu01: lookup 32.182M ± 0.013M events/sec (approximated from 32 samples of ~31ms)
100% full: cpu01: lookup 31.497M ± 0.016M events/sec (approximated from 32 samples of ~31ms)--- tools/testing/selftests/bpf/Makefile | 5 +- tools/testing/selftests/bpf/bench.c | 7 + tools/testing/selftests/bpf/bench.h | 3 + .../bpf/benchs/bench_bpf_hashmap_lookup.c | 277 ++++++++++++++++++ .../selftests/bpf/progs/bpf_hashmap_lookup.c | 61 ++++ 5 files changed, 352 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c
tools/testing/selftests/bpf/Makefile +4 -1
@@ -604,6 +604,7 @@ $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h $(OUTPUT)/bench_bpf_hashmap_full_update.o: $(OUTPUT)/bpf_hashmap_full_update_bench.skel.h $(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench.skel.h $(OUTPUT)/bench_local_storage_rcu_tasks_trace.o: $(OUTPUT)/local_storage_rcu_tasks_trace_bench.skel.h +$(OUTPUT)/bench_bpf_hashmap_lookup.o: $(OUTPUT)/bpf_hashmap_lookup.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -618,7 +619,9 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_strncmp.o \ $(OUTPUT)/bench_bpf_hashmap_full_update.o \ $(OUTPUT)/bench_local_storage.o \ - $(OUTPUT)/bench_local_storage_rcu_tasks_trace.o + $(OUTPUT)/bench_local_storage_rcu_tasks_trace.o \ + $(OUTPUT)/bench_bpf_hashmap_lookup.o \ + # $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +7 -0
@@ -272,6 +272,7 @@ extern struct argp bench_bpf_loop_argp;extern struct argp bench_local_storage_argp;extern struct argp bench_local_storage_rcu_tasks_trace_argp;extern struct argp bench_strncmp_argp; +extern struct argp bench_hashmap_lookup_argp;static struct argp_child bench_parsers[] = { { &bench_ringbufs_argp,0 ,"Ring buffers benchmark" ,0 },
@@ -281,6 +282,7 @@ static struct argp_child bench_parsers[] = { { &bench_strncmp_argp, 0, "bpf_strncmp helper benchmark", 0 }, { &bench_local_storage_rcu_tasks_trace_argp, 0, "local_storage RCU Tasks Trace slowdown benchmark", 0 }, + { &bench_hashmap_lookup_argp, 0, "Hashmap lookup benchmark", 0 }, {}, };
@@ -403,6 +405,9 @@ struct argp *bench_name_to_argp(const char *bench_name)if (_SCMP ("bpf-loop" ))return &bench_bpf_loop_argp; +if (_SCMP ("bpf-hashmap-lookup" )) +return &bench_hashmap_lookup_argp; +/* no extra arguments */ if (_SCMP("count-global") || _SCMP("count-local") ||
@@ -587,6 +592,7 @@ extern const struct bench bench_local_storage_cache_seq_get;extern const struct bench bench_local_storage_cache_interleaved_get;extern const struct bench bench_local_storage_cache_hashmap_control;extern const struct bench bench_local_storage_tasks_trace; +extern const struct bench bench_bpf_hashmap_lookup;static const struct bench *benchs[] = { &bench_count_global,
@@ -626,6 +632,7 @@ static const struct bench *benchs[] = { &bench_local_storage_cache_interleaved_get, &bench_local_storage_cache_hashmap_control, &bench_local_storage_tasks_trace, + &bench_bpf_hashmap_lookup, };static void setup_benchmark ()
tools/testing/selftests/bpf/bench.h +3 -0
@@ -121,4 +121,7 @@ enum {ARG_NR_PROCS ,ARG_KTHREAD_PID ,ARG_QUIET , +ARG_KEY_SIZE , +ARG_MAP_FLAGS , + ARG_MAX_ENTRIES, };
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +277 -0
277 lines not on this page · raw message
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +61 -0
61 lines not on this page · raw message
Signature · 1 line
2.34.1
Re: [PATCH bpf-next 6/6] selftest/bpf/benchs: Add benchmark for hashmap lookups
Quoted 50 lines · Anton Protopopov
Add a new benchmark which measures hashmap lookup operations speed. A user can control the following parameters of the benchmark:
*
key_size(max 1024): the key size to use
*max_entries: the hashmap max entries
*nr_entries: the number of entries to insert/lookup
*nr_loops: the number of loops for the benchmark
*map_flagsThe hashmap flags passed toBPF_MAP_CREATEThe BPF program performing the benchmarks calls two nested
bpf_loop:
bpf_loop(nr_loops/nr_entries)
bpf_loop(nr_entries)
bpf_map_lookup()So the
nr_loopsdetermines the number of actual map lookups. All lookups are successful.Example (the output is generated on a AMD Ryzen 9 3950X machine):
for nr_entries in `seq 4096 4096 65536`; do echo -n "$((nr_entries*100/65536))% full: "; sudo ./bench -d2 -a bpf-hashmap-lookup --key_size=4 --nr_entries=$nr_entries --max_entries=65536 --nr_loops=1000000 --map_flags=0x40 | grep cpu; done 6% full: cpu01: lookup 50.739M ± 0.018M events/sec (approximated from 32 samples of ~19ms) 12% full: cpu01: lookup 47.751M ± 0.015M events/sec (approximated from 32 samples of ~20ms) 18% full: cpu01: lookup 45.153M ± 0.013M events/sec (approximated from 32 samples of ~22ms) 25% full: cpu01: lookup 43.826M ± 0.014M events/sec (approximated from 32 samples of ~22ms) 31% full: cpu01: lookup 41.971M ± 0.012M events/sec (approximated from 32 samples of ~23ms) 37% full: cpu01: lookup 41.034M ± 0.015M events/sec (approximated from 32 samples of ~24ms) 43% full: cpu01: lookup 39.946M ± 0.012M events/sec (approximated from 32 samples of ~25ms) 50% full: cpu01: lookup 38.256M ± 0.014M events/sec (approximated from 32 samples of ~26ms) 56% full: cpu01: lookup 36.580M ± 0.018M events/sec (approximated from 32 samples of ~27ms) 62% full: cpu01: lookup 36.252M ± 0.012M events/sec (approximated from 32 samples of ~27ms) 68% full: cpu01: lookup 35.200M ± 0.012M events/sec (approximated from 32 samples of ~28ms) 75% full: cpu01: lookup 34.061M ± 0.009M events/sec (approximated from 32 samples of ~29ms) 81% full: cpu01: lookup 34.374M ± 0.010M events/sec (approximated from 32 samples of ~29ms) 87% full: cpu01: lookup 33.244M ± 0.011M events/sec (approximated from 32 samples of ~30ms) 93% full: cpu01: lookup 32.182M ± 0.013M events/sec (approximated from 32 samples of ~31ms) 100% full: cpu01: lookup 31.497M ± 0.016M events/sec (approximated from 32 samples of ~31ms)Signed-off-by Anton Protopopov <[email protected]>--- tools/testing/selftests/bpf/Makefile | 5 +- tools/testing/selftests/bpf/bench.c | 7 + tools/testing/selftests/bpf/bench.h | 3 + .../bpf/benchs/bench_bpf_hashmap_lookup.c | 277 ++++++++++++++++++ .../selftests/bpf/progs/bpf_hashmap_lookup.c | 61 ++++ 5 files changed, 352 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c
[...]
Quoted 8 lines
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +8
-0+static error_t parse_arg (int key,char *arg,struct argp_state *state) +{ +long ret; + +switch (key) { +case ARG_KEY_SIZE : + ret =strtol (arg,NULL ,10 ); +if (ret <1 || ret >MAX_KEY_SIZE ) {
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c line 65
Quoted 10 lines
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +10
-0+fprintf (stderr,"invalid key_size" ); +argp_usage (state); + } + args.key_size = ret; +break ; +case ARG_MAP_FLAGS : +if (!strncasecmp (arg,"0x" ,2 )) + ret =strtol (arg,NULL ,0x10 ); +else + ret =strtol (arg,NULL ,10 );
if you pass base as zero, strtol() will do this for you
Quoted 6 lines
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +6
-0+if (ret <0 || ret >UINT_MAX ) { +fprintf (stderr,"invalid map_flags" ); +argp_usage (state); + } + args.map_flags = ret; +break ;
[...]
Re: [PATCH bpf-next 6/6] selftest/bpf/benchs: Add benchmark for hashmap lookups
Quoted 19 lines · Andrii Nakryiko
Quoted 1 line · Anton Protopopov
[...]
Quoted 5 lines
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +5
-0+ +switch (key) { +case ARG_KEY_SIZE : + ret =strtol (arg,NULL ,10 ); +if (ret <1 || ret >MAX_KEY_SIZE ) {tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c line 65
Quoted 10 lines
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +10
-0+fprintf (stderr,"invalid key_size" ); +argp_usage (state); + } + args.key_size = ret; +break ; +case ARG_MAP_FLAGS : +if (!strncasecmp (arg,"0x" ,2 )) + ret =strtol (arg,NULL ,0x10 ); +else + ret =strtol (arg,NULL ,10 );
Quoted 1 line
if you pass base as zero,
strtol()will do this for you
Thanks, I didn't remeber this!
Quoted 8 lines
Quoted 6 lines
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c new file +6
-0+if (ret <0 || ret >UINT_MAX ) { +fprintf (stderr,"invalid map_flags" ); +argp_usage (state); + } + args.map_flags = ret; +break ;[...]
Martin KaFai Lau
reviewerRe: [PATCH bpf-next 6/6] selftest/bpf/benchs: Add benchmark for hashmap lookups
In reply to Anton ProtopopovQuoted 30 lines · Anton Protopopov
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +30
-0+/* The number of slots to store times */ +#define NR_SLOTS 32 + +/* Configured by userspace */ +u64 nr_entries; +u64 nr_loops; +u32 __attribute__((__aligned__ (8 ))) key[256 ]; + +/* Filled by us */ +u64 __attribute__((__aligned__(256))) percpu_times_index[NR_SLOTS]; > +u64 __attribute__((__aligned__(256))) percpu_times[256][NR_SLOTS]; + +static inline void patch_key (u32 i) +{ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + key[0 ] = i +1 ; +#else + key[0 ] =__builtin_bswap32 (i +1 ); +#endif +/* the rest of key is random and is configured by userspace */ +} + +static int lookup_callback (__u32 index,u32 *unused) +{ +patch_key (index); +return bpf_map_lookup_elem (&hash_map_bench, key) ?0 :1 ; +} + +static int loop_lookup_callback (__u32 index,u32 *unused) +{ +return bpf_loop (nr_entries, lookup_callback,NULL ,0 ) ?0 :1 ;
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c line 55
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +10
-0+} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx) +{ +u32 cpu =bpf_get_smp_processor_id (); +u32 times_index; +u64 start_time; + + times_index = percpu_times_index[cpu &255 ] %NR_SLOTS ;
percpu_times_index only has NR_SLOTS (32) elements?
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+ start_time =bpf_ktime_get_ns (); +bpf_loop (nr_loops, loop_lookup_callback,NULL ,0 ); + percpu_times[cpu &255 ][times_index] =bpf_ktime_get_ns () - start_time; + percpu_times_index[cpu &255 ] +=1 ; +return 0 ; +}
Re: [PATCH bpf-next 6/6] selftest/bpf/benchs: Add benchmark for hashmap lookups
Quoted 35 lines · Martin KaFai Lau
Quoted 34 lines · Anton Protopopov
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +34
-0+/* The number of slots to store times */ +#define NR_SLOTS 32 + +/* Configured by userspace */ +u64 nr_entries; +u64 nr_loops; +u32 __attribute__((__aligned__ (8 ))) key[256 ]; + +/* Filled by us */ +u64 __attribute__((__aligned__(256))) percpu_times_index[NR_SLOTS]; > +u64 __attribute__((__aligned__(256))) percpu_times[256][NR_SLOTS]; + +static inline void patch_key (u32 i) +{ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + key[0 ] = i +1 ; +#else + key[0 ] =__builtin_bswap32 (i +1 ); +#endif +/* the rest of key is random and is configured by userspace */ +} + +static int lookup_callback (__u32 index,u32 *unused) +{ +patch_key (index); +return bpf_map_lookup_elem (&hash_map_bench, key) ?0 :1 ; +} + +static int loop_lookup_callback (__u32 index,u32 *unused) +{ +return bpf_loop (nr_entries, lookup_callback,NULL ,0 ) ?0 :1 ; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx)
Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c line 55
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+{ +u32 cpu =bpf_get_smp_processor_id (); +u32 times_index; +u64 start_time; + + times_index = percpu_times_index[cpu &255 ] %NR_SLOTS ;
percpu_times_indexonly hasNR_SLOTS(32) elements?
Yes, the idea was the following. One measurement (bpf prog execution) takes about 20-80 ms (depending on the key/map size). So in 2-3 seconds we can get about NR_SLOTS elements. For me 32 looked like enough to get stats for this benchmark. Do you think this is better to make the NR_SLOTS bigger/configurable?
Quoted 7 lines
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+ start_time =bpf_ktime_get_ns (); +bpf_loop (nr_loops, loop_lookup_callback,NULL ,0 ); + percpu_times[cpu &255 ][times_index] =bpf_ktime_get_ns () - start_time; + percpu_times_index[cpu &255 ] +=1 ; +return 0 ; +}
Martin KaFai Lau
reviewerRe: [PATCH bpf-next 6/6] selftest/bpf/benchs: Add benchmark for hashmap lookups
Quoted 45 lines · Anton Protopopov
Quoted 35 lines · Martin KaFai Lau
Quoted 34 lines · Anton Protopopov
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +34
-0+/* The number of slots to store times */ +#define NR_SLOTS 32 + +/* Configured by userspace */ +u64 nr_entries; +u64 nr_loops; +u32 __attribute__((__aligned__ (8 ))) key[256 ]; + +/* Filled by us */ +u64 __attribute__((__aligned__(256))) percpu_times_index[NR_SLOTS]; > +u64 __attribute__((__aligned__(256))) percpu_times[256][NR_SLOTS]; + +static inline void patch_key (u32 i) +{ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + key[0 ] = i +1 ; +#else + key[0 ] =__builtin_bswap32 (i +1 ); +#endif +/* the rest of key is random and is configured by userspace */ +} + +static int lookup_callback (__u32 index,u32 *unused) +{ +patch_key (index); +return bpf_map_lookup_elem (&hash_map_bench, key) ?0 :1 ; +} + +static int loop_lookup_callback (__u32 index,u32 *unused) +{ +return bpf_loop (nr_entries, lookup_callback,NULL ,0 ) ?0 :1 ; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx)Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c line 55
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+{ +u32 cpu =bpf_get_smp_processor_id (); +u32 times_index; +u64 start_time; + + times_index = percpu_times_index[cpu &255 ] %NR_SLOTS ;
percpu_times_indexonly hasNR_SLOTS(32) elements?
Quoted 5 lines
Yes, the idea was the following. One measurement (bpf prog execution) takes about 20-80 ms (depending on the key/map size). So in 2-3 seconds we can get about
NR_SLOTSelements. For me 32 looked like enough to get stats for this benchmark. Do you think this is better to make theNR_SLOTSbigger/configurable?
I thought percpu_times_index[] is the next slot to use for a particular cpu in percpu_times[256][NR_SLOTS]. 256 is the max number of cpu supported? It is doing "cpu" & 255 also. Should it be sized as percpu_times_index[256] instead then?
May be #define what 256 is here such that it can have a self describe name.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+ start_time =bpf_ktime_get_ns (); +bpf_loop (nr_loops, loop_lookup_callback,NULL ,0 ); + percpu_times[cpu &255 ][times_index] =bpf_ktime_get_ns () - start_time; + percpu_times_index[cpu &255 ] +=1 ; +return 0 ; +}
Re: [PATCH bpf-next 6/6] selftest/bpf/benchs: Add benchmark for hashmap lookups
Quoted 52 lines · Martin KaFai Lau
Quoted 45 lines · Anton Protopopov
Quoted 35 lines · Martin KaFai Lau
Quoted 34 lines · Anton Protopopov
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +34
-0+/* The number of slots to store times */ +#define NR_SLOTS 32 + +/* Configured by userspace */ +u64 nr_entries; +u64 nr_loops; +u32 __attribute__((__aligned__ (8 ))) key[256 ]; + +/* Filled by us */ +u64 __attribute__((__aligned__(256))) percpu_times_index[NR_SLOTS]; > +u64 __attribute__((__aligned__(256))) percpu_times[256][NR_SLOTS]; + +static inline void patch_key (u32 i) +{ +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + key[0 ] = i +1 ; +#else + key[0 ] =__builtin_bswap32 (i +1 ); +#endif +/* the rest of key is random and is configured by userspace */ +} + +static int lookup_callback (__u32 index,u32 *unused) +{ +patch_key (index); +return bpf_map_lookup_elem (&hash_map_bench, key) ?0 :1 ; +} + +static int loop_lookup_callback (__u32 index,u32 *unused) +{ +return bpf_loop (nr_entries, lookup_callback,NULL ,0 ) ?0 :1 ; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx)Quoted 8 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c line 55
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+{ +u32 cpu =bpf_get_smp_processor_id (); +u32 times_index; +u64 start_time; + + times_index = percpu_times_index[cpu &255 ] %NR_SLOTS ;
percpu_times_indexonly hasNR_SLOTS(32) elements?Quoted 5 lines
Yes, the idea was the following. One measurement (bpf prog execution) takes about 20-80 ms (depending on the key/map size). So in 2-3 seconds we can get about
NR_SLOTSelements. For me 32 looked like enough to get stats for this benchmark. Do you think this is better to make theNR_SLOTSbigger/configurable?
Quoted 6 lines
I thought percpu_times_index[] is the next slot to use for a particular cpu in percpu_times[256][NR_SLOTS]. 256 is the max number of cpu supported? It is doing "cpu" & 255 also. Should it be sized as percpu_times_index[256] instead then?
May be #define what 256 is here such that it can have a self describe name.
Oh, thanks! Of course, percpu_times_index is of wrong size, I will fix this and use names instead of numbers.
Quoted 9 lines
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c new file +6
-0+ start_time =bpf_ktime_get_ns (); +bpf_loop (nr_loops, loop_lookup_callback,NULL ,0 ); + percpu_times[cpu &255 ][times_index] =bpf_ktime_get_ns () - start_time; + percpu_times_index[cpu &255 ] +=1 ; +return 0 ; +}
Quoted 4 lines · Anton Protopopov
Add a new benchmark for hashmap lookups and fix several typos. See individual commits for descriptions.
Quoted 8 lines
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 :)
Quoted 29 lines
Anton Protopopov (6):
selftest/bpf/benchs: fix a typo inbpf_hashmap_full_updateselftest/bpf/benchs: make a function static inbpf_hashmap_full_updateselftest/bpf/benchs: enhance argp parsing selftest/bpf/benchs: make quiet option common selftest/bpf/benchs: print less if the quiet option is set selftest/bpf/benchs: Add benchmark for hashmap lookupstools/testing/selftests/bpf/Makefile | 5 +- tools/testing/selftests/bpf/bench.c | 126 +++++++- tools/testing/selftests/bpf/bench.h | 24 ++ .../bpf/benchs/bench_bloom_filter_map.c | 6 - .../benchs/bench_bpf_hashmap_full_update.c | 4 +- .../bpf/benchs/bench_bpf_hashmap_lookup.c | 277 ++++++++++++++++++ .../selftests/bpf/benchs/bench_bpf_loop.c | 4 - .../bpf/benchs/bench_local_storage.c | 5 - .../bench_local_storage_rcu_tasks_trace.c | 20 +- .../selftests/bpf/benchs/bench_ringbufs.c | 8 - .../selftests/bpf/benchs/bench_strncmp.c | 4 - .../run_bench_bpf_hashmap_full_update.sh | 2 +- .../selftests/bpf/progs/bpf_hashmap_lookup.c | 61 ++++ 13 files changed, 486 insertions(+), 60 deletions(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_hashmap_lookup.c--
2.34.1
Quoted 8 lines · Andrii Nakryiko
Quoted 7 lines · Anton Protopopov
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.
Quoted 8 lines
Quoted 5 lines
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.
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):
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.8A 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.8Other 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.)
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).
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.
Quoted 16 lines · Anton Protopopov
Quoted 14 lines · Andrii Nakryiko
Quoted 12 lines · Anton Protopopov
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).
Quoted 5 lines
Quoted 2 lines
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.
Quoted 6 lines
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.
Quoted 7 lines
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.8A smaller map (10K, 50% full):
Quoted 8 lines
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.8Other 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.
Quoted 9 lines
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
Quoted 10 lines
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)
{(quoted diff) +2
-0+ if (likely((key_len & 0x3) == 0)) + return jhash2(key, key_len >> 2, hashrnd); return jhash(key, key_len, hashrnd); }
Quoted 3 lines
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!
Quoted 32 lines · Andrii Nakryiko
Quoted 16 lines · Anton Protopopov
Quoted 14 lines · Andrii Nakryiko
Quoted 12 lines · Anton Protopopov
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).Quoted 5 lines
Quoted 2 lines
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.
Quoted 6 lines
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):
Quoted 3 lines
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).
My first attempt was with lib/xxhash.c, and it looked well on the first glance (outperformed every other hash in my hash benchmark). However, when used inside the hashmap, it behaved way worse than expected, so I had to inline it.
Quoted 20 lines
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.
Quoted 7 lines
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.8A smaller map (10K, 50% full):
Quoted 8 lines
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.8Other 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.)
Quoted 6 lines
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.
For keys longer than 240 the scalar xxh3 works way worse than xxhash. BTW, do you know use cases when hashmap keys are > 240? (For cilium/tetragon the most interesting use cases are keys of sizes ~4-40.)
Quoted 23 lines
Quoted 9 lines
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()andSTACK_TRACEmap (and what motivatedbpf_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).
Quoted 1 line
Ok, this makes sense. Based on the fact that for stacktrace xxh3 also works about twice faster (for stack depths of 10 and more), I see no problem just using it as is (corrected by the fact that for key sizes of 240 and more we might prefer xxh64; this shouldn't break the stacktrace algorithms if we use different hash algorithms, right?).
Quoted 10 lines
Quoted 10 lines
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)
{(quoted diff) +2
-0+ if (likely((key_len & 0x3) == 0)) + return jhash2(key, key_len >> 2, hashrnd); return jhash(key, key_len, hashrnd); }
Quoted 6 lines
Quoted 3 lines
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!
Benchmarks for "the better hash" are running already!
Quoted 69 lines · Anton Protopopov
Quoted 32 lines · Andrii Nakryiko
Quoted 16 lines · Anton Protopopov
Quoted 14 lines · Andrii Nakryiko
Quoted 12 lines · Anton Protopopov
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).Quoted 5 lines
Quoted 2 lines
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.
Quoted 6 lines
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):
Quoted 3 lines
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).My first attempt was with
lib/xxhash.c, and it looked well on the first glance (outperformed every other hash in my hash benchmark). However, when used inside the hashmap, it behaved way worse than expected, so I had to inline it.Quoted 20 lines
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.
Quoted 7 lines
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.8A smaller map (10K, 50% full):
Quoted 8 lines
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.8Other 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.)Quoted 6 lines
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.
Quoted 3 lines
For keys longer than 240 the scalar xxh3 works way worse than xxhash. BTW, do you know use cases when hashmap keys are > 240? (For cilium/tetragon the most interesting use cases are keys of sizes ~4-40.)
Can't recall such big keys, but if someone was to use bpf_get_stack() and using stack traces as keys of hashmap, we'd be looking at 1KB+ keys in such case.
When you say "way worse", how much do you think? This is surprising, given official benchmark results. But then, I don't think official benchmark has scalar xxh3 on some of the graphs.
Quoted 24 lines
Quoted 24 lines
Quoted 10 lines
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()andSTACK_TRACEmap (and what motivatedbpf_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).
Quoted 7 lines
Quoted 1 line
Ok, this makes sense. Based on the fact that for stacktrace xxh3 also works about twice faster (for stack depths of 10 and more), I see no problem just using it as is (corrected by the fact that for key sizes of 240 and more we might prefer xxh64; this shouldn't break the stacktrace algorithms if we use different hash algorithms, right?).
Yep, it shouldn't, it's implementation detail. But of course it would be nice to stick to just one hashing algorithm.
Quoted 19 lines
Quoted 11 lines
Quoted 11 lines
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)
{(quoted diff) +2
-0+ if (likely((key_len & 0x3) == 0)) + return jhash2(key, key_len >> 2, hashrnd); return jhash(key, key_len, hashrnd); }Quoted 6 lines
Quoted 3 lines
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!
Benchmarks for "the better hash" are running already!
Quoted 74 lines · Andrii Nakryiko
Quoted 69 lines · Anton Protopopov
Quoted 32 lines · Andrii Nakryiko
Quoted 16 lines · Anton Protopopov
Quoted 14 lines · Andrii Nakryiko
Quoted 12 lines · Anton Protopopov
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).Quoted 5 lines
Quoted 2 lines
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.
Quoted 6 lines
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):
Quoted 3 lines
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).My first attempt was with
lib/xxhash.c, and it looked well on the first glance (outperformed every other hash in my hash benchmark). However, when used inside the hashmap, it behaved way worse than expected, so I had to inline it.Quoted 20 lines
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.
Quoted 7 lines
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.8A smaller map (10K, 50% full):
Quoted 8 lines
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.8Other 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.)Quoted 6 lines
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.
Quoted 3 lines
For keys longer than 240 the scalar xxh3 works way worse than xxhash. BTW, do you know use cases when hashmap keys are > 240? (For cilium/tetragon the most interesting use cases are keys of sizes ~4-40.)
Quoted 7 lines
Can't recall such big keys, but if someone was to use
bpf_get_stack()and using stack traces as keys of hashmap, we'd be looking at 1KB+ keys in such case.When you say "way worse", how much do you think? This is surprising, given official benchmark results. But then, I don't think official benchmark has scalar xxh3 on some of the graphs.
Here are numbers for xxh3 vs xxh64 (hash_size/cycles):
hash_size 16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400
xxh3 17 25 33 33 42 42 47 47 68 73 78 83 88 93 98 184 218 218 218 218 252 252 252 252 286
xxh64 26 41 49 48 57 55 63 62 71 70 79 77 86 85 93 92 107 101 110 107 117 118 135 125 134Note how xxh3 numbers jump at hash_size=240. Probably this is because the scalar xxh3 was never actually benchmarked by the original author? I've asked them about this case, see https://github.com/Cyan4973/xxHash/issues/793
Quoted 52 lines
Quoted 22 lines
Quoted 22 lines
Quoted 8 lines
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()andSTACK_TRACEmap (and what motivatedbpf_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).Quoted 7 lines
Quoted 1 line
Ok, this makes sense. Based on the fact that for stacktrace xxh3 also works about twice faster (for stack depths of 10 and more), I see no problem just using it as is (corrected by the fact that for key sizes of 240 and more we might prefer xxh64; this shouldn't break the stacktrace algorithms if we use different hash algorithms, right?).
Yep, it shouldn't, it's implementation detail. But of course it would be nice to stick to just one hashing algorithm.
Quoted 19 lines
Quoted 11 lines
Quoted 11 lines
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)
{(quoted diff) +2
-0+ if (likely((key_len & 0x3) == 0)) + return jhash2(key, key_len >> 2, hashrnd); return jhash(key, key_len, hashrnd); }Quoted 6 lines
Quoted 3 lines
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!
Benchmarks for "the better hash" are running already!