Re: [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr()

From: David Gibson

Date: Mon Nov 16 2026 - 23:08:00 EST


On Tue, Nov 17, 2026 at 03:00:36PM +1100, David Gibson wrote:
> On Mon, Nov 16, 2026 at 12:53:05PM -0800, Douglas Anderson wrote:
> > `fdt_find_string_len_()` currently calls `memcmp()` at every byte offset
> > across the string table (`for (p = strtab; p <= last; p++)`). When
> > building or modifying trees with large string tables (such as DTBs and
> > overlays with hundreds of `/__symbols__` or `/__fixups__` labels via
> > `fdt_sw` or `fdt_rw`), scanning multi-kilobyte string tables byte by
> > byte dominates serialization time.
> >
> > Advance `p` between candidate first-byte matches using `memchr()` (with
> > an explicit `slen == 0` check for empty property names and a `tabsize <
> > slen + 1` bounds check before computing `last`), preserving identical
> > suffix-sharing behavior.
> >
> > On one stress test (running the fdtfactor tool across 438 arm64 Qualcomm
> > DTBs) this reduced `fdt_property()` time by ~5.6x.
>
> What we really want is memmem(), which would presumably have a similar
> optimization (and likely more) built in. However, we avoid that to
> make this easier to environments which lack it.
>
> Complexity isn't too great, so this looks reasonable to me

Hmm... actually, thinking about this again, I'm kind of baffled that
the speedup is so large. In the old version, if p is at a character
that doesn't match the start of the string we're looking for, memcmp()
should return almost immediately (after a single byte comparison), so
I'd expect both versions to be - roughly speaking - a single scan
through each byte of the strings block. At least with gcc builtin and
inlined mem*() implementations, I'd expect the performance difference
to be pretty modest between that and the new version.

What was the environment (host CPU, libc, compiler options) you used
for the benchmark?

--
David Gibson (he or they) | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au | minimalist, thank you, not the other way
| around.
http://www.ozlabs.org/~dgibson

Attachment: signature.asc
Description: PGP signature