All of lore.kernel.org
 help / color / mirror / Atom feed
From: David Gibson <david@gibson.dropbear.id.au>
To: David Laight <david.laight.linux@gmail.com>
Cc: "Doug Anderson" <dianders@chromium.org>,
	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:35:57 +1100	[thread overview]
Message-ID: <av6KvEBGjIbY-2oC@gractus.seuss> (raw)
In-Reply-To: <20261118221538.4de223fd@pumpkin>

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

On Wed, Nov 18, 2026 at 10:15:38PM +0000, David Laight wrote:
> On Wed, 18 Nov 2026 12:39:59 -0800
> Doug Anderson <dianders@chromium.org> wrote:
> 
> > Hi David,
> > 
> > On Wed, Nov 18, 2026 at 11:15 AM David Laight
> > <david.laight.linux@gmail.com> wrote:
> > >  
> > > > 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]`.  
> > >
> > > You need to count the number of times that a letter that is the first
> > > character of a string you are going to lookup appears in the entire buffer.
> > > There might only be one 'j' in the entire buffer - but you never look for it.
> > > (But I might still be wrong)  
> > 
> > That 3.9% (`187,315` `memchr()` calls across ~4.77M scanned bytes) was
> > actually measured directly by replaying those 855 real lookups (`s[0]`
> > of each string being inserted), not an unweighted 1/26 average across
> > the alphabet. Even though common prefixes like `'p'`, `'u'`, `'q'`, and
> > `'s'` get looked up a lot, 26.6% of the `dt_strings` block (`2,139`
> > bytes of `'_'`, `'-'`, `'0'-'9'`, and `'#'`, plus `855` NUL bytes) are
> > characters that almost never appear as `s[0]`, which pulls the
> > lookup-weighted hit rate back down to 3.9%.
> > 
> > Intuitively, `'\0'` hits once per string (`1 / L`), so `s[0]` wins as
> > long as average string length `L` stays below the ~22-26 byte crossover
> > -- and even on plain non-`-@` DTBs without `/__symbols__`, property
> > names average ~12-14 bytes (`'\0'` still made 1.6x-2.2x more `memchr()`
> > calls than `s[0]` across plain DTB `fdt_sw` builds, `/chosen` fixups,
> > and `.dtbo` overlay application).
> > 
> > > Have you tried an open coded scans instead of calling memchr() and memcmp()?
> > > With an average of 13 bytes per string (26 for your memchr()) the code loop
> > > might be faster.
> > > But beware, gcc is likely to convert the code back to a call to memcmp()
> > > - it certainly does for strlen and memcpy.
> > >
> > > Oh - and if this code runs in kernel the timings will be significantly
> > > different to glibc - it uses some magic avx instructions for strlen()
> > > and memchr() is effectively the same.
> > > The kernel functions are likely to be out of line byte loops.  
> > 
> > Out of curiosity I timed all of those across 200 replays of the same
> > 855-string (11,259-byte) Qualcomm `dt_strings` block with `gcc 15.2` on
> > x86_64 (`gcc -O2` kept the open-coded loops inline and didn't turn them
> > back into `memcmp()`):
> 
> Once you are doing timings, adding a few more doesn't take long.
> 
> > * glibc `memchr` + `!p[slen]` + glibc `memcmp`:
> >   0.25 s (`-O0`), 0.23 s (`-Os`), 0.22 s (`-O2`)
> > * glibc `memchr` + `!p[slen]` + open-coded inner compare:
> >   0.23 s (`-O0`), 0.21 s (`-Os`), 0.21 s (`-O2`)
> 
> So that one is a marginal win.
> 
> > * Fully open-coded (`p[0] == s[0] && !p[slen]` + inner byte loop):
> >   0.91 s (`-O0`), 0.62 s (`-Os`), 0.40 s (`-O2`)
> > * Out-of-line byte-loop `memchr` + `!p[slen]` + byte-loop `memcmp`:
> >   0.86 s (`-O0`), 0.90 s (`-Os`), 0.50 s (`-O2`)
> > * Original per-byte out-of-line byte-loop `memcmp`:
> >   3.31 s (`-O0`), 1.87 s (`-Os`), 1.86 s (`-O2`)
> > 
> > Even with a ~25-byte average stride, glibc's AVX2 `memchr()` handles
> > almost an entire stride in a single 32-byte vector load + compare, so it
> > beats the open-coded scalar loop by ~1.9x at `-O2` (and ~2.7x at `-Os`).
> 
> Using avx2 is 'cheating' ...
> Someone at Intel realised that strlen() does matter and threw some silicon at it.
> They finally did the same for integer divide (but I think AMD did it first)
> and did a divide that generates move than one bit per clock. 
> 
> > Open-coding just the inner compare barely moves the needle since
> > `!p[slen]` already cut `memcmp()` down to 14.3k calls across the 855
> > insertions.
> > 
> > On the kernel / bootloader side, `fdt_find_string_len_()` is only called
> > by `fdt_sw` and `fdt_rw` when adding new property names to `dt_strings`
> > -- normal read-only DTB parsing (`fdt_ro.c`) never calls it. And even
> > with a naive out-of-line byte-loop `memchr()`, `memchr()` + `!p[slen]` +
> > `memcmp()` is still 3.7x faster at `-O2` (`1.86 s -> 0.50 s`) and 2.1x
> > faster at `-Os` (`1.87 s -> 0.90 s`) than the old code, so keeping the
> > simpler `memchr()` + `!p[slen]` + `memcmp()` seems like the right
> > tradeoff.
> 
> Seems reasonable.

Uh, calm down folks.  I'm happy to take easy performance wins, but
this really isn't worth getting deep into the weeds on.

-- 
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 --]

  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 [this message]
2026-11-19  5:32       ` David Gibson
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=av6KvEBGjIbY-2oC@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.