Re: [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr()
From: David Laight
Date: Wed Nov 18 2026 - 04:54:27 EST
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 :-)
>
> 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.
Even with the code below you want to do the !p[slen] check before the memcmp().
David
>
> On one stress test (running the fdtfactor tool across 438 arm64 Qualcomm
> DTBs) this reduced `fdt_property()` time by ~5.6x.
>
> Assisted-by: Gemini:gemini-pro-prerelease
> Signed-off-by: Douglas Anderson <dianders@xxxxxxxxxxxx>
> ---
> Found this speedup while benchmarking fdtfactor. It's not critical to
> functionality, but seems like a nice win.
>
> Changes in v4:
> - New patch speeding up fdt_find_string_len_() with memchr()
>
> libfdt/fdt.c | 14 +++++++++++---
> 1 file changed, 11 insertions(+), 3 deletions(-)
>
> diff --git a/libfdt/fdt.c b/libfdt/fdt.c
> index d9ccb70345d0..c7cedfba7815 100644
> --- a/libfdt/fdt.c
> +++ b/libfdt/fdt.c
> @@ -348,12 +348,20 @@ int fdt_next_subnode(const void *fdt, int offset)
> const char *fdt_find_string_len_(const char *strtab, int tabsize, const char *s,
> int slen)
> {
> - const char *last = strtab + tabsize - (slen + 1);
> - const char *p;
> + const char *last;
> + const char *p = strtab;
>
> - for (p = strtab; p <= last; p++)
> + if (tabsize < slen + 1)
> + return NULL;
> + if (slen == 0)
> + return memchr(strtab, '\0', tabsize);
> +
> + last = strtab + tabsize - (slen + 1);
> + while (p <= last && (p = memchr(p, s[0], last - p + 1)) != NULL) {
> if (memcmp(p, s, slen) == 0 && p[slen] == '\0')
> return p;
> + p++;
> + }
> return NULL;
> }
>