All right, so let's get started again.
The next talk is by Anton about optimizing BPF hash map and friends.
Hello, I'm Anton, working at Datapart team at Isovalent and yeah, this is talk about
how simple it is to optimize BPF hash map.
So about a year ago, like a little less, Andreina Kricker proposed, suggested to try new hash
functions for BPF hash map and BPF tech trace map.
And in Selume we use, and in Tatragon we use hashes extensively, so for us it's a big
deal and I decided to give it a try.
So I will briefly provide some like benchmarking how to one-on-one and then we will take a
look at different hash functions and then we will see benchmarks for hash maps which utilize
old hash functions and new hash functions.
So first thing to do when your benchmark is to try to reduce noise because modern CPUs
do everything to ruin your benchmarking.
They will run on different frequency, hyperthreading will get in and in the best case you benchmark
inside kernel because you can disable preemption and interrupts.
So benchmark, we take, if you want to benchmark some function, we first measure some kind
of time source or clock source and then we execute our function, maybe in a loop and
then we measure time once again and then we divide the number of observations by the number
of loops and get our result.
So in some cases we can't execute our function in a loop.
For example, if it's not like an abstract hash function, it's just, if it's just part
of kernel then n is obviously equal to 1 and we need to take an account the time it takes
to get time and one obvious way to do this is to benchmark an empty loop and this give
us roughly how long the get time function works and typically people benchmark with
something like rdtc instruction and if you don't reduce noise then rdtc instruction
is pretty unstable.
So here my CPU obviously runs on two different frequencies and if my function which I want
to benchmark runs 30, 40 cycles then deviation in this case is bigger than function itself
so I can't rely on it.
So if we disable like reduce noise as I said then results become way more stable so here
it's like maybe it looks scary but it's actually like 37 plus minus one cycle so even for very
small functions this makes benchmarking more reliable but in this form rdtc doesn't work
because it's not a serializing instruction which means that if you insert your code here
then it can be executed in the middle of code and even after your code so and it can differ
from execution to execution and so we need some way to serialize it and luckily there
are no ways to do this so just serialize it and there is a white paper written maybe ten
years ago about titanium and it's still valid with some changes from architecture to architecture
but yeah we can do this.
In this case benchmarking like the offset takes a little bit more like it's not 37 cycles
anymore it's 70 cycles but again it's pretty stable and we can use this number to offset
our measurements and in fact I did such benchmarking when I don't run in a loop it's then switch
it to like more dumb benchmarks when you do loops over bpf maps because it's harder to
port things and if you want someone else to try these benchmarks they will have to patch
their kernel and this is not simple.
So let's take a look at several hash functions of interest so jhash is currently used hash
function in the bpf it's Bob Jenkins hash and it's probably was developed some 30 years
ago so spooky hash is another it's a newer version it's not not a newer version it's
a newer hash from Bob Jenkins and then there goes xxhashes xxh32n64 it's a previous generation
of these functions they are available in kernel and we can try them as well and xxh3 is like
the state of art hash function.
So if we just take a look at this plot the orange line which goes there is jhash which
is currently used the green line which looks to be winning here is like the previous generation
xxh64 the blue line this is the newest generation xxh3 and while it looks here that it doesn't
perform as well as xxh64 for small keys it does outperform it and for bpf hash maps we
primarily interested in using it for small keys like I don't know like actually I never
use it like huge keys and in any case this like xxh3 works faster than Jenkins hash and
later I will show that it can be actually run even more faster but one interesting thing
is that the spooky hash it actually like it it performs pretty bad for small keys because
it has a lot of like setup which it does in any case but later it starts outperform like
every hash function I was interested when it does it so it does it at about key size
of 9000 it's cool but it's not the key size of interest for us.
So if we take a look at xxh3 and jhash we can see that the blue line xxh3 it actually
outperforms like jhash for all key sizes and there is also this green line it's jhash2
it's optimized version of jhash which can be used if your key size is multiple of 4
and it's actually used in bloom filters but for some reason not in hash maps.
So if we take closer look at small key sizes we see that yes xxh3 outperforms jhash so
for me it's enough reason to try to benchmark maps with it and let's take a look now at
BPF maps which use hash functions so first one is stack trace map and then hash map in
bloom filters.
So stack trace was actually the main reason for Andrey to propose xxh3 because what it
does it takes a stack trace and then it hashes it and creates a map of IDs which refers to
this traces and if there are hash collisions then old stack traces are lost and we get
incorrect picture about the system and stack traces is not too random so if your hash function
is not very good if it doesn't have very good like avalanche properties then it will create
more collisions for less random data and xxh3 behaves way better than jhash for avalanche
properties and this is like one of reasons and the main reason to use it for stack trace.
The other reason as a benchmark that's also like for stack trace it also runs about twice
faster for typical key sizes because typical key size it's like 8 bytes per stack depth
and this is typically like 60, 80, 100 bytes so xxh3 is like is a very good candidate here
so for hash benchmarks I was primarily focused on lookups because this is what we do the
most and this is the thing which like is easy to measure compared to like more complex pictures
so there are some links to benchmarks I used and scripts to actually execute benchmark
and plot it because like for every change I had to draw some like 100 or 150 pictures
for different key sizes for different fullness of hash maps so it's impossible to do otherwise
like and I had a few pictures here so if we just use xxh3 then it looks like it like the
new map which is orange it outperforms the original map which is blue and here is lookup
speed in cycles vertical and horizontal axis is a key size so the bigger the key the better
the more gain from using the new hash function but if we take like a bigger map I see that
xxh3 as it is degrades for key size 4 and this is already like for me it's a blocker
I can't like propose a change which degrades existing applications so then I went to a
different architecture micro architecture and here I saw that it degrades for different
key size like here it degrades for key size 12 and if you if we take like a bigger map
it degrades for like key size 24 and then I thought how to fix this because it's if
it works for bigger keys then maybe I can utilize this and I did the same thing as bloom bloom
filter currently does so bloom filter executes jh2 for key sizes divisible by 4 and it uses
jhash in other cases so I did the same utilize jhash 2 for key sizes of which are divisible
by 4 but for small ones like it's this keyln divided by 4 keyln 32 it's actually computed
it's just keyln divided by 4 but it's computed during hash initialization and we can decide
for which key sizes we do this and with this hash function I finally see that it doesn't
degrade anywhere so this is like 10k 100k and 100% full which is like the worst case
and if we take another slice this is 100k 100k map with key size 8 and on the left side
it's almost empty on the right side it's 100% full and the bigger key size the bigger gain
for particular key size so for key size 64 new like map with new hash function runs about
50% faster and for key size 128 it runs almost twice faster and bloom filters as I mentioned
they use the jhash 2 for keys divisible by 4 so I don't expect any gain for keys divisible
by 4 at least for small keys and it looks like this so this is like an extreme case
of bloom filter with 9 hashes but and I just did it so it reproduces the plot of hash function
here and yes for small keys it is the same and for bigger keys we have a gain and here
is the key size 240 where xh3 function originally utilizes vector instructions and we can't use
obviously vector instructions in BPF maps and for key size 240 it's like it is expected
to start using vector instructions but there is also scalar implementation which works
faster than jhash but it degrades at this point so and another thing to mention that
old hash functions jhash xxh64 they were designed and optimized it with O2 option in mind so
if we switch to O3 then they will behave the same but xxh3 actually runs like 50-60% faster
so it actually performs way better with O3 so I just jump like here so and I know that
like O3 is no go for kernel like there were several attempts to introduce it and the reason
was that there are no candidates which benefit from this O3 but this one is a particular
candidate like hash if we could use O3 for hash map because not only for xxh3 because
it should be inline then in this case we would be able to get rid of this composite hash
which mixes hashes and just use it as is so yeah as I said for stuck trace map it definitely
makes sense to use it so there is both benefit in speed small one because stuck trace map
the bottleneck for speed is not the hash but the bottleneck for hash collisions is the
hash and for hash map it's a question maybe someone would advise me on what to do with
O3 and after I run like benchmarks on slightly bigger number of architectures then I think
this is also like a good candidate to use in the hash map so here are some links for
benchmarks and paper which I use it for those who will be reading this and thank you
all right thanks a lot any questions you for the O3 thing can you only compile maybe the
like the hash map file with O3 yeah yeah if it is like currently it is disabled like
for every file in kernel for custom build we can enable it but like generally we just
pass O2 everywhere if it's possible just to compile BPF maps with O3 this will solve the
thing yes it's it's not such a big change so you don't have to compile the whole kernel
with O3 yeah yeah yeah it's local code okay any other questions no then thanks a lot
you