Re: [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr()
From: Doug Anderson
Date: Tue Nov 17 2026 - 11:21:46 EST
Hi David,
On Mon, Nov 16, 2026 at 8:07 PM David Gibson
<david@xxxxxxxxxxxxxxxxxxxxx> wrote:
>
> > > 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
>
> Hmm... actually, thinking about this again, I'm kind of baffled that
> the speedup is so large. In the old version, if p is at a character
> that doesn't match the start of the string we're looking for, memcmp()
> should return almost immediately (after a single byte comparison), so
> I'd expect both versions to be - roughly speaking - a single scan
> through each byte of the strings block. At least with gcc builtin and
> inlined mem*() implementations, I'd expect the performance difference
> to be pretty modest between that and the new version.
>
> What was the environment (host CPU, libc, compiler options) you used
> for the benchmark?
Environment details:
* CPU: AMD Ryzen Threadripper PRO 5995WX (x86_64, AVX2)
* libc: Debian glibc 2.43
* Compiler: gcc (Debian 15.2.0-14) 15.2.0
* Flags: default `meson setup build` (`buildtype=debug`, so `-O0 -g
-fPIC`), though testing at `-Os`, `-O2`, and `-O3` gives the same
~16-17x speedup on the string-table scan itself.
There are two things going on even at `-O2` / `-O3`:
1. **GCC can't inline `memcmp(p, s, slen)` when `slen` isn't a
compile-time constant**: Because `slen` is a runtime variable (and
GCC also can't synthesize a `*p == *s` pre-check on its own since
`slen` could be `0`), GCC at `-O2` / `-O3` emits a full PLT call to
`memcmp()` on every single byte `p` of `strtab`:
.L10:
movq %rbx, %rdx
movq %rbp, %rsi
movq %r15, %rdi
call memcmp@PLT
...
addq $1, %r15
cmpq %r15, %r12
jnb .L10
Even though glibc's `__memcmp_avx2_movbe` returns quickly on a
first-byte mismatch, paying a PLT call/return and function prologue
on every byte of a ~14 KB `/__symbols__` string table (~5.8M
`memcmp()` calls per 800-symbol DTB) dominates runtime. Just adding a
scalar `*p == *s` guard ahead of `memcmp()` already speeds up the
test below by ~8x at `-O2`.
2. **SIMD scanning inside `memchr()` (~2x faster than a scalar byte loop
at `-O2`)**: Instead of stepping one byte per scalar loop iteration,
glibc's `memchr()` (`__memchr_avx2` on x86_64) broadcasts `s[0]`
across a 32-byte YMM register (`vpbroadcastb` + `vpcmpeqb`) and scans
32 bytes per iteration inside a single call, only returning on the
~4-6% of offsets where `p[0] == s[0]`.
(In the commit message, overall `fdt_property()` time dropped by ~5.6x
rather than ~16x because ordinary repeated property names like
`compatible`, `reg`, and `phandle` hit near the beginning of `strtab`
right away, and `fdt_property()` also includes copying the property
value and header bookkeeping.)
Here is a small standalone C program (`bench_find_string.c`) that models
building an 800-symbol string table 200 times (~4.2s -> ~0.25s at `-O2`
on my machine):
---8<---
// SPDX-License-Identifier: GPL-2.0-or-later OR BSD-2-Clause
/*
* Build & run:
* cc -O2 bench_find_string.c -o bench_find_string
* ./bench_find_string
*/
#include <stdio.h>
#include <string.h>
#include <time.h>
typedef const char *(*find_fn)(const char *, int, const char *, int);
__attribute__((noinline))
static const char *old_find_string_len(const char *strtab, int tabsize,
const char *s, int slen)
{
const char *last = strtab + tabsize - (slen + 1);
const char *p;
for (p = strtab; p <= last; p++)
if (memcmp(p, s, slen) == 0 && p[slen] == '\0')
return p;
return NULL;
}
__attribute__((noinline))
static const char *new_find_string_len(const char *strtab, int tabsize,
const char *s, int slen)
{
const char *last;
const char *p = strtab;
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;
}
static double bench(find_fn fn, char names[][32], int nsyms, int iters,
int *out_tabsize)
{
struct timespec t0, t1;
char strtab[32768];
clock_gettime(CLOCK_MONOTONIC, &t0);
for (int it = 0; it < iters; it++) {
int tabsize = 0;
for (int i = 0; i < nsyms; i++) {
int slen = strlen(names[i]);
if (fn(strtab, tabsize, names[i], slen))
continue;
memcpy(strtab + tabsize, names[i], slen + 1);
tabsize += slen + 1;
}
*out_tabsize = tabsize;
}
clock_gettime(CLOCK_MONOTONIC, &t1);
return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) * 1e-9;
}
int main(void)
{
static const char * const prefixes[] = {
"clk_gcc", "reg_vdd", "pinctrl", "i2c_bus",
"usb_phy", "pcie_ep", "mmc_sdhc", "gpu_opp",
};
enum { NUM_SYMS = 800, ITERS = 200 };
char names[NUM_SYMS][32];
int tabsize = 0;
double dt_old, dt_new;
for (int i = 0; i < NUM_SYMS; i++)
snprintf(names[i], sizeof(names[i]), "%s_node_%04d",
prefixes[i % 8], i);
dt_old = bench(old_find_string_len, names, NUM_SYMS, ITERS,
&tabsize);
dt_new = bench(new_find_string_len, names, NUM_SYMS, ITERS,
&tabsize);
printf("%d trees x %d symbols (final strtab = %d B):\n",
ITERS, NUM_SYMS, tabsize);
printf(" old (per-byte memcmp): %.4f s\n", dt_old);
printf(" new (memchr + memcmp): %.4f s (%.1fx faster)\n",
dt_new, dt_old / dt_new);
return 0;
}
--->8---
-Doug