bpf: Using binary search to improve the performance of btf_find_by_name_kind
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v4 Latest3 patches 9 repliesIn review
- v3 RFC1 patch 7 repliesSuperseded
Changes in v4 from the cover letter
- Divide the patch into two parts: kernel and libbpf
- Use Eduard's code to sort btf_types in the btf__dedup function
- Correct some btf testcases due to modifications of the order of btf_types.
Patches in v4 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/3 | libbpf: Sort btf_types in ascending order by nametools/ tools/ tools/ | +268 | 3 replies | |
| 2/3 | bpf: Using binary search to improve the performance of btf_find_by_name_kindinclude/ kernel/ | +147 | 4 replies | |
| 3/3 | libbpf: Using binary search to improve the performance of btf__find_by_name_kindtools/ | +140 | 2 replies |
Reviews trailers per patch
None of the 3 patches has a Reviewed-by or Acked-by.
| Patch | Masami Hiramatsu (Google) |
|---|---|
| 1/3 | |
| 2/3 | T-b |
| 3/3 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind
Currently, we are only using the linear search method to find the type id by the name, which has a time complexity of O(n). This change involves sorting the names of btf types in ascending order and using binary search, which has a time complexity of O(log(n)). This idea was inspired by the following patch:
60443c88f3a8 ("kallsyms: Improve the performance of kallsyms_lookup_name()").
At present, this improvement is only for searching in vmlinux's and module's BTFs.
Another change is the search direction, where we search the BTF first and then its base, the type id of the first matched btf_type will be returned.
Here is a time-consuming result that finding 87590 type ids by their names in vmlinux's BTF.
Before: 158426 ms
After: 114 ms
The average lookup performance has improved more than 1000x in the above scenario.
v4:
- Divide the patch into two parts: kernel and libbpf
- Use Eduard's code to sort btf_types in the btf__dedup function
- Correct some btf testcases due to modifications of the order of btf_types.
v3:
- Link: https://lore.kernel.org/all/[email protected]/
- Sort btf_types during build process other than during boot, to reduce the overhead of memory and boot time.
v2:
- Link: https://lore.kernel.org/all/[email protected]
Donglin Peng (3):
libbpf: Sort btf_types in ascending order by name
bpf: Using binary search to improve the performance of
btf_find_by_name_kind
libbpf: Using binary search to improve the performance of
btf__find_by_name_kind
include/linux/btf.h | 1 + kernel/bpf/btf.c | 157 +++++++++- tools/lib/bpf/btf.c | 274 +++++++++++++--- tools/testing/selftests/bpf/prog_tests/btf.c | 296 +++++++++--------- .../bpf/prog_tests/btf_dedup_split.c | 64 ++-- 5 files changed, 555 insertions(+), 237 deletions(-)
Signature · 1 line
2.34.1