Re: [RFC PATCH v4 3/7] libbpf: Optimize type lookup with binary search for sorted BTF

[Eduard Zingerman <eddyz87@gmail.com>]

On Wed, 2025-11-05 at 21:48 +0800, Donglin Peng wrote:
> On Wed, Nov 5, 2025 at 9:17 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Tue, 2025-11-04 at 16:54 -0800, Andrii Nakryiko wrote:
> > > On Tue, Nov 4, 2025 at 4:19 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > 
> > > > On Tue, 2025-11-04 at 16:11 -0800, Andrii Nakryiko wrote:
> > > > 
> > > > [...]
> > > > 
> > > > > > @@ -897,44 +903,134 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> > > > > >         return type_id;
> > > > > >  }
> > > > > > 
> > > > > > -__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> > > > > > +/*
> > > > > > + * Find BTF types with matching names within the [left, right] index range.
> > > > > > + * On success, updates *left and *right to the boundaries of the matching range
> > > > > > + * and returns the leftmost matching index.
> > > > > > + */
> > > > > > +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> > > > > > +                                               __s32 *left, __s32 *right)
> > > > > 
> > > > > I thought we discussed this, why do you need "right"? Two binary
> > > > > searches where one would do just fine.
> > > > 
> > > > I think the idea is that there would be less strcmp's if there is a
> > > > long sequence of items with identical names.
> > > 
> > > Sure, it's a tradeoff. But how long is the set of duplicate name
> > > entries we expect in kernel BTF? Additional O(logN) over 70K+ types
> > > with high likelihood will take more comparisons.
> > 
> > $ bpftool btf dump file vmlinux | grep '^\[' | awk '{print $3}' | sort | uniq -c | sort -k1nr | head
> >   51737 '(anon)'
> >     277 'bpf_kfunc'
> >       4 'long
> >       3 'perf_aux_event'
> >       3 'workspace'
> >       2 'ata_acpi_gtm'
> >       2 'avc_cache_stats'
> >       2 'bh_accounting'
> >       2 'bp_cpuinfo'
> >       2 'bpf_fastcall'
> > 
> > 'bpf_kfunc' is probably for decl_tags.
> > So I agree with you regarding the second binary search, it is not
> > necessary.  But skipping all anonymous types (and thus having to
> > maintain nr_sorted_types) might be useful, on each search two
> > iterations would be wasted to skip those.
> 
> Thank you. After removing the redundant iterations, performance increased
> significantly compared with two iterations.
> 
> Test Case: Locate all 58,719 named types in vmlinux BTF
> Methodology:
> ./vmtest.sh -- ./test_progs -t btf_permute/perf -v
> 
> Two iterations:
> > Condition          | Lookup Time | Improvement |
> > --------------------|-------------|-------------|
> > Unsorted (Linear)  | 17,282 ms   | Baseline    |
> > Sorted (Binary)    | 19 ms       | 909x faster |
> 
> One iteration:
> Results:
> > Condition          | Lookup Time | Improvement |
> > --------------------|-------------|-------------|
> > Unsorted (Linear)  | 17,619 ms   | Baseline    |
> > Sorted (Binary)    | 10 ms       | 1762x faster |
> 
> Here is the code implementation with a single iteration approach.

Could you please also check if there is a difference between having
nr_sorted_types as is and having it equal to nr_types?
Want to understand if this optimization is necessary.

[...]