All of lore.kernel.org
 help / color / mirror / Atom feed
From: David Gibson <david@gibson.dropbear.id.au>
To: Doug Anderson <dianders@chromium.org>
Cc: "David Laight" <david.laight.linux@gmail.com>,
	Devicetree-compiler@vger.kernel.org,
	"Rob Herring" <robh@kernel.org>,
	"Krzysztof Kozlowski" <krzk+dt@kernel.org>,
	"Conor Dooley" <conor+dt@kernel.org>,
	"Konrad Dybcio" <konradybcio@kernel.org>,
	Devicetree@vger.kernel.org,
	"Tudor Ambarus" <tudor.ambarus@linaro.org>,
	"Chen-Yu Tsai" <wenst@chromium.org>,
	"Saravana Kannan" <saravanak@kernel.org>,
	"André Draszik" <andre.draszik@linaro.org>,
	"Simon Glass" <sjg@chromium.org>,
	linux-kernel@vger.kernel.org,
	"Brian Norris" <briannorris@chromium.org>,
	"Peter Griffin" <peter.griffin@linaro.org>,
	"Julius Werner" <jwerner@chromium.org>
Subject: Re: [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr()
Date: Thu, 19 Nov 2026 16:32:20 +1100	[thread overview]
Message-ID: <av6J47fOAYxejSgr@gractus.seuss> (raw)
In-Reply-To: <CAD=FV=XZP5ZD8J8k5wD5XgQP-sF1SEoZNkRkXyYL1ZeuU187_A@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 3917 bytes --]

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
> <david.laight.linux@gmail.com> wrote:
> >
> > On Mon, 16 Nov 2026 12:53:05 -0800
> > Douglas Anderson <dianders@chromium.org> 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 <sarcasm> 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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

  parent reply	other threads:[~2026-11-19  5:38 UTC|newest]

Thread overview: 38+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16 20:52 [PATCH v4 00/14] fdtfactor: Introduce fdtfactor to auto-factor overlays Douglas Anderson
2026-11-16 20:52 ` [PATCH v4 01/14] README: Add overview blurbs for dtc and ancillary tools Douglas Anderson
2026-11-16 20:52 ` [PATCH v4 02/14] pylibfdt: Make Property a subclass of bytes instead of bytearray Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 03/14] pylibfdt: Trim Fdt bytearray to totalsize() in FdtSw.as_fdt() Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 04/14] pylibfdt: Add Property.from_*() creation methods Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 05/14] pylibfdt: Unpack Property.as_list() in a single struct.unpack() call Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 06/14] pylibfdt: Speed up FdtRo.properties() with a C helper Douglas Anderson
2026-11-17  3:47   ` David Gibson
2026-11-17 16:17     ` Doug Anderson
2026-11-20 15:22   ` Simon Glass
2026-11-20 17:50     ` Doug Anderson
2026-11-16 20:53 ` [PATCH v4 07/14] libpydt: Add DeviceTree live tree representation Douglas Anderson
2026-11-20 15:20   ` Simon Glass
2026-11-16 20:53 ` [PATCH v4 08/14] libfdt: Speed up fdt_find_string_len_() with memchr() Douglas Anderson
2026-11-17  4:00   ` David Gibson
2026-11-17  4:07     ` David Gibson
2026-11-17 16:21       ` Doug Anderson
2026-11-19  5:38         ` David Gibson
2026-11-18  9:54   ` David Laight
2026-11-18 17:24     ` Doug Anderson
2026-11-18 19:15       ` David Laight
2026-11-18 20:39         ` Doug Anderson
2026-11-18 22:15           ` David Laight
2026-11-19  5:35             ` David Gibson
2026-11-19  5:32       ` David Gibson [this message]
2026-11-19  5:29     ` David Gibson
2026-11-16 20:53 ` [PATCH v4 09/14] libfdt: overlay: Update base /__local_fixups__ on apply Douglas Anderson
2026-11-20 15:28   ` Simon Glass
2026-11-20 17:51     ` Doug Anderson
2026-11-16 20:53 ` [PATCH v4 10/14] fdtfactor: Add tool to split DTBs into a base DTB and overlays Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 11/14] fdtfactor: Add -S/--strip-local-fixups option Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 12/14] fdtfactor: Support compressed DTB inputs and outputs Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 13/14] fdtfactor: Add compiled FIT factoring support Douglas Anderson
2026-11-16 20:53 ` [PATCH v4 14/14] fdtfactor: Parallelize blob compression and decompression Douglas Anderson
2026-11-20 15:29   ` Simon Glass
2026-11-20 17:53     ` Doug Anderson
2026-11-17  3:48 ` [PATCH v4 00/14] fdtfactor: Introduce fdtfactor to auto-factor overlays David Gibson
2026-11-17  4:01   ` David Gibson

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=av6J47fOAYxejSgr@gractus.seuss \
    --to=david@gibson.dropbear.id.au \
    --cc=Devicetree-compiler@vger.kernel.org \
    --cc=Devicetree@vger.kernel.org \
    --cc=andre.draszik@linaro.org \
    --cc=briannorris@chromium.org \
    --cc=conor+dt@kernel.org \
    --cc=david.laight.linux@gmail.com \
    --cc=dianders@chromium.org \
    --cc=jwerner@chromium.org \
    --cc=konradybcio@kernel.org \
    --cc=krzk+dt@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=peter.griffin@linaro.org \
    --cc=robh@kernel.org \
    --cc=saravanak@kernel.org \
    --cc=sjg@chromium.org \
    --cc=tudor.ambarus@linaro.org \
    --cc=wenst@chromium.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.