Re: [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr()
From: David Gibson
Date: Mon Nov 16 2026 - 23:00:52 EST
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
--
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