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

From: Doug Anderson

Date: Wed Nov 18 2026 - 12:25:00 EST


Hi David,

On Wed, Nov 18, 2026 at 1:54 AM David Laight
<david.laight.linux@xxxxxxxxx> wrote:
>
> On Mon, 16 Nov 2026 12:53:05 -0800
> Douglas Anderson <dianders@xxxxxxxxxxxx> 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.
>
> Are those symbols just in a linear list with embedded '\0' ?
> That doesn't scale well at all :-)

I'm assuming from your :-) that your "That doesn't scale well at all"
was intended to be wrapped in <sarcasm> tags? :-P


> > 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.
>
> Might it be better to scan for the '\0' that terminated/separates the strings?
> Then you do one memcmp() for each string/symbol rather than for each time
> the first character appears in any string.

Two things work against scanning for `'\0'` here:

1. `fdt_find_string_len_()` intentionally supports suffix sharing (e.g.
`"controller"` matching the tail of `"interrupt-controller\0"`), so
scanning for `'\0'` can't check `nul + 1` (the start of the next
string) -- it has to start at `strtab + slen` and test `p = nul -
slen` before each `'\0'`.

2. Every stored string ends with `'\0'`, whereas `s[0]` only appears in
a smaller fraction of bytes. On a real upstream Qualcomm base DTB's
`dt_strings` block (855 strings in 11,259 bytes, average 13.2 bytes
per string), `'\0'` occurs on 7.6% of bytes while `s[0]` averages
3.9%. Replaying those 855 insertions makes 362k `memchr()` calls when
scanning for `'\0'` vs. 187k `memchr()` calls when scanning for
`s[0]`.

> Even with the code below you want to do the !p[slen] check before the memcmp().

Agreed. Since `p <= last` (`strtab + tabsize - (slen + 1)`), `p[slen]`
is always in bounds, and checking `!p[slen]` (i.e. `p[slen] == '\0'`)
before `memcmp(p, s, slen) == 0` cuts the `memcmp()` call count across
that 855-string replay from 187k down to 14.3k (the exact same 14.3k
`memcmp()` calls you'd get from scanning for `'\0'` with a `*p == *s`
pre-check, just with half as many `memchr()` stops).

Timing 200 replays of that 855-string (11,259-byte) Qualcomm
`dt_strings` block with `gcc 15.2 -O2` on x86_64:
* Original (per-byte `memcmp`): 3.45 s
* Scan for `'\0'`, `memcmp(nul - slen, s, slen)`: 0.45 s
* Scan for `'\0'`, `*p == *s` then `memcmp`: 0.36 s
* Scan for `s[0]`, `memcmp` then `!p[slen]` (merged `c954f9dd8357`):
0.27 s
* Scan for `s[0]`, `!p[slen]` then `memcmp`: 0.21 s (~20% faster)

Since you already applied this patch to `main` (`c954f9dd8357`), so
I'll include a 1-line follow-up patch swapping the check order (with
`Suggested-by:` you) in v5.

-Doug