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: 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:38:04 +1100	[thread overview]
Message-ID: <av6LPM4Z94FyWlHN@gractus.seuss> (raw)
In-Reply-To: <CAD=FV=V+2wMhc6OALzbHgn8x9AnWUFCay6sGB7sqKqffGLb7ZQ@mail.gmail.com>

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

On Tue, Nov 17, 2026 at 08:21:26AM -0800, Doug Anderson wrote:
> Hi David,
> 
> On Mon, Nov 16, 2026 at 8:07 PM David Gibson
> <david@gibson.dropbear.id.au> 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]`.

Ah, right, thanks for the analysis.

> (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):

-- 
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 [this message]
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
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=av6LPM4Z94FyWlHN@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=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.