On 6/8/22 7:02 PM, Martin KaFai Lau wrote:
> On Sat, Jun 04, 2022 at 03:20:06PM -0700, Dave Marchevsky wrote:
>> 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.
> Thanks for working on this. Have some high level comments and questions.
>
>> "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
>> similar to "sequential get", but creates and uses BPF_MAP_TYPE_HASH
>> instead of local storage. Only one inner map is created - a hashmap
>> meant to hold tid -> data mapping for all tasks. Size of the hashmap is
>> hardcoded to my system's PID_MAX_LIMIT (4,194,304). The number of these
>> keys which are actually fetched as part of the benchmark is
>> configurable.
> Note that the key size of the hashmap in the socket use case could make
> a different also. It usually uses the four tuples(src/dst ip6/port).
> Not necessarily something need to be configurable now but would be
> nice thing to do later.
>
IIRC I tried varying the key / val sizes and while there was a difference
it was not nearly as big as varying 'number of keys actually fetched'. Will
confirm.
>>
>> 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):
>>
>> Hashmap Control
>> ===============
>> num keys: 10
>> hashmap (control) sequential get: hits throughput: 33.748 ± 0.700 M ops/s, hits latency: 29.631 ns/op, important_hits throughput: 33.748 ± 0.700 M ops/s
>>
>> num keys: 1000
>> hashmap (control) sequential get: hits throughput: 29.997 ± 0.953 M ops/s, hits latency: 33.337 ns/op, important_hits throughput: 29.997 ± 0.953 M ops/s
>>
>> num keys: 10000
>> hashmap (control) sequential get: hits throughput: 22.828 ± 1.114 M ops/s, hits latency: 43.805 ns/op, important_hits throughput: 22.828 ± 1.114 M ops/s
>>
>> num keys: 100000
>> hashmap (control) sequential get: hits throughput: 17.595 ± 0.225 M ops/s, hits latency: 56.834 ns/op, important_hits throughput: 17.595 ± 0.225 M ops/s
>>
>> num keys: 4194304
>> hashmap (control) sequential get: hits throughput: 7.098 ± 0.757 M ops/s, hits latency: 140.878 ns/op, important_hits throughput: 7.098 ± 0.757 M ops/s
>>
>> Local Storage
>> =============
>> num_maps: 1
>> local_storage cache sequential get: hits throughput: 47.298 ± 0.180 M ops/s, hits latency: 21.142 ns/op, important_hits throughput: 47.298 ± 0.180 M ops/s
>> local_storage cache interleaved get: hits throughput: 55.277 ± 0.888 M ops/s, hits latency: 18.091 ns/op, important_hits throughput: 55.277 ± 0.888 M ops/s
>>
>> num_maps: 10
>> local_storage cache sequential get: hits throughput: 40.240 ± 0.802 M ops/s, hits latency: 24.851 ns/op, important_hits throughput: 4.024 ± 0.080 M ops/s
>> local_storage cache interleaved get: hits throughput: 48.701 ± 0.722 M ops/s, hits latency: 20.533 ns/op, important_hits throughput: 17.393 ± 0.258 M ops/s
> iiuc, important_hits is only useful for the 'interleaved get' test?
>
> and the important_hits is always a certain fraction of the total get.
> For num_maps:10 here, 4 extra for every 10 get,
> so 4/14 ~ 28% of the total get?
>
I think important_hits is meaningful for both sequential and interleaved
benchmarks - but only when seeking to optimize the performance of a particular
map, perhaps at the expense of others, vs all maps in general.
Presumably if the performance of a particular map is more important than others
it's also being used significantly more often, hence interleaved benchmark.
I expect that future work here will improve cliff performance in general, which
will be visible from sequential benchmark, while hopefully also further
improving important_hits in interleaved case where it's 4/14 of all gets.
>>
>> num_maps: 16
>> local_storage cache sequential get: hits throughput: 44.515 ± 0.708 M ops/s, hits latency: 22.464 ns/op, important_hits throughput: 2.782 ± 0.044 M ops/s
>> local_storage cache interleaved get: hits throughput: 49.553 ± 2.260 M ops/s, hits latency: 20.181 ns/op, important_hits throughput: 15.767 ± 0.719 M ops/s
>>
>> num_maps: 17
>> local_storage cache sequential get: hits throughput: 38.778 ± 0.302 M ops/s, hits latency: 25.788 ns/op, important_hits throughput: 2.284 ± 0.018 M ops/s
>> local_storage cache interleaved get: hits throughput: 43.848 ± 1.023 M ops/s, hits latency: 22.806 ns/op, important_hits throughput: 13.349 ± 0.311 M ops/s
>>
>> num_maps: 24
>> local_storage cache sequential get: hits throughput: 19.317 ± 0.568 M ops/s, hits latency: 51.769 ns/op, important_hits throughput: 0.806 ± 0.024 M ops/s
>> local_storage cache interleaved get: hits throughput: 24.397 ± 0.272 M ops/s, hits latency: 40.989 ns/op, important_hits throughput: 6.863 ± 0.077 M ops/s
>>
>> num_maps: 32
>> local_storage cache sequential get: hits throughput: 13.333 ± 0.135 M ops/s, hits latency: 75.000 ns/op, important_hits throughput: 0.417 ± 0.004 M ops/s
>> local_storage cache interleaved get: hits throughput: 16.898 ± 0.383 M ops/s, hits latency: 59.178 ns/op, important_hits throughput: 4.717 ± 0.107 M ops/s
>>
>> num_maps: 100
>> local_storage cache sequential get: hits throughput: 6.360 ± 0.107 M ops/s, hits latency: 157.233 ns/op, important_hits throughput: 0.064 ± 0.001 M ops/s
>> local_storage cache interleaved get: hits throughput: 7.303 ± 0.362 M ops/s, hits latency: 136.930 ns/op, important_hits throughput: 1.907 ± 0.094 M ops/s
>>
>> num_maps: 1000
>> local_storage cache sequential get: hits throughput: 0.452 ± 0.010 M ops/s, hits latency: 2214.022 ns/op, important_hits throughput: 0.000 ± 0.000 M ops/s
>> local_storage cache interleaved get: hits throughput: 0.542 ± 0.007 M ops/s, hits latency: 1843.341 ns/op, important_hits throughput: 0.136 ± 0.002 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.
>>
>> To get a sense of the overhead of the benchmark program, I
>> commented out bpf_task_storage_get/bpf_map_lookup_elem in
>> local_storage_bench.c and ran the benchmark on the same host as the
>> 'real' run. Results:
>> Hashmap Control
>> ===============
>> num keys: 10
>> hashmap (control) sequential get: hits throughput: 54.288 ± 0.655 M ops/s, hits latency: 18.420 ns/op, important_hits throughput: 54.288 ± 0.655 M ops/s
>>
>> num keys: 1000
>> hashmap (control) sequential get: hits throughput: 52.913 ± 0.519 M ops/s, hits latency: 18.899 ns/op, important_hits throughput: 52.913 ± 0.519 M ops/s
>>
>> num keys: 10000
>> hashmap (control) sequential get: hits throughput: 53.480 ± 1.235 M ops/s, hits latency: 18.699 ns/op, important_hits throughput: 53.480 ± 1.235 M ops/s
>>
>> num keys: 100000
>> hashmap (control) sequential get: hits throughput: 54.982 ± 1.902 M ops/s, hits latency: 18.188 ns/op, important_hits throughput: 54.982 ± 1.902 M ops/s
>>
>> num keys: 4194304
>> hashmap (control) sequential get: hits throughput: 50.858 ± 0.707 M ops/s, hits latency: 19.662 ns/op, important_hits throughput: 50.858 ± 0.707 M ops/s
>>
>> Local Storage
>> =============
>> num_maps: 1
>> local_storage cache sequential get: hits throughput: 110.990 ± 4.828 M ops/s, hits latency: 9.010 ns/op, important_hits throughput: 110.990 ± 4.828 M ops/s
>> local_storage cache interleaved get: hits throughput: 161.057 ± 4.090 M ops/s, hits latency: 6.209 ns/op, important_hits throughput: 161.057 ± 4.090 M ops/s
>>
>> num_maps: 10
>> local_storage cache sequential get: hits throughput: 112.930 ± 1.079 M ops/s, hits latency: 8.855 ns/op, important_hits throughput: 11.293 ± 0.108 M ops/s
>> local_storage cache interleaved get: hits throughput: 115.841 ± 2.088 M ops/s, hits latency: 8.633 ns/op, important_hits throughput: 41.372 ± 0.746 M ops/s
>>
>> num_maps: 16
>> local_storage cache sequential get: hits throughput: 115.653 ± 0.416 M ops/s, hits latency: 8.647 ns/op, important_hits throughput: 7.228 ± 0.026 M ops/s
>> local_storage cache interleaved get: hits throughput: 138.717 ± 1.649 M ops/s, hits latency: 7.209 ns/op, important_hits throughput: 44.137 ± 0.525 M ops/s
>>
>> num_maps: 17
>> local_storage cache sequential get: hits throughput: 112.020 ± 1.649 M ops/s, hits latency: 8.927 ns/op, important_hits throughput: 6.598 ± 0.097 M ops/s
>> local_storage cache interleaved get: hits throughput: 128.089 ± 1.960 M ops/s, hits latency: 7.807 ns/op, important_hits throughput: 38.995 ± 0.597 M ops/s
>>
>> num_maps: 24
>> local_storage cache sequential get: hits throughput: 92.447 ± 5.170 M ops/s, hits latency: 10.817 ns/op, important_hits throughput: 3.855 ± 0.216 M ops/s
>> local_storage cache interleaved get: hits throughput: 128.844 ± 2.808 M ops/s, hits latency: 7.761 ns/op, important_hits throughput: 36.245 ± 0.790 M ops/s
>>
>> num_maps: 32
>> local_storage cache sequential get: hits throughput: 102.042 ± 1.462 M ops/s, hits latency: 9.800 ns/op, important_hits throughput: 3.194 ± 0.046 M ops/s
>> local_storage cache interleaved get: hits throughput: 126.577 ± 1.818 M ops/s, hits latency: 7.900 ns/op, important_hits throughput: 35.332 ± 0.507 M ops/s
>>
>> num_maps: 100
>> local_storage cache sequential get: hits throughput: 111.327 ± 1.401 M ops/s, hits latency: 8.983 ns/op, important_hits throughput: 1.113 ± 0.014 M ops/s
>> local_storage cache interleaved get: hits throughput: 131.327 ± 1.339 M ops/s, hits latency: 7.615 ns/op, important_hits throughput: 34.302 ± 0.350 M ops/s
>>
>> num_maps: 1000
>> local_storage cache sequential get: hits throughput: 101.978 ± 0.563 M ops/s, hits latency: 9.806 ns/op, important_hits throughput: 0.102 ± 0.001 M ops/s
>> local_storage cache interleaved get: hits throughput: 141.084 ± 1.098 M ops/s, hits latency: 7.088 ns/op, important_hits throughput: 35.430 ± 0.276 M ops/s
>>
>> Adjusting for overhead, latency numbers for "hashmap control" and
>> "sequential get" are:
>>
>> hashmap_control_1k: ~14.4ns
>> hashmap_control_10k: ~25.1ns
>> hashmap_control_100k: ~38.6ns
>> sequential_get_1: ~12.1ns
>> sequential_get_10: ~16.0ns
>> sequential_get_16: ~13.8ns
>> sequential_get_17: ~16.8ns
>> sequential_get_24: ~40.9ns
>> sequential_get_32: ~65.2ns
>> sequential_get_100: ~148.2ns
>> sequential_get_1000: ~2204ns
>>
>> Clearly demonstrating a cliff.
>>
>> In the discussion for v1 of this patchset, Alexei noted that
>> local_storage was 2.5x faster than a large hashmap [1]. The benchmark
>> results confirm that this is still the case: a long-running BPF
>> application putting some pid-specific info into a hashmap for each pid
>> it sees will probably see on the order of 10-100k pids. Bench numbers
>> for hashmaps of this size are ~2.5x slower than sequential_get_16, but
>> as the number of local_storage maps grows past local_storage cache size
>> performance advantage reverses.
> iiuc, the test on the local_storage get is done on the same task ?
>
Yes, the task of the userspace runner process.
>>
>> When running the benchmarks it may be necessary to bump 'open files'
>> ulimit for a successful run.
>>
>> [0]: https://lore.kernel.org/all/20220420002143.1096548-1-davemarchevsky@xxxxxx
>> [1]: https://lore.kernel.org/bpf/20220511173305.ftldpn23m4ski3d3@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/
>>
>
> [ ... ]
>
>> +static int do_lookup(unsigned int elem, struct loop_ctx *lctx)
>> +{
>> + void *map, *inner_map;
>> + int idx = 0;
>> +
>> + if (use_hashmap)
>> + map = &array_of_hash_maps;
>> + else
>> + map = &array_of_local_storage_maps;
>> +
>> + inner_map = bpf_map_lookup_elem(map, &elem);
>> + if (!inner_map)
>> + return -1;
>> +
>> + if (use_hashmap) {
>> + idx = bpf_get_prandom_u32() % hashmap_num_keys;
>> + bpf_map_lookup_elem(inner_map, &idx);
> Is the hashmap populated ?
>
Nope. Do you expect this to make a difference? Will try when confirming key /
val size above.
>> + } else {
>> + bpf_task_storage_get(inner_map, lctx->task, &idx,
>> + BPF_LOCAL_STORAGE_GET_F_CREATE);
>> + }
>> +
>> + lctx->loop_hits++;
>> + if (!elem)
>> + lctx->loop_important_hits++;
>> + return 0;
>> +}
>> +
>> +static long loop(u32 index, void *ctx)
>> +{
>> + struct loop_ctx *lctx = (struct loop_ctx *)ctx;
>> + unsigned int map_idx = index % num_maps;
>> +
>> + do_lookup(map_idx, lctx);
>> + if (interleave && map_idx % 3 == 0)
>> + do_lookup(0, lctx);
>> + return 0;
>> +}
>> +
>> +SEC("fentry/" SYS_PREFIX "sys_getpgid")
>> +int get_local(void *ctx)
>> +{
>> + struct loop_ctx lctx;
>> +
>> + lctx.task = bpf_get_current_task_btf();
>> + lctx.loop_hits = 0;
>> + lctx.loop_important_hits = 0;
>> + bpf_loop(10000, &loop, &lctx, 0);
>> + __sync_add_and_fetch(&hits, lctx.loop_hits);
>> + __sync_add_and_fetch(&important_hits, lctx.loop_important_hits);
>> + return 0;
>> +}
>> +
>> +char _license[] SEC("license") = "GPL";
>> --
>> 2.30.2
>>
