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

From: David Gibson

Date: Thu Nov 19 2026 - 00:39:47 EST


On Wed, Nov 18, 2026 at 09:24:38AM -0800, Doug Anderson wrote:
> 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.

Uh.. "you" seems to be referring to two different people here. I
applied the patch, David Laight suggested the optimization.

Fwiw, since this further optimization is essentially free in terms of
code complexity, I'm certainly happy to apply it. I am absolutely not
keen on further micro-optimization of this.

--
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