On Tue, Jul 16, 2024 at 6:05 AM Hou Tao <houtao@xxxxxxxxxxxxxxx> wrote:
>
>
> I had hacked bpf verifier (mainly check_stack_range_initialized()) to
> support variable-sized key for both qp-trie and hash-table. For now,
> only one bpf_dynptr is allowed in the key. I also update the benchmark
> in qp-trie patch-set [1] to compare the lookup performance between
> normal hash-table, hash-table with variable-sized key (namely
> dynkey-htab), and qp-trie. The key for hash-table with variable-sized
> key and qp-trie is shown below:
>
> struct test_key {
> __u64 cookie;
> struct bpf_dynptr_user desc;
> };
>
> For randomly generated dynptr key, when the max length of ->desc is big
> (e.g., >128) the performance of qp-trie is the best and it is 20%~80%
> faster then dynkey hash-table. Not sure about the reason why dynkey-htab
> is slower, it may be due to the overhead of hash function or hash
> collision. The performance of dynkey hash table is only 5% good compared
> with the normal hash-table when the max length of ->desc is 128. When
> the max length of ->desc is 512, dynkey hash-table will be 20% faster
> than normal hash table as shown below:
>
> | max length of desc | qp-trie | dynkey-hash-tab |normal hash-tab |
> | --- | --- | --- | --- |
> | 64 | 7.5 M/s | 7.1 M/s | 8.3 M/s |
> | 128 | 6.7 M/s | 5.3 M/s | 5.3 M/s |
> | 256 | 4.9 M/s | 3.4 M/s | 3.2 M/s |
> | 512 | 3.5 M/s | 2.1 M/s | 1.8 M/s |
> | 1024 | 2.5 M/s | 1.4 M/s | 1.1 M/s |
> | 2048 | 1.7 M/s | 0.9 M/s | 0.6 M/s |
>
> When using strings from BTF, kallsyms or Alexa top 1M sites as the
> dynptr in test_key, the performance of qp-trie is about 40% or more
> slower than dynkey hash-table and normal hash-table. The mean length of
> strings in these input files is about 17/24/15 respectively. And there
> is no big difference between the lookup performance of dynkey hash-table
> and normal hash-table. It may be due to the reason the implementation of
> dynkey hash-table, because it invokes jhash three times to get the final
> hash value.
>
> | input | qp-trie | dynkey-hash-tab |normal hash-tab |
> | --- | --- | --- | --- |
> | BTF | 4.6 M/s | 7.3 M/s | 7.4 M/s |
> | kallsyms | 4.7 M/s | 6.5 M/s | 6.5 M/s |
> | top 1M | 2.4 M/s | 4.4 M/s | 4.3 M/s |
Thanks a ton for doing this analysis.
This is very encouraging.
Clearly we need dynkey support in both hash and qp-trie.
Some users will use it to store filenames,
so the average might be > 128 and qp-trie will have an advantage.
In other cases the strings might be short and hash with dynkey
will be useful.
Also let's not forget that it's not only the average that matters.
Right now users need to bump the key size in hash map to a max
possible string while the average might be a fraction of that.
In such case dynkey-hash will outperform normal hash.
Looking forward to patches for qp-trie and hashmap with dynkey.
