Message-ID: <CAErzpmvp53j0XrT=tyDH6wdrWejdVpJxd_1P6gO_-97-z5JsgQ@mail.gmail.com>
Date: Tue, 6 Jan 2026 10:50:22 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc: ast@...nel.org, eddyz87@...il.com, zhangxiaoqin@...omi.com, 
	ihor.solodrai@...ux.dev, linux-kernel@...r.kernel.org, bpf@...r.kernel.org, 
	pengdonglin <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v10 04/13] libbpf: Optimize type lookup with
 binary search for sorted BTF

On Tue, Jan 6, 2026 at 8:36 AM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Sat, Dec 20, 2025 at 1:38 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> >
> > On Sat, Dec 20, 2025 at 1:28 AM Andrii Nakryiko
> > <andrii.nakryiko@...il.com> wrote:
> > >
> > > On Thu, Dec 18, 2025 at 6:53 PM Donglin Peng <dolinux.peng@...il.com> wrote:
> > > >
> > > > On Fri, Dec 19, 2025 at 7:29 AM Andrii Nakryiko
> > > > <andrii.nakryiko@...il.com> wrote:
> > > > >
> > > > > On Thu, Dec 18, 2025 at 3:31 AM Donglin Peng <dolinux.peng@...il.com> wrote:
> > > > > >
> > > > > > From: pengdonglin <pengdonglin@...omi.com>
> > > > > >
> > > > > > This patch introduces binary search optimization for BTF type lookups
> > > > > > when the BTF instance contains sorted types.
> > > > > >
> > > > > > The optimization significantly improves performance when searching for
> > > > > > types in large BTF instances with sorted types. For unsorted BTF, the
> > > > > > implementation falls back to the original linear search.
> > > > > >
> > > > > > Cc: Eduard Zingerman <eddyz87@...il.com>
> > > > > > Cc: Alexei Starovoitov <ast@...nel.org>
> > > > > > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > > > > > Cc: Alan Maguire <alan.maguire@...cle.com>
> > > > > > Cc: Ihor Solodrai <ihor.solodrai@...ux.dev>
> > > > > > Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> > > > > > Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> > > > > > ---
> > > > > >  tools/lib/bpf/btf.c | 103 ++++++++++++++++++++++++++++++++++----------
> > > > > >  1 file changed, 80 insertions(+), 23 deletions(-)
> > > > > >
> > > > >
> > > > > [...]
> > > > >
> > > > > > +       l = start_id;
> > > > > > +       r = end_id;
> > > > > > +       while (l <= r) {
> > > > > > +               m = l + (r - l) / 2;
> > > > > > +               t = btf_type_by_id(btf, m);
> > > > > > +               tname = btf__str_by_offset(btf, t->name_off);
> > > > > > +               ret = strcmp(tname, name);
> > > > > > +               if (ret < 0) {
> > > > > > +                       l = m + 1;
> > > > > > +               } else {
> > > > > > +                       if (ret == 0)
> > > > > > +                               lmost = m;
> > > > > > +                       r = m - 1;
> > > > > > +               }
> > > > > >         }
> > > > >
> > > > > this differs from what we discussed in [0], you said you'll use that
> > > > > approach. Can you please elaborate on why you didn't?
> > > > >
> > > > >   [0] https://lore.kernel.org/bpf/CAEf4Bzb3Eu0J83O=Y4KA-LkzBMjtx7cbonxPzkiduzZ1Pedajg@mail.gmail.com/
> > > >
> > > > Yes. As mentioned in the v8 changelog [1], the binary search approach
> > > > you referenced was implemented in versions v6 and v7 [2]. However,
> > > > testing revealed a slight performance regression. The root cause was
> > > > an extra strcmp operation introduced in v7, as discussed in [3]. Therefore,
> > > > in v8, I reverted to the approach from v5 [4] and refactored it for clarity.
> > >
> > > If you keep oscillating like that this patch set will never land. 4%
> > > (500us) gain on artificial and unrealistic micro-benchmark is
> > > meaningless and irrelevant, you are just adding more work for yourself
> > > and for reviewers by constantly changing your implementation between
> > > revisions for no good reason.
> >
> > Thank you, I understand and will learn from it. I think the performance gain
> > makes sense. I’d like to share a specific real-world case where this
> > optimization
> > could matter:  the `btf_find_by_name_kind()` function is indeed infrequently
> > used by the BPF subsystem, but it’s heavily relied upon by the ftrace
> > subsystem’s features like `func-args`, `funcgraph-args` [1], and the upcoming
> > `funcgraph-retval` [2]. These features invoke the function nearly once per
> > trace line when outputting, with a call frequency that can reach **100 kHz**
> > in intensive tracing workloads.
> >
> > In such scenarios, the extra `strcmp` operations translate to ~100,000
> > additional
> > string comparisons per second. While this might seem negligible in isolation,
>
> I'm pretty confident it is quite negligible compared to all other
> *useful* work you'll have to do to use that BTF type to format those
> arguments. Yes, 100KHz is pretty frequent, but it won't be anywhere
> close to 4% if you profile the entire end-to-end overhead of emitting
> arguments using func-args.

Thanks, I agree.

>
> > the overhead accumulates under high-frequency tracing—potentially impacting
> > latency for users relying on detailed function argument/return value tracing.
> >
> > Thanks again for pushing for rigor—it helps make the code more cleaner
> > and robust.
> >
> > [1] https://lore.kernel.org/all/20250227185822.639418500@goodmis.org/
> > [2] https://lore.kernel.org/all/20251215034153.2367756-1-dolinux.peng@gmail.com/
> >
> > >
> > >
> > > >
> > > > Benchmark results show that v8 achieves a 4.2% performance improvement
> > > > over v7. If we don't care the performance gain, I will revert to the approach
> > > > in v7 in the next version.
> > > >
> > > > [1] https://lore.kernel.org/bpf/20251126085025.784288-1-dolinux.peng@gmail.com/
> > > > [2] https://lore.kernel.org/all/20251119031531.1817099-1-dolinux.peng@gmail.com/
> > > > [3] https://lore.kernel.org/all/CAEf4BzaqEPD46LddJHO1-k5KPGyVWf6d=duDAxG1q=jykJkMBg@mail.gmail.com/
> > > > [4] https://lore.kernel.org/all/20251106131956.1222864-4-dolinux.peng@gmail.com/
> > > >
>
> [...]

Powered by blists - more mailing lists