| Message ID | 20220331122822.14283-1-houtao1@huawei.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | bpf: Introduce ternary search tree for string key | expand |
On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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@mail.gmail.com/ > > 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 >
Hi, On 4/7/2022 1:38 AM, Andrii Nakryiko wrote: > On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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. I have heard about it when check the space efficient of HAT trie [0], because qp-trie needs to save the whole string key in the leaf node and its space efficiency can not be better than ternary search tree for strings with common prefix, so I did not consider about it. But I will do some benchmarks to check the lookup performance and space efficiency of qp-trie and tst for string with common prefix and strings without much common prefix. If qp-trie is better, I think I can take the time to post it as a bpf map if you are OK with that. > > 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 :) Yes. The case with common prefix I known is full file path. > 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. Yes. The global lock is a problem but the splitting is not in-place. I will try to figure out whether the lock can be more scalable after the benchmark test between qp-trie and tst. Regards, Tao [0]: https://github.com/Tessil/hat-trie > > 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@mail.gmail.com/ >> >> 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 >> > .
On Fri, Apr 8, 2022 at 8:08 PM Hou Tao <houtao1@huawei.com> wrote: > > Hi, > > On 4/7/2022 1:38 AM, Andrii Nakryiko wrote: > > On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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. > I have heard about it when check the space efficient of HAT trie [0], because > qp-trie needs to save the whole string key in the leaf node and its space > efficiency can not be better than ternary search tree for strings with common > prefix, so I did not consider about it. But I will do some benchmarks to check > the lookup performance and space efficiency of qp-trie and tst for string with > common prefix and strings without much common prefix. > If qp-trie is better, I think I can take the time to post it as a bpf map if you > are OK with that. You can probably always craft a data set where prefix sharing is so prevalent that space savings are very significant. But I think for a lot of real-world data it won't be as extreme and qp-trie might be very comparable (if not more memory-efficient) due to very compact node layout (which was the point of qp-trie). So I'd be really curious to see some comparisons. Would be great if you can try both! > > > > > > 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 :) > Yes. The case with common prefix I known is full file path. > > 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. > Yes. The global lock is a problem but the splitting is not in-place. I will try > to figure out whether the lock can be more scalable after the benchmark test > between qp-trie and tst. Great, looking forward! > > Regards, > Tao > > [0]: https://github.com/Tessil/hat-trie > > > > 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@mail.gmail.com/ > >> > >> 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 > >> > > . >
Hi, (I send my previous reply in HTML mode mistakenly and the mail list doesn't receive it, so send it again in the plain text mode.) On 4/13/2022 12:09 PM, Andrii Nakryiko wrote: > On Fri, Apr 8, 2022 at 8:08 PM Hou Tao <houtao1@huawei.com> wrote: >> Hi, >> >> On 4/7/2022 1:38 AM, Andrii Nakryiko wrote: >>> On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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. snip >>>> >>> 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. >> I have heard about it when check the space efficient of HAT trie [0], because >> qp-trie needs to save the whole string key in the leaf node and its space >> efficiency can not be better than ternary search tree for strings with common >> prefix, so I did not consider about it. But I will do some benchmarks to check >> the lookup performance and space efficiency of qp-trie and tst for string with >> common prefix and strings without much common prefix. >> If qp-trie is better, I think I can take the time to post it as a bpf map if you >> are OK with that. > You can probably always craft a data set where prefix sharing is so > prevalent that space savings are very significant. But I think for a > lot of real-world data it won't be as extreme and qp-trie might be > very comparable (if not more memory-efficient) due to very compact > node layout (which was the point of qp-trie). So I'd be really curious > to see some comparisons. Would be great if you can try both! It is a bit surprised to me that qp-trie has better memory efficiency (and better lookup performance sometimes) compared with tst when there are not so many common prefix between input strings (All tests below are conducted by implementing the data structure in user-space): * all unique symbols in /proc/kallsyms (171428 sorted symbols, 4.2MB in total) | qp-trie | tst | hash | total memory used (MB) | 8.6 | 11.2 | 22.3 | total update time (us) | 94623 | 87396 | 24477 | total lookup time (us) | 50681 | 67395 | 22842 | * all strings in BTF string area (115980 unsorted strings, 2MB in total) | qp-trie | tst | hash | total memory used (MB) | 5.0 | 7.3 | 13.5 | total update time (us) | 67764 | 43484 | 16462 | total lookup time (us) | 33732 | 31612 | 16462 | * all strings in BTF string area (115980 sorted string, 2MB in total) | qp-trie | tst | hash | total memory used (MB) | 5.0 | 7.3 | 13.5 | total update time (us) | 58745 | 57756 | 16210 | total lookup time (us) | 26922 | 40850 | 16896 | * all files under Linux kernel (2.7MB, 74359 files generated by find utility with "./" stripped) | qp-trie | tst | hash | total memory used (MB) | 4.6 | 5.2 | 11.6 | total update time (us) | 50422 | 28842 | 15255 | total lookup time (us) | 22543 | 18252 | 11836 | When the length of common prefix increases, ternary search tree becomes better than qp-trie. * all files under Linux kernel with a comm prefix (e.g. "/home/houtao") | qp-trie | tst | hash | total memory used (MB) | 5.5 | 5.2 | 12.2 | total update time (us) | 51558 | 29835 | 15345 | total lookup time (us) | 23121 | 19638 | 11540 | Because the lengthy prefix is not so common, and for string map I think the memory efficiency and lookup performance is more importance than update performance, so maybe qp-trie is a better choice for string map ? Any suggestions ? Regards, Tao >> >>> 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 :) >> Yes. The case with common prefix I known is full file path. >>> 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. >> Yes. The global lock is a problem but the splitting is not in-place. I will try >> to figure out whether the lock can be more scalable after the benchmark test >> between qp-trie and tst. > Great, looking forward! > >> Regards, >> Tao >> >> [0]: https://github.com/Tessil/hat-trie >>> 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@mail.gmail.com/ >>>> >>>> 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 >>>> >>> . > .
On Wed, Apr 13, 2022 at 6:03 PM Hou Tao <houtao1@huawei.com> wrote: > > Hi, > > (I send my previous reply in HTML mode mistakenly and the mail list doesn't > receive it, so send it again in the plain text mode.) > > On 4/13/2022 12:09 PM, Andrii Nakryiko wrote: > > On Fri, Apr 8, 2022 at 8:08 PM Hou Tao <houtao1@huawei.com> wrote: > >> Hi, > >> > >> On 4/7/2022 1:38 AM, Andrii Nakryiko wrote: > >>> On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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. > snip > >>>> > >>> 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. > >> I have heard about it when check the space efficient of HAT trie [0], because > >> qp-trie needs to save the whole string key in the leaf node and its space > >> efficiency can not be better than ternary search tree for strings with common > >> prefix, so I did not consider about it. But I will do some benchmarks to check > >> the lookup performance and space efficiency of qp-trie and tst for string with > >> common prefix and strings without much common prefix. > >> If qp-trie is better, I think I can take the time to post it as a bpf map if you > >> are OK with that. > > You can probably always craft a data set where prefix sharing is so > > prevalent that space savings are very significant. But I think for a > > lot of real-world data it won't be as extreme and qp-trie might be > > very comparable (if not more memory-efficient) due to very compact > > node layout (which was the point of qp-trie). So I'd be really curious > > to see some comparisons. Would be great if you can try both! > It is a bit surprised to me that qp-trie has better memory efficiency (and > better lookup performance sometimes) compared with tst when there are not so > many common prefix between input strings (All tests below are conducted by > implementing the data structure in user-space): Thanks for a quick follow up and a benchmark! Low memory use is probably due to the minimal amount of pointers and extra metadata used per node in qp-trie. qp-trie approach is very lean, which is why I was recommending trying it out. > > * all unique symbols in /proc/kallsyms (171428 sorted symbols, 4.2MB in total) > > | qp-trie | tst | hash | > total memory used (MB) | 8.6 | 11.2 | 22.3 | > total update time (us) | 94623 | 87396 | 24477 | > total lookup time (us) | 50681 | 67395 | 22842 | > > * all strings in BTF string area (115980 unsorted strings, 2MB in total) > > | qp-trie | tst | hash | > total memory used (MB) | 5.0 | 7.3 | 13.5 | > total update time (us) | 67764 | 43484 | 16462 | > total lookup time (us) | 33732 | 31612 | 16462 | > > * all strings in BTF string area (115980 sorted string, 2MB in total) > > | qp-trie | tst | hash | > total memory used (MB) | 5.0 | 7.3 | 13.5 | > total update time (us) | 58745 | 57756 | 16210 | > total lookup time (us) | 26922 | 40850 | 16896 | > > * all files under Linux kernel (2.7MB, 74359 files generated by find utility > with "./" stripped) > > | qp-trie | tst | hash | > total memory used (MB) | 4.6 | 5.2 | 11.6 | > total update time (us) | 50422 | 28842 | 15255 | > total lookup time (us) | 22543 | 18252 | 11836 | Seems like lookup time is more or less on par (and for kallsyms noticeably faster), but update is sometimes a bit slower. I don't know if you did your own code or used open-source implementation, but keep in mind that performance of qp-trie very much depends on fast __builtin_popcount, so make sure you are using proper -march when compiling. See [0] [0] https://stackoverflow.com/questions/52161596/why-is-builtin-popcount-slower-than-my-own-bit-counting-function > > When the length of common prefix increases, ternary search tree becomes better > than qp-trie. > > * all files under Linux kernel with a comm prefix (e.g. "/home/houtao") > > | qp-trie | tst | hash | > total memory used (MB) | 5.5 | 5.2 | 12.2 | > total update time (us) | 51558 | 29835 | 15345 | > total lookup time (us) | 23121 | 19638 | 11540 | > > Because the lengthy prefix is not so common, and for string map I think the > memory efficiency and lookup performance is more importance than update > performance, so maybe qp-trie is a better choice for string map ? Any suggestions ? > I'm biased :) But I like the idea of qp-trie as a general purpose ordered and dynamically sized BPF map. It makes no assumption about data being string-like and sharing common prefixes. It can be made to work just as fine with any array of bytes, making it very suitable as a generic lookup table map. Note that upstream implementation does assume zero-terminated strings and no key being a prefix of another key. But all that can be removed. For fixed-length keys this can never happen by construction, for variable-length keys (and we'll be able to support this finally with bpf_dynptr's help very soon), we can record length of the key in each leaf and use that during comparisons. Also note that qp-trie can be internally used by BPF_MAP_TYPE_LPM_TRIE very efficiently and speed it up considerable in the process (and especially to get rid of the global lock). So if you were to invest in a proper full-featured production implementation of a BPF map, I'd start with qp-trie. From available benchmarks it's both faster and more memory efficient than Red-Black trees, which could be an alternative underlying implementation of such ordered and "resizable" map. > Regards, > Tao > >> > >>> 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 :) > >> Yes. The case with common prefix I known is full file path. > >>> 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. > >> Yes. The global lock is a problem but the splitting is not in-place. I will try > >> to figure out whether the lock can be more scalable after the benchmark test > >> between qp-trie and tst. > > Great, looking forward! > > > >> Regards, > >> Tao > >> > >> [0]: https://github.com/Tessil/hat-trie > >>> 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@mail.gmail.com/ > >>>> > >>>> 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 > >>>> > >>> . > > . >
Hi, On 4/15/2022 5:25 AM, Andrii Nakryiko wrote: > On Wed, Apr 13, 2022 at 6:03 PM Hou Tao <houtao1@huawei.com> wrote: >> Hi, >> >> (I send my previous reply in HTML mode mistakenly and the mail list doesn't >> receive it, so send it again in the plain text mode.) >> >> On 4/13/2022 12:09 PM, Andrii Nakryiko wrote: >>> On Fri, Apr 8, 2022 at 8:08 PM Hou Tao <houtao1@huawei.com> wrote: >>>> Hi, >>>> >>>> On 4/7/2022 1:38 AM, Andrii Nakryiko wrote: >>>>> On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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. >> snip >>>>> 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. >>>> I have heard about it when check the space efficient of HAT trie [0], because >>>> qp-trie needs to save the whole string key in the leaf node and its space >>>> efficiency can not be better than ternary search tree for strings with common >>>> prefix, so I did not consider about it. But I will do some benchmarks to check >>>> the lookup performance and space efficiency of qp-trie and tst for string with >>>> common prefix and strings without much common prefix. >>>> If qp-trie is better, I think I can take the time to post it as a bpf map if you >>>> are OK with that. >>> You can probably always craft a data set where prefix sharing is so >>> prevalent that space savings are very significant. But I think for a >>> lot of real-world data it won't be as extreme and qp-trie might be >>> very comparable (if not more memory-efficient) due to very compact >>> node layout (which was the point of qp-trie). So I'd be really curious >>> to see some comparisons. Would be great if you can try both! >> It is a bit surprised to me that qp-trie has better memory efficiency (and >> better lookup performance sometimes) compared with tst when there are not so >> many common prefix between input strings (All tests below are conducted by >> implementing the data structure in user-space): > Thanks for a quick follow up and a benchmark! > > Low memory use is probably due to the minimal amount of pointers and > extra metadata used per node in qp-trie. qp-trie approach is very > lean, which is why I was recommending trying it out. > >> * all unique symbols in /proc/kallsyms (171428 sorted symbols, 4.2MB in total) >> >> | qp-trie | tst | hash | >> total memory used (MB) | 8.6 | 11.2 | 22.3 | >> total update time (us) | 94623 | 87396 | 24477 | >> total lookup time (us) | 50681 | 67395 | 22842 | >> >> * all strings in BTF string area (115980 unsorted strings, 2MB in total) >> >> | qp-trie | tst | hash | >> total memory used (MB) | 5.0 | 7.3 | 13.5 | >> total update time (us) | 67764 | 43484 | 16462 | >> total lookup time (us) | 33732 | 31612 | 16462 | >> >> * all strings in BTF string area (115980 sorted string, 2MB in total) >> >> | qp-trie | tst | hash | >> total memory used (MB) | 5.0 | 7.3 | 13.5 | >> total update time (us) | 58745 | 57756 | 16210 | >> total lookup time (us) | 26922 | 40850 | 16896 | >> >> * all files under Linux kernel (2.7MB, 74359 files generated by find utility >> with "./" stripped) >> >> | qp-trie | tst | hash | >> total memory used (MB) | 4.6 | 5.2 | 11.6 | >> total update time (us) | 50422 | 28842 | 15255 | >> total lookup time (us) | 22543 | 18252 | 11836 | > Seems like lookup time is more or less on par (and for kallsyms > noticeably faster), but update is sometimes a bit slower. I don't know > if you did your own code or used open-source implementation, but keep > in mind that performance of qp-trie very much depends on fast > __builtin_popcount, so make sure you are using proper -march when > compiling. See [0] > > [0] https://stackoverflow.com/questions/52161596/why-is-builtin-popcount-slower-than-my-own-bit-counting-function I used the open source code from github [0] directly. And after adding -march=native, both the lookup and update performance of qp-trie are improved. And the lookup performance of qp-trie is always better than tst, but the update performance of qp-trie is still worse than tst. [0]: https://github.com/fanf2/qp.git >> When the length of common prefix increases, ternary search tree becomes better >> than qp-trie. >> >> * all files under Linux kernel with a comm prefix (e.g. "/home/houtao") >> >> | qp-trie | tst | hash | >> total memory used (MB) | 5.5 | 5.2 | 12.2 | >> total update time (us) | 51558 | 29835 | 15345 | >> total lookup time (us) | 23121 | 19638 | 11540 | >> >> Because the lengthy prefix is not so common, and for string map I think the >> memory efficiency and lookup performance is more importance than update >> performance, so maybe qp-trie is a better choice for string map ? Any suggestions ? >> > I'm biased :) But I like the idea of qp-trie as a general purpose > ordered and dynamically sized BPF map. It makes no assumption about > data being string-like and sharing common prefixes. It can be made to > work just as fine with any array of bytes, making it very suitable as > a generic lookup table map. Note that upstream implementation does > assume zero-terminated strings and no key being a prefix of another > key. But all that can be removed. For fixed-length keys this can never > happen by construction, for variable-length keys (and we'll be able to > support this finally with bpf_dynptr's help very soon), we can record > length of the key in each leaf and use that during comparisons. Using the trailing zero byte to make sure no key will be a prefix of another is simple, but I will check whether or not there is other way to make the bytes array key work out. Alexei had suggest me to use the length of key as part of key just like bpf_lpm_trie_key does, maybe i can try it first. > > Also note that qp-trie can be internally used by BPF_MAP_TYPE_LPM_TRIE > very efficiently and speed it up considerable in the process (and > especially to get rid of the global lock). > > So if you were to invest in a proper full-featured production > implementation of a BPF map, I'd start with qp-trie. From available > benchmarks it's both faster and more memory efficient than Red-Black > trees, which could be an alternative underlying implementation of such > ordered and "resizable" map. Thanks for your suggestions. I will give it a try. Regards, Tao >> Regards, >> Tao >>>>> 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 :) >>>> Yes. The case with common prefix I known is full file path. >>>>> 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. >>>> Yes. The global lock is a problem but the splitting is not in-place. I will try >>>> to figure out whether the lock can be more scalable after the benchmark test >>>> between qp-trie and tst. >>> Great, looking forward! >>> >>>> Regards, >>>> Tao >>>> >>>> [0]: https://github.com/Tessil/hat-trie >>>>> 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@mail.gmail.com/ >>>>>> >>>>>> 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 >>>>>> >>>>> . >>> . > .
On Tue, Apr 26, 2022 at 1:03 AM Hou Tao <houtao1@huawei.com> wrote: > > Hi, > > On 4/15/2022 5:25 AM, Andrii Nakryiko wrote: > > On Wed, Apr 13, 2022 at 6:03 PM Hou Tao <houtao1@huawei.com> wrote: > >> Hi, > >> > >> (I send my previous reply in HTML mode mistakenly and the mail list doesn't > >> receive it, so send it again in the plain text mode.) > >> > >> On 4/13/2022 12:09 PM, Andrii Nakryiko wrote: > >>> On Fri, Apr 8, 2022 at 8:08 PM Hou Tao <houtao1@huawei.com> wrote: > >>>> Hi, > >>>> > >>>> On 4/7/2022 1:38 AM, Andrii Nakryiko wrote: > >>>>> On Thu, Mar 31, 2022 at 5:04 AM Hou Tao <houtao1@huawei.com> 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. > >> snip > >>>>> 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. > >>>> I have heard about it when check the space efficient of HAT trie [0], because > >>>> qp-trie needs to save the whole string key in the leaf node and its space > >>>> efficiency can not be better than ternary search tree for strings with common > >>>> prefix, so I did not consider about it. But I will do some benchmarks to check > >>>> the lookup performance and space efficiency of qp-trie and tst for string with > >>>> common prefix and strings without much common prefix. > >>>> If qp-trie is better, I think I can take the time to post it as a bpf map if you > >>>> are OK with that. > >>> You can probably always craft a data set where prefix sharing is so > >>> prevalent that space savings are very significant. But I think for a > >>> lot of real-world data it won't be as extreme and qp-trie might be > >>> very comparable (if not more memory-efficient) due to very compact > >>> node layout (which was the point of qp-trie). So I'd be really curious > >>> to see some comparisons. Would be great if you can try both! > >> It is a bit surprised to me that qp-trie has better memory efficiency (and > >> better lookup performance sometimes) compared with tst when there are not so > >> many common prefix between input strings (All tests below are conducted by > >> implementing the data structure in user-space): > > Thanks for a quick follow up and a benchmark! > > > > Low memory use is probably due to the minimal amount of pointers and > > extra metadata used per node in qp-trie. qp-trie approach is very > > lean, which is why I was recommending trying it out. > > > >> * all unique symbols in /proc/kallsyms (171428 sorted symbols, 4.2MB in total) > >> > >> | qp-trie | tst | hash | > >> total memory used (MB) | 8.6 | 11.2 | 22.3 | > >> total update time (us) | 94623 | 87396 | 24477 | > >> total lookup time (us) | 50681 | 67395 | 22842 | > >> > >> * all strings in BTF string area (115980 unsorted strings, 2MB in total) > >> > >> | qp-trie | tst | hash | > >> total memory used (MB) | 5.0 | 7.3 | 13.5 | > >> total update time (us) | 67764 | 43484 | 16462 | > >> total lookup time (us) | 33732 | 31612 | 16462 | > >> > >> * all strings in BTF string area (115980 sorted string, 2MB in total) > >> > >> | qp-trie | tst | hash | > >> total memory used (MB) | 5.0 | 7.3 | 13.5 | > >> total update time (us) | 58745 | 57756 | 16210 | > >> total lookup time (us) | 26922 | 40850 | 16896 | > >> > >> * all files under Linux kernel (2.7MB, 74359 files generated by find utility > >> with "./" stripped) > >> > >> | qp-trie | tst | hash | > >> total memory used (MB) | 4.6 | 5.2 | 11.6 | > >> total update time (us) | 50422 | 28842 | 15255 | > >> total lookup time (us) | 22543 | 18252 | 11836 | > > Seems like lookup time is more or less on par (and for kallsyms > > noticeably faster), but update is sometimes a bit slower. I don't know > > if you did your own code or used open-source implementation, but keep > > in mind that performance of qp-trie very much depends on fast > > __builtin_popcount, so make sure you are using proper -march when > > compiling. See [0] > > > > [0] https://stackoverflow.com/questions/52161596/why-is-builtin-popcount-slower-than-my-own-bit-counting-function > I used the open source code from github [0] directly. And after adding > -march=native, both the lookup and update performance of qp-trie are improved. > And the lookup performance of qp-trie is always better than tst, but the update > performance of qp-trie is still worse than tst. Cool, thanks for update! If update is not much worse and the lookup is better, I think it's a pretty good tradeoff! > > [0]: https://github.com/fanf2/qp.git > >> When the length of common prefix increases, ternary search tree becomes better > >> than qp-trie. > >> > >> * all files under Linux kernel with a comm prefix (e.g. "/home/houtao") > >> > >> | qp-trie | tst | hash | > >> total memory used (MB) | 5.5 | 5.2 | 12.2 | > >> total update time (us) | 51558 | 29835 | 15345 | > >> total lookup time (us) | 23121 | 19638 | 11540 | > >> > >> Because the lengthy prefix is not so common, and for string map I think the > >> memory efficiency and lookup performance is more importance than update > >> performance, so maybe qp-trie is a better choice for string map ? Any suggestions ? > >> > > I'm biased :) But I like the idea of qp-trie as a general purpose > > ordered and dynamically sized BPF map. It makes no assumption about > > data being string-like and sharing common prefixes. It can be made to > > work just as fine with any array of bytes, making it very suitable as > > a generic lookup table map. Note that upstream implementation does > > assume zero-terminated strings and no key being a prefix of another > > key. But all that can be removed. For fixed-length keys this can never > > happen by construction, for variable-length keys (and we'll be able to > > support this finally with bpf_dynptr's help very soon), we can record > > length of the key in each leaf and use that during comparisons. > Using the trailing zero byte to make sure no key will be a prefix of another is > simple, but I will check whether or not there is other way to make the bytes > array key work out. Alexei had suggest me to use the length of key as part of > key just like bpf_lpm_trie_key does, maybe i can try it first. Yeah, using key length as part of the key during comparison is what I meant as well. I didn't mean to aritificially add trailing zero (this idea doesn't work for arbitrary binary data). > > > > Also note that qp-trie can be internally used by BPF_MAP_TYPE_LPM_TRIE > > very efficiently and speed it up considerable in the process (and > > especially to get rid of the global lock). > > > > So if you were to invest in a proper full-featured production > > implementation of a BPF map, I'd start with qp-trie. From available > > benchmarks it's both faster and more memory efficient than Red-Black > > trees, which could be an alternative underlying implementation of such > > ordered and "resizable" map. > Thanks for your suggestions. I will give it a try. Awesome! > > Regards, > Tao > > >> Regards, > >> Tao > >>>>> 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 :) > >>>> Yes. The case with common prefix I known is full file path. > >>>>> 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. > >>>> Yes. The global lock is a problem but the splitting is not in-place. I will try > >>>> to figure out whether the lock can be more scalable after the benchmark test > >>>> between qp-trie and tst. > >>> Great, looking forward! > >>> > >>>> Regards, > >>>> Tao > >>>> > >>>> [0]: https://github.com/Tessil/hat-trie > >>>>> 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@mail.gmail.com/ > >>>>>> > >>>>>> 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 > >>>>>> > >>>>> . > >>> . > > . >
Hi, On 4/27/2022 11:57 AM, Andrii Nakryiko wrote: > On Tue, Apr 26, 2022 at 1:03 AM Hou Tao <houtao1@huawei.com> wrote: snip >>> I'm biased :) But I like the idea of qp-trie as a general purpose >>> ordered and dynamically sized BPF map. It makes no assumption about >>> data being string-like and sharing common prefixes. It can be made to >>> work just as fine with any array of bytes, making it very suitable as >>> a generic lookup table map. Note that upstream implementation does >>> assume zero-terminated strings and no key being a prefix of another >>> key. But all that can be removed. For fixed-length keys this can never >>> happen by construction, for variable-length keys (and we'll be able to >>> support this finally with bpf_dynptr's help very soon), we can record >>> length of the key in each leaf and use that during comparisons. >> Using the trailing zero byte to make sure no key will be a prefix of another is >> simple, but I will check whether or not there is other way to make the bytes >> array key work out. Alexei had suggest me to use the length of key as part of >> key just like bpf_lpm_trie_key does, maybe i can try it first. > Yeah, using key length as part of the key during comparison is what I > meant as well. I didn't mean to aritificially add trailing zero (this > idea doesn't work for arbitrary binary data). > >>> Also note that qp-trie can be internally used by BPF_MAP_TYPE_LPM_TRIE >>> very efficiently and speed it up considerable in the process (and >>> especially to get rid of the global lock). >>> >>> So if you were to invest in a proper full-featured production >>> implementation of a BPF map, I'd start with qp-trie. From available >>> benchmarks it's both faster and more memory efficient than Red-Black >>> trees, which could be an alternative underlying implementation of such >>> ordered and "resizable" map. Recently I tried to add concurrent update and deletion support for qp-trie, and found out that hand-over-hand lock scheme may don't work for qp-trie update. The short explanation is that update procedure needs traverse qp-trie twice and the position tuple got in the first pass may be stale due to concurrent updates occurred in the second pass. The detailed explanation is shown below. To reduce space usage for qp-trie, there is no common prefix saved in branch node, so the update of qp-trie needs to traversing qp-trie to find the most similar key firstly, comparing with it to get a (index, flag,) tuple for the leaf key, then traversing qp-trie again to find the insert position by using the tuple. The problem is that, the position tuple may be stale due to concurrent updates occurred in different branch. Considering the following case: When inserting "aa_bind_mount" and "aa_buffers_lock" concurrently into the following qp-trie. The most similar key for "aa_bind_mount" is leaf X, and for "aa_buffers_lock" it is leaf Y. The calculated index tuple for both new keys are the same: (index=3, flag=2). Assuming "aa_bind_mount" is inserted firstly, so when inserting "aa_buffers_lock", the correct index will be (index=4, flag=1) instead of (index=3, flag=2) and the result will be incorrect. branch: index 1 flags 1 bitmap 0x00088 * leaf: a.81577 0 * branch: index 4 flags 1 bitmap 0x00180 * * branch: index 4 flags 2 bitmap 0x02080 * * * leaf: aa_af_perm 1 (leaf X, for aa_bind_mount) * * branch: index 4 flags 2 bitmap 0x00052 * * * leaf: aa_apply_modes_to_perms 6 * * * leaf: aa_asprint_hashstr 7 (leaf Y, for aa_buffers_lock) In order to get a correct position tuple, the intuitive solution is adding common prefix in branch node and letting update procedure to find the insertion position by comparing with the prefix, so it only needs to traverse qp-trie once and hand-over-hand locking scheme can work. I plan to work on qp-trie with common prefix and will update its memory usage and concurrent update/insert speed in this thread once the demo is ready. So any more suggestions ? Regards, Tao >> Thanks for your suggestions. I will give it a try. > Awesome! > >> Regards, >> Tao >> >>>> Regards, >>>> Tao >>>>>>> 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 :) >>>>>> Yes. The case with common prefix I known is full file path. >>>>>>> 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. >>>>>> Yes. The global lock is a problem but the splitting is not in-place. I will try >>>>>> to figure out whether the lock can be more scalable after the benchmark test >>>>>> between qp-trie and tst. >>>>> Great, looking forward! >>>>> >>>>>> Regards, >>>>>> Tao >>>>>> >>>>>> [0]: https://github.com/Tessil/hat-trie >>>>>>> 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@mail.gmail.com/ >>>>>>>> >>>>>>>> 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 >>>>>>>> >>>>>>> . >>>>> . >>> . > .
On Wed, Jun 8, 2022 at 2:00 AM Hou Tao <houtao1@huawei.com> wrote: > > Hi, > > On 4/27/2022 11:57 AM, Andrii Nakryiko wrote: > > On Tue, Apr 26, 2022 at 1:03 AM Hou Tao <houtao1@huawei.com> wrote: > snip > >>> I'm biased :) But I like the idea of qp-trie as a general purpose > >>> ordered and dynamically sized BPF map. It makes no assumption about > >>> data being string-like and sharing common prefixes. It can be made to > >>> work just as fine with any array of bytes, making it very suitable as > >>> a generic lookup table map. Note that upstream implementation does > >>> assume zero-terminated strings and no key being a prefix of another > >>> key. But all that can be removed. For fixed-length keys this can never > >>> happen by construction, for variable-length keys (and we'll be able to > >>> support this finally with bpf_dynptr's help very soon), we can record > >>> length of the key in each leaf and use that during comparisons. > >> Using the trailing zero byte to make sure no key will be a prefix of another is > >> simple, but I will check whether or not there is other way to make the bytes > >> array key work out. Alexei had suggest me to use the length of key as part of > >> key just like bpf_lpm_trie_key does, maybe i can try it first. > > Yeah, using key length as part of the key during comparison is what I > > meant as well. I didn't mean to aritificially add trailing zero (this > > idea doesn't work for arbitrary binary data). > > > >>> Also note that qp-trie can be internally used by BPF_MAP_TYPE_LPM_TRIE > >>> very efficiently and speed it up considerable in the process (and > >>> especially to get rid of the global lock). > >>> > >>> So if you were to invest in a proper full-featured production > >>> implementation of a BPF map, I'd start with qp-trie. From available > >>> benchmarks it's both faster and more memory efficient than Red-Black > >>> trees, which could be an alternative underlying implementation of such > >>> ordered and "resizable" map. > Recently I tried to add concurrent update and deletion support for qp-trie, and > found out that hand-over-hand lock scheme may don't work for qp-trie update. The > short explanation is that update procedure needs traverse qp-trie twice and the > position tuple got in the first pass may be stale due to concurrent updates > occurred in the second pass. The detailed explanation is shown below. > > To reduce space usage for qp-trie, there is no common prefix saved in branch > node, so the update of qp-trie needs to traversing qp-trie to find the most > similar key firstly, comparing with it to get a (index, flag,) tuple for the > leaf key, then traversing qp-trie again to find the insert position by using the > tuple. The problem is that, the position tuple may be stale due to concurrent > updates occurred in different branch. Considering the following case: > > When inserting "aa_bind_mount" and "aa_buffers_lock" concurrently into the > following qp-trie. The most similar key for "aa_bind_mount" is leaf X, and for > "aa_buffers_lock" it is leaf Y. The calculated index tuple for both new keys are > the same: (index=3, flag=2). Assuming "aa_bind_mount" is inserted firstly, so > when inserting "aa_buffers_lock", the correct index will be (index=4, flag=1) > instead of (index=3, flag=2) and the result will be incorrect. > > branch: index 1 flags 1 bitmap 0x00088 > * leaf: a.81577 0 > * branch: index 4 flags 1 bitmap 0x00180 > * * branch: index 4 flags 2 bitmap 0x02080 > * * * leaf: aa_af_perm 1 (leaf X, for aa_bind_mount) > * * branch: index 4 flags 2 bitmap 0x00052 > * * * leaf: aa_apply_modes_to_perms 6 > * * * leaf: aa_asprint_hashstr 7 (leaf Y, for aa_buffers_lock) > > In order to get a correct position tuple, the intuitive solution is adding > common prefix in branch node and letting update procedure to find the insertion > position by comparing with the prefix, so it only needs to traverse qp-trie once > and hand-over-hand locking scheme can work. I plan to work on qp-trie with > common prefix and will update its memory usage and concurrent update/insert > speed in this thread once the demo is ready. So any more suggestions ? > Yeah, that sucks. I'm not sure I completely understand the common prefix solution and whether it will still be qp-trie after that, but if you try that, it would be interesting to learn about the results you get! I think in the worst case we'll have to do tree-wide lock, perhaps maybe having an initial 256-way root node for first byte, and each of 256 subtrees could have their own lock. Alternatively we can do optimistic lockless lookup (in the hope to find a match), but if that fails - take tree-wide lock, and perform the search and insertion again. This will favor lookup hits, obviously, but hopefully that's going to be a common use case where keys are mostly matching. WDYT? > Regards, > Tao > > >> Thanks for your suggestions. I will give it a try. > > Awesome! > > > >> Regards, > >> Tao > >> > >>>> Regards, > >>>> Tao > >>>>>>> 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 :) > >>>>>> Yes. The case with common prefix I known is full file path. > >>>>>>> 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. > >>>>>> Yes. The global lock is a problem but the splitting is not in-place. I will try > >>>>>> to figure out whether the lock can be more scalable after the benchmark test > >>>>>> between qp-trie and tst. > >>>>> Great, looking forward! > >>>>> > >>>>>> Regards, > >>>>>> Tao > >>>>>> > >>>>>> [0]: https://github.com/Tessil/hat-trie > >>>>>>> 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@mail.gmail.com/ > >>>>>>>> > >>>>>>>> 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 > >>>>>>>> > >>>>>>> . > >>>>> . > >>> . > > . >
Hi, On 7/6/2022 6:37 AM, Andrii Nakryiko wrote: > On Wed, Jun 8, 2022 at 2:00 AM Hou Tao <houtao1@huawei.com> wrote: >> Hi, >> >> On 4/27/2022 11:57 AM, Andrii Nakryiko wrote: >>> On Tue, Apr 26, 2022 at 1:03 AM Hou Tao <houtao1@huawei.com> wrote: >> snip >>>>> I'm biased :) But I like the idea of qp-trie as a general purpose >>>>> ordered and dynamically sized BPF map. It makes no assumption about >>>>> data being string-like and sharing common prefixes. It can be made to >>>>> work just as fine with any array of bytes, making it very suitable as >>>>> a generic lookup table map. Note that upstream implementation does >>>>> assume zero-terminated strings and no key being a prefix of another >>>>> key. But all that can be removed. For fixed-length keys this can never >>>>> happen by construction, for variable-length keys (and we'll be able to >>>>> support this finally with bpf_dynptr's help very soon), we can record >>>>> length of the key in each leaf and use that during comparisons. >>>> Using the trailing zero byte to make sure no key will be a prefix of another is >>>> simple, but I will check whether or not there is other way to make the bytes >>>> array key work out. Alexei had suggest me to use the length of key as part of >>>> key just like bpf_lpm_trie_key does, maybe i can try it first. >>> Yeah, using key length as part of the key during comparison is what I >>> meant as well. I didn't mean to aritificially add trailing zero (this >>> idea doesn't work for arbitrary binary data). >>> >>>>> Also note that qp-trie can be internally used by BPF_MAP_TYPE_LPM_TRIE >>>>> very efficiently and speed it up considerable in the process (and >>>>> especially to get rid of the global lock). >>>>> >>>>> So if you were to invest in a proper full-featured production >>>>> implementation of a BPF map, I'd start with qp-trie. From available >>>>> benchmarks it's both faster and more memory efficient than Red-Black >>>>> trees, which could be an alternative underlying implementation of such >>>>> ordered and "resizable" map. >> Recently I tried to add concurrent update and deletion support for qp-trie, and >> found out that hand-over-hand lock scheme may don't work for qp-trie update. The >> short explanation is that update procedure needs traverse qp-trie twice and the >> position tuple got in the first pass may be stale due to concurrent updates >> occurred in the second pass. The detailed explanation is shown below. >> >> To reduce space usage for qp-trie, there is no common prefix saved in branch >> node, so the update of qp-trie needs to traversing qp-trie to find the most >> similar key firstly, comparing with it to get a (index, flag,) tuple for the >> leaf key, then traversing qp-trie again to find the insert position by using the >> tuple. The problem is that, the position tuple may be stale due to concurrent >> updates occurred in different branch. Considering the following case: >> >> When inserting "aa_bind_mount" and "aa_buffers_lock" concurrently into the >> following qp-trie. The most similar key for "aa_bind_mount" is leaf X, and for >> "aa_buffers_lock" it is leaf Y. The calculated index tuple for both new keys are >> the same: (index=3, flag=2). Assuming "aa_bind_mount" is inserted firstly, so >> when inserting "aa_buffers_lock", the correct index will be (index=4, flag=1) >> instead of (index=3, flag=2) and the result will be incorrect. >> >> branch: index 1 flags 1 bitmap 0x00088 >> * leaf: a.81577 0 >> * branch: index 4 flags 1 bitmap 0x00180 >> * * branch: index 4 flags 2 bitmap 0x02080 >> * * * leaf: aa_af_perm 1 (leaf X, for aa_bind_mount) >> * * branch: index 4 flags 2 bitmap 0x00052 >> * * * leaf: aa_apply_modes_to_perms 6 >> * * * leaf: aa_asprint_hashstr 7 (leaf Y, for aa_buffers_lock) >> >> In order to get a correct position tuple, the intuitive solution is adding >> common prefix in branch node and letting update procedure to find the insertion >> position by comparing with the prefix, so it only needs to traverse qp-trie once >> and hand-over-hand locking scheme can work. I plan to work on qp-trie with >> common prefix and will update its memory usage and concurrent update/insert >> speed in this thread once the demo is ready. So any more suggestions ? >> > Yeah, that sucks. I'm not sure I completely understand the common prefix > solution and whether it will still be qp-trie after that, but if you try that, > it would be interesting to learn about the results you get! The code for bpf-qp-trie is mostly ready, and will show some benchmark numbers for prefixed qp-trie and 256-locks qp-trie. For the common prefix solution, the branch node will save the common prefix for its children node just like the following diagram shows: branch node A (prefix: a) | | *--------*--------* | | leaf X (ab) | branch node (prefix: d) *------*--------* | | leaf Y (adc) leaf Z (admin) The newly-add prefix is only used by update procedure and is updated by both update and delete procedure due to the prefix splitting and merging. After adding the common prefix, the hand-over-hand lock scheme works, but the memory usage is bad compared with 256-lock qp-trie and hash table. For the strings in BTF, memory usage of qp-trie with prefix is bigger than hash table as shown below. * Notation (All below tests are conducted by creating and manipulating bpf maps in kernel through libbpf) tree-lock: prefixed qp-trie uses hand-over-hand lock scheme 256-lock: qp-trie ues 256 global locks for 256 sub-trees htab: hashtab data set | kallsyms | btf | knl | top_1m | tree-lock memory (MB) | 32.6 | 20.5 | 15.4 | 158.1 | 256-lock memory (MB) | 19.1 | 12.0 | 9.9 | 90.6 | htab memory (MB) | 36.7 | 17.1 | 16.2 | 206.8 | The lookup performance of prefixed qp-trie is nearly the same with 256-lock qp-trie, but is still bad then 256-lock qp-trie when thread number is 1 or 2. From the below table, it seems lookup procedure don't scale very well, because there are not too much differences between the result of number thread 6 and 8. After a quick perf report, it seems the overhead comes from copy_to_user() and fget(). * all unique symbols in /proc/kallsyms thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock lookup time (ms) | 144.8 | 92.5 | 71.7 | 59.9 | 52.9 | 49.1 | 45.8 | 44.3 | 256-lock lookup time (ms) | 136.7 | 91.1 | 69.9 | 58.1 | 51.5 | 47.6 | 44.9 | 44.3 | htab lookup time (ms) | 118.8 | 81.7 | 59.9 | 47.2 | 44.0 | 41.7 | 40.3 | 40.9 | * all strings in BTF string area thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock lookup time (ms) | 109.7 | 71.7 | 54.4 | 44.2 | 38.6 | 34.7 | 33.6 | 32.1 | 256-lock lookup time (ms) | 101.3 | 69.0 | 51.5 | 41.2 | 36.0 | 32.8 | 32.3 | 30.4 | htab lookup time (ms) | 83.2 | 59.3 | 42.7 | 30.7 | 28.7 | 27.8 | 27.4 | 31.7 | * all files under Linux kernel without prefix generated by find thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock lookup time (ms) | 73.8 | 47.7 | 36.7 | 29.9 | 26.5 | 22.9 | 20.9 | 20.4 | 256-lock lookup time (ms) | 67.9 | 39.0 | 36.2 | 28.1 | 23.1 | 21.4 | 19.6 | 20.1 | htab lookup time (ms) | 53.9 | 39.0 | 33.2 | 25.8 | 21.1 | 21.9 | 20.9 | 20.5 | * domain name for the top 1-million sites thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock lookup time (ms) | 1032.6 | 660.8 | 473.8 | 383.0 | 333.4 | 293.2 | 259.0 | 241.2 | 256-lock lookup time (ms) | 972.1 | 607.3 | 435.6 | 348.7 | 298.0 | 264.8 | 240.5 | 222.5 | htab lookup time (ms) | 590.6 | 435.2 | 341.2 | 268.4 | 229.2 | 206.0 | 197.9 | 194.8 | For update procedure, performance of hand-over-hand lock will be much better than 256-locks when number of threads is greater than 4. But it doesn't have too much win against 256-locks for delete procedure. The main reason may be now 3-locks are taken for delete procedure (2 locks for update procedure) because now qp_trie_node instead of its pointer is saved in qp trie twigs and it can improve the lookup performance by ~30% by decreasing one pointer de-reference. * all unique symbols in /proc/kallsyms thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock update time (ms) | 305.4 | 243.2 | 199.9 | 189.6 | 188.1 | 191.5 | 185.5 | 191.2 | 256-lock update time (ms) | 251.6 | 209.7 | 202.6 | 202.2 | 216.5 | 250.0 | 209.8 | 236.2 | htab update time (ms) | 173.6 | 124.1 | 95.3 | 96.9 | 84.8 | 78.2 | 75.8 | 74.4 | tree-lock delete time (ms) | 267.4 | 231.1 | 199.7 | 194.8 | 189.4 | 190.0 | 190.6 | 191.0 | 256-lock delete time (ms) | 209.2 | 161.8 | 166.0 | 164.2 | 162.1 | 161.8 | 160.7 | 163.3 | htab delete time (ms) | 114.7 | 84.3 | 65.9 | 56.9 | 53.7 | 52.4 | 52.5 | 53.6 | * all strings in BTF string area thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock update time (ms) | 215.9 | 184.1 | 146.7 | 127.6 | 93.3 | 86.9 | 81.3 | 77.9 | 256-lock update time (ms) | 173.7 | 130.9 | 116.4 | 107.9 | 101.3 | 98.1 | 95.7 | 91.6 | htab update time (ms) | 113.1 | 84.5 | 76.8 | 63.3 | 55.1 | 45.5 | 40.7 | 40.5 | tree-lock delete time (ms) | 187.5 | 144.2 | 116.8 | 106.6 | 111.3 | 90.1 | 83.5 | 82.0 | 256-lock delete time (ms) | 148.4 | 117.2 | 120.5 | 104.8 | 94.3 | 88.7 | 95.3 | 90.8 | htab delete time (ms) | 84.1 | 73.3 | 47.8 | 41.2 | 40.0 | 37.3 | 37.8 | 38.0 | * all files under Linux kernel without prefix generated by find thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock update time (ms) | 143.1 | 112.1 | 87.9 | 94.8 | 91.4 | 89.7 | 87.9 | 86.9 | 256-lock update time (ms) | 121.8 | 113.2 | 117.9 | 117.6 | 118.3 | 120.7 | 119.8 | 120.5 | htab update time (ms) | 85.4 | 66.7 | 52.9 | 44.6 | 39.2 | 37.8 | 36.1 | 34.8 | tree-lock delete time (ms) | 126.1 | 110.1 | 86.4 | 77.7 | 74.4 | 81.8 | 88.3 | 91.7 | 256-lock delete time (ms) | 100.0 | 88.7 | 95.9 | 93.5 | 77.1 | 88.1 | 76.7 | 85.5 | htab delete time (ms) | 59.0 | 50.0 | 31.7 | 32.5 | 31.4 | 31.1 | 27.1 | 29.6 | * domain name for the top sites thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock update time (ms) | 1890.2 | 1289.4 | 949.8 | 790.0 | 677.6 | 614.2 | 567.6 | 536.2 | 256-lock update time (ms) | 1521.4 | 1173.1 | 1136.2 | 1075.2 | 1059.3 | 1043.6 | 1022.2 | 988.1 | htab update time (ms) | 896.5 | 618.5 | 474.1 | 396.2 | 357.0 | 319.3 | 297.1 | 288.2 | tree-lock delete time (ms) | 1856.3 | 1290.1 | 1007.1 | 881.5 | 804.7 | 755.7 | 725.9 | 700.2 | 256-lock delete time (ms) | 1429.3 | 1066.3 | 1018.1 | 955.2 | 923.4 | 889.3 | 870.3 | 836.6 | htab delete time (ms) | 648.8 | 480.8 | 377.6 | 313.7 | 284.1 | 280.4 | 273.9 | 269.9 | But if the input data set is inserted or deleted in sorted order, hand-over-hand lock scheme don't work well as show below: * all sorted strings in BTF string area thread number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | tree-lock update time (ms) | 201.2 | 185.1 | 156.6 | 131.6 | 151.3 | 134.2 | 144.7 | 130.6 | 256-lock update time (ms) | 162.7 | 132.6 | 135.6 | 136.8 | 138.9 | 137.8 | 149.4 | 161.0 | htab update time (ms) | 114.5 | 89.3 | 75.1 | 55.1 | 48.2 | 52.5 | 53.7 | 52.5 | tree-lock delete time (ms) | 176.7 | 172.1 | 163.7 | 154.3 | 134.1 | 133.6 | 133.3 | 133.0 | 256-lock delete time (ms) | 139.4 | 128.2 | 138.8 | 131.1 | 112.2 | 107.1 | 128.8 | 130.9 | htab delete time (ms) | 81.1 | 67.1 | 44.7 | 38.3 | 37.5 | 41.1 | 44.3 | 43.3 | > I think in the worst case we'll have to do tree-wide lock, perhaps > maybe having an initial 256-way root node for first byte, and each of > 256 subtrees could have their own lock. Yes, I think 256-way root node and 256 locks is not so bad choice for us as we can see from the test results above. And for prefixed qp-trie its memory usage is too bad, so I prefer 256 subtree locks for now. > Alternatively we can do optimistic lockless lookup (in the hope to > find a match), but if that fails - take tree-wide lock, and perform > the search and insertion again. This will favor lookup hits, > obviously, but hopefully that's going to be a common use case where > keys are mostly matching. Lockless programming is hard, but I think we can try these optimization after supporting the basic operations for qp-trie. Regards, Tao > > WDYT? > > >> Regards, >> Tao >> >>>> Thanks for your suggestions. I will give it a try. >>> Awesome! >>> >>>> Regards, >>>> Tao >>>> >>>>>> Regards, >>>>>> Tao >>>>>>>>> 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 :) >>>>>>>> Yes. The case with common prefix I known is full file path. >>>>>>>>> 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. >>>>>>>> Yes. The global lock is a problem but the splitting is not in-place. I will try >>>>>>>> to figure out whether the lock can be more scalable after the benchmark test >>>>>>>> between qp-trie and tst. >>>>>>> Great, looking forward! >>>>>>> >>>>>>>> Regards, >>>>>>>> Tao >>>>>>>> >>>>>>>> [0]: https://github.com/Tessil/hat-trie >>>>>>>>> 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@mail.gmail.com/ >>>>>>>>>> >>>>>>>>>> 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 >>>>>>>>>> >>>>>>>>> . >>>>>>> . >>>>> . >>> . > .
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. Regards, Tao [1]: https://lore.kernel.org/bpf/CAADnVQJUJp3YBcpESwR3Q1U6GS1mBM=Vp-qYuQX7eZOaoLjdUA@mail.gmail.com/ 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