On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@xxxxxxxxxx> wrote: > > Hi, > > The initial motivation for the patchset is due to the suggestion of Alexei. > During the discuss of supporting of string key in hash-table, he saw the > space efficiency of ternary search tree under our early test and suggest > us to post it as a new bpf map [1]. > > Ternary search tree is a special trie where nodes are arranged in a > manner similar to binary search tree, but with up to three children > rather than two. The three children correpond to nodes whose value is > less than, equal to, and greater than the value of current node > respectively. > > In ternary search tree map, only the valid content of string is saved. > The trailing null byte and unused bytes after it are not saved. If there > are common prefixes between these strings, the prefix is only saved once. > Compared with other space optimized trie (e.g. HAT-trie, succinct trie), > the advantage of ternary search tree is simple and being writeable. > > Below are diagrams for ternary search map when inserting hello, he, > test and tea into it: > > 1. insert "hello" > > [ hello ] > > 2. insert "he": need split "hello" into "he" and "llo" > > [ he ] > | > * > | > [ llo ] > > 3. insert "test": add it as right child of "he" > > [ he ] > | > *-------x > | | > [ llo ] [ test ] > > 5. insert "tea": split "test" into "te" and "st", > and insert "a" as left child of "st" > > [ he ] > | > x------*-------x > | | | > [ ah ] [ llo ] [ te ] > | > * > | > [ st ] > | > x----* > | > [ a ] > > As showed in above diagrams, the common prefix between "test" and "tea" > is "te" and it only is saved once. Also add benchmarks to compare the > memory usage and lookup performance between ternary search tree and > hash table. When the common prefix is lengthy (~192 bytes) and the > length of suffix is about 64 bytes, there are about 2~3 folds memory > saving compared with hash table. But the memory saving comes at prices: > the lookup performance of tst is about 2~3 slower compared with hash > table. See more benchmark details on patch #2. > > Comments and suggestions are always welcome. > Have you heard and tried qp-trie ([0]) by any chance? It is elegant and simple data structure. By all the available benchmarks it handily beats Red-Black trees in terms of memory usage and performance (though it of course depends on the data set, just like "memory compression" for ternary tree of yours depends on large set of common prefixes). qp-trie based BPF map seems (at least on paper) like a better general-purpose BPF map that is dynamically sized (avoiding current HASHMAP limitations) and stores keys in sorted order (and thus allows meaningful ordered iteration *and*, importantly for longest prefix match tree, allows efficient prefix matches). I did a quick experiment about a month ago trying to replace libbpf's internal use of hashmap with qp-trie for BTF string dedup and it was slightly slower than hashmap (not surprisingly, though, because libbpf over-sizes hashmap to avoid hash collisions and long chains in buckets), but it was still very decent even in that scenario. So I've been mulling the idea of implementing BPF map based on qp-trie elegant design and ideas, but can't find time to do this. This prefix sharing is nice when you have a lot of long common prefixes, but I'm a bit skeptical that as a general-purpose BPF data structure it's going to be that beneficial. 192 bytes of common prefixes seems like a very unusual dataset :) More specifically about TST implementation in your paches. One global per-map lock I think is a very big downside. We have LPM trie which is very slow in big part due to global lock. It might be possible to design more granular schema for TST, but this whole in-place splitting logic makes this harder. I think qp-trie can be locked in a granular fashion much more easily by having a "hand over hand" locking: lock parent, find child, lock child, unlock parent, move into child node. Something like that would be more scalable overall, especially if the access pattern is not focused on a narrow set of nodes. Anyways, I love data structures and this one is an interesting idea. But just my few cents of "production-readiness" for general-purpose data structures for BPF. [0] https://dotat.at/prog/qp/README.html > Regards, > Tao > > [1]: https://lore.kernel.org/bpf/CAADnVQJUJp3YBcpESwR3Q1U6GS1mBM=Vp-qYuQX7eZOaoLjdUA@xxxxxxxxxxxxxx/ > > Hou Tao (2): > bpf: Introduce ternary search tree for string key > selftests/bpf: add benchmark for ternary search tree map > > include/linux/bpf_types.h | 1 + > include/uapi/linux/bpf.h | 1 + > kernel/bpf/Makefile | 1 + > kernel/bpf/bpf_tst.c | 411 +++++++++++++++++ > tools/include/uapi/linux/bpf.h | 1 + > tools/testing/selftests/bpf/Makefile | 5 +- > tools/testing/selftests/bpf/bench.c | 6 + > .../selftests/bpf/benchs/bench_tst_map.c | 415 ++++++++++++++++++ > .../selftests/bpf/benchs/run_bench_tst.sh | 54 +++ > tools/testing/selftests/bpf/progs/tst_bench.c | 70 +++ > 10 files changed, 964 insertions(+), 1 deletion(-) > create mode 100644 kernel/bpf/bpf_tst.c > create mode 100644 tools/testing/selftests/bpf/benchs/bench_tst_map.c > create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_tst.sh > create mode 100644 tools/testing/selftests/bpf/progs/tst_bench.c > > -- > 2.31.1 >
