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 > wrote: > > > > On Mon, 16 Nov 2026 12:53:05 -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. > > > > 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 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