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

From: David Gibson

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


On Wed, Nov 18, 2026 at 09:54:18AM +0000, David Laight 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 :-)

It's not supposed to scale, it's supposed to be simple. Device trees
just aren't that large.

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

Doesn't work; as Doug says, suffix sharing is supported.

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