GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — gh-122901: Speed up `str` creation from non-ASCII data with a branch-free `find_max_char()` by ruema · Pull Request #122902 · python/cpython

Conversation

@ruema

@ruema ruema commented Aug 11, 2024 •
edited by bedevere-app Bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

Change to find_max_char to speedup string creation.
See issue #122901.

  • Issue: Improve performance of find_max_char #122901

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@ruema
Improve performance of find_max_char
b0f8321
@bedevere-app bedevere-app Bot mentioned this pull request Aug 11, 2024
Improve performance of find_max_char #122901
Closed
@bedevere-app bedevere-app Bot added the awaiting review label Aug 11, 2024
ruema added 2 commits August 11, 2024 13:17
@ruema
missing ) added
a43c1fc
@ruema
bugfix for unaligned short strings.
d597175
@github-actions

This comment was marked as resolved.

Sign in to view
@github-actions github-actions Bot added the stale Stale PR or inactive for long period of time. label Apr 18, 2026
@StanFromIreland
Merge branch 'main' into feature/speedup_find_max_char
4a8b4d1
@bedevere-app bedevere-app Bot added the type-feature A feature request or enhancement label Oct 30, 2026
@StanFromIreland
Re-write and move the news entry
fe362fe
@StanFromIreland StanFromIreland self-assigned this Oct 30, 2026
@StanFromIreland
Fix alignment prologue to actually align the pointer (+ some PEP 7 nits)
1650b4b
@StanFromIreland StanFromIreland changed the title gh-122901: Improve performance of find_max_char gh-122901: Speed up str creation from non-ASCII data with a branch-free find_max_char() Oct 30, 2026
@StanFromIreland
Little nits
f524f84
@StanFromIreland StanFromIreland added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Oct 30, 2026
@bedevere-bot

This comment was marked as resolved.

Sign in to view
@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Oct 30, 2026
@StanFromIreland

StanFromIreland commented Oct 30, 2026

Copy link
Copy Markdown
Member

I did some benchmarking with the following script:

Details 
import pyperf

LATIN1 = '\xe9'
UCS2 = '\u019f'
UCS4 = '\U0001f600'

def slice_tail(s):
    return s[:-1]

def slice_head(s):
    return s[1:]

def slice_head3(s):
    return s[3:]

def isascii(b):
    return b.isascii()

def decode_latin1(b):
    return b.decode('latin-1')

def split_lines(s):
    return s.split('\n')

CASES = {
    'control: ascii[1001] slice[:-1]': (slice_tail, 'a' * 1001),
    'ucs1[8] slice[:-1]': (slice_tail, 'a' * 7 + LATIN1),
    'ucs1[21] slice[:-1]': (slice_tail, 'a' * 20 + LATIN1),
    'ucs1[1001] slice[:-1]': (slice_tail, 'a' * 1000 + LATIN1),
    'ucs1[1001] slice[1:] (odd ptr)': (slice_head, LATIN1 + 'a' * 1000),
    'ucs1[1001] slice[3:]': (slice_head3, LATIN1 * 3 + 'a' * 998),
    'ucs1[1001] non-ascii body slice[:-1]': (slice_tail, LATIN1 * 1000 + 'a'),
    'ucs1[100001] slice[:-1]': (slice_tail, 'a' * 100000 + LATIN1),
    'ucs1[10_000_001] slice[:-1]': (slice_tail, 'a' * 10_000_000 + LATIN1),
    'ucs2[21] slice[:-1]': (slice_tail, 'a' * 20 + UCS2),
    'ucs2[1002] slice[:-1] (issue)': (slice_tail, 'a' * 1000 + UCS2 * 2),
    'ucs2[1001] latin1 body slice[:-1]': (slice_tail, LATIN1 * 1000 + UCS2),
    'ucs2[1001] slice[1:]': (slice_head, UCS2 + 'a' * 1000),
    'ucs2[1001] wide body slice[:-1]': (slice_tail, UCS2 * 1000 + 'a'),
    'ucs4[21] slice[:-1]': (slice_tail, 'a' * 20 + UCS4),
    'ucs4[1001] slice[:-1]': (slice_tail, 'a' * 1000 + UCS4),
    'ucs4[1001] wide body slice[:-1]': (slice_tail, UCS4 * 1000 + 'a'),
    'bytes[10] isascii': (isascii, b'a' * 10),
    'bytes[1000] isascii': (isascii, b'a' * 1000),
    'bytes[1000] decode latin-1': (decode_latin1, b'a' * 1000),
    'bytes[1000] non-ascii decode latin-1': (decode_latin1, b'\xe9' * 1000),
    'ucs1 200 lines x 51 split': (split_lines, ('abcdefghij' * 5 + LATIN1 + '\n') * 200),
    'ucs1 200 lines x 11 split': (split_lines, ('abcdefghij' + LATIN1 + '\n') * 200),
    'ucs2 200 lines x 51 split': (split_lines, ('abcdefghij' * 5 + UCS2 + '\n') * 200),
}

runner = pyperf.Runner()
for name, (func, arg) in CASES.items():
    runner.bench_func(name, func, arg)

AMD Ryzen 7 8845HS, --enable-optimizations & --with-lto, GCC 15.3.1, Linux-7.1.13-100

control: ascii[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 85.1 ns +- 4.8 ns -> [maxchar-pr] 88.5 ns +- 5.0 ns: 1.04x slower
ucs1[8] slice[:-1]: Mean +- std dev: [maxchar-main] 45.3 ns +- 2.9 ns -> [maxchar-pr] 43.8 ns +- 2.7 ns: 1.03x faster
ucs1[21] slice[:-1]: Mean +- std dev: [maxchar-main] 48.0 ns +- 5.5 ns -> [maxchar-pr] 46.3 ns +- 2.2 ns: 1.04x faster
ucs1[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 120 ns +- 5 ns -> [maxchar-pr] 103 ns +- 6 ns: 1.17x faster
ucs1[1001] slice[1:] (odd ptr): Mean +- std dev: [maxchar-main] 124 ns +- 5 ns -> [maxchar-pr] 108 ns +- 3 ns: 1.14x faster
ucs1[1001] slice[3:]: Mean +- std dev: [maxchar-main] 124 ns +- 4 ns -> [maxchar-pr] 111 ns +- 5 ns: 1.11x faster
ucs1[1001] non-ascii body slice[:-1]: Mean +- std dev: [maxchar-main] 73.6 ns +- 3.9 ns -> [maxchar-pr] 83.4 ns +- 4.3 ns: 1.13x slower
ucs1[100001] slice[:-1]: Mean +- std dev: [maxchar-main] 6.71 us +- 0.22 us -> [maxchar-pr] 4.47 us +- 0.14 us: 1.50x faster
ucs1[10_000_001] slice[:-1]: Mean +- std dev: [maxchar-main] 788 us +- 34 us -> [maxchar-pr] 520 us +- 4 us: 1.52x faster
ucs2[21] slice[:-1]: Mean +- std dev: [maxchar-main] 48.4 ns +- 4.2 ns -> [maxchar-pr] 45.0 ns +- 1.8 ns: 1.08x faster
ucs2[1002] slice[:-1] (issue): Mean +- std dev: [maxchar-main] 195 ns +- 7 ns -> [maxchar-pr] 136 ns +- 2 ns: 1.44x faster
ucs2[1001] latin1 body slice[:-1]: Mean +- std dev: [maxchar-main] 195 ns +- 5 ns -> [maxchar-pr] 137 ns +- 3 ns: 1.42x faster
ucs2[1001] slice[1:]: Mean +- std dev: [maxchar-main] 195 ns +- 5 ns -> [maxchar-pr] 139 ns +- 2 ns: 1.40x faster
ucs4[21] slice[:-1]: Mean +- std dev: [maxchar-main] 50.7 ns +- 2.1 ns -> [maxchar-pr] 49.9 ns +- 1.9 ns: 1.01x faster
ucs4[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 309 ns +- 8 ns -> [maxchar-pr] 331 ns +- 11 ns: 1.07x slower
ucs4[1001] wide body slice[:-1]: Mean +- std dev: [maxchar-main] 101 ns +- 4 ns -> [maxchar-pr] 106 ns +- 2 ns: 1.04x slower
bytes[1000] isascii: Mean +- std dev: [maxchar-main] 61.5 ns +- 2.2 ns -> [maxchar-pr] 84.0 ns +- 2.9 ns: 1.36x slower
bytes[1000] decode latin-1: Mean +- std dev: [maxchar-main] 134 ns +- 4 ns -> [maxchar-pr] 119 ns +- 8 ns: 1.12x faster
bytes[1000] non-ascii decode latin-1: Mean +- std dev: [maxchar-main] 82.7 ns +- 4.6 ns -> [maxchar-pr] 96.6 ns +- 5.6 ns: 1.17x slower
ucs1 200 lines x 51 split: Mean +- std dev: [maxchar-main] 5.69 us +- 0.17 us -> [maxchar-pr] 5.79 us +- 0.09 us: 1.02x slower
ucs1 200 lines x 11 split: Mean +- std dev: [maxchar-main] 3.67 us +- 0.14 us -> [maxchar-pr] 3.45 us +- 0.05 us: 1.06x faster
ucs2 200 lines x 51 split: Mean +- std dev: [maxchar-main] 8.57 us +- 0.17 us -> [maxchar-pr] 7.92 us +- 0.12 us: 1.08x faster

Benchmark hidden because not significant (2): ucs2[1001] wide body slice[:-1], bytes[10] isascii

Geometric mean: 1.08x faster

Intel(R) Core(TM) i5-7500T CPU @ 2.70GHz, release-build, GCC 15.2.1, Linux-6.14.0-63

control: ascii[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 228 ns +- 13 ns -> [maxchar-pr] 220 ns +- 7 ns: 1.04x faster
ucs1[8] slice[:-1]: Mean +- std dev: [maxchar-main] 143 ns +- 1 ns -> [maxchar-pr] 140 ns +- 1 ns: 1.02x faster
ucs1[21] slice[:-1]: Mean +- std dev: [maxchar-main] 142 ns +- 4 ns -> [maxchar-pr] 141 ns +- 1 ns: 1.01x faster
ucs1[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 286 ns +- 2 ns -> [maxchar-pr] 248 ns +- 5 ns: 1.16x faster
ucs1[1001] slice[1:] (odd ptr): Mean +- std dev: [maxchar-main] 295 ns +- 4 ns -> [maxchar-pr] 251 ns +- 4 ns: 1.18x faster
ucs1[1001] slice[3:]: Mean +- std dev: [maxchar-main] 293 ns +- 3 ns -> [maxchar-pr] 249 ns +- 2 ns: 1.18x faster
ucs1[1001] non-ascii body slice[:-1]: Mean +- std dev: [maxchar-main] 227 ns +- 1 ns -> [maxchar-pr] 232 ns +- 2 ns: 1.02x slower
ucs1[100001] slice[:-1]: Mean +- std dev: [maxchar-main] 7.60 us +- 0.14 us -> [maxchar-pr] 4.75 us +- 0.11 us: 1.60x faster
ucs1[10_000_001] slice[:-1]: Mean +- std dev: [maxchar-main] 1.24 ms +- 0.01 ms -> [maxchar-pr] 969 us +- 10 us: 1.28x faster
ucs2[21] slice[:-1]: Mean +- std dev: [maxchar-main] 145 ns +- 1 ns -> [maxchar-pr] 144 ns +- 1 ns: 1.01x faster
ucs2[1002] slice[:-1] (issue): Mean +- std dev: [maxchar-main] 483 ns +- 6 ns -> [maxchar-pr] 272 ns +- 1 ns: 1.77x faster
ucs2[1001] latin1 body slice[:-1]: Mean +- std dev: [maxchar-main] 521 ns +- 2 ns -> [maxchar-pr] 295 ns +- 4 ns: 1.77x faster
ucs2[1001] slice[1:]: Mean +- std dev: [maxchar-main] 526 ns +- 3 ns -> [maxchar-pr] 297 ns +- 2 ns: 1.77x faster
ucs2[1001] wide body slice[:-1]: Mean +- std dev: [maxchar-main] 239 ns +- 2 ns -> [maxchar-pr] 241 ns +- 2 ns: 1.01x slower
ucs4[21] slice[:-1]: Mean +- std dev: [maxchar-main] 148 ns +- 1 ns -> [maxchar-pr] 147 ns +- 1 ns: 1.01x faster
ucs4[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 808 ns +- 6 ns -> [maxchar-pr] 475 ns +- 4 ns: 1.70x faster
bytes[10] isascii: Mean +- std dev: [maxchar-main] 92.9 ns +- 0.5 ns -> [maxchar-pr] 92.7 ns +- 0.4 ns: 1.00x faster
bytes[1000] isascii: Mean +- std dev: [maxchar-main] 151 ns +- 2 ns -> [maxchar-pr] 108 ns +- 1 ns: 1.39x faster
bytes[1000] decode latin-1: Mean +- std dev: [maxchar-main] 308 ns +- 2 ns -> [maxchar-pr] 267 ns +- 2 ns: 1.16x faster
bytes[1000] non-ascii decode latin-1: Mean +- std dev: [maxchar-main] 256 ns +- 8 ns -> [maxchar-pr] 250 ns +- 2 ns: 1.02x faster
ucs1 200 lines x 51 split: Mean +- std dev: [maxchar-main] 15.0 us +- 0.2 us -> [maxchar-pr] 12.1 us +- 0.6 us: 1.24x faster
ucs1 200 lines x 11 split: Mean +- std dev: [maxchar-main] 9.74 us +- 0.21 us -> [maxchar-pr] 8.39 us +- 0.18 us: 1.16x faster
ucs2 200 lines x 51 split: Mean +- std dev: [maxchar-main] 17.2 us +- 1.2 us -> [maxchar-pr] 12.1 us +- 0.7 us: 1.43x faster

Benchmark hidden because not significant (1): ucs4[1001] wide body slice[:-1]

Geometric mean: 1.22x faster

The results are quite compiler and build specific. Disassembling the PGO+LTO binary shows that GCC compiled the 32-word loop as a plain scalar loop rather than vectorising it, presumably because the loop is not hot enough in the PGO training run, and in that case the single accumulator becomes a serial dependency chain, which explains the slowdowns on bytes.isascii() and the UCS4 slice. I'll try to adjust the loop so it stays fast whether or not it gets vectorised, without making this too complex...
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
Use four accumulators and a 16-word block so the loop is fast when no…
1daa7ee 
…t vectorized
@StanFromIreland

StanFromIreland commented Oct 30, 2026

Copy link
Copy Markdown
Member

So, after some testing I pushed a little change to use four accumulators and a 16-word block so the loop is faster even when it's not vectorised. Benchmarking again, some more promising results:

AMD Ryzen 7 8845HS, --enable-optimizations & --with-lto, GCC 15.3.1, Linux-7.1.13-100

control: ascii[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 85.1 ns +- 4.8 ns -> [maxchar-pr-4acc] 107 ns +- 4 ns: 1.26x slower
ucs1[8] slice[:-1]: Mean +- std dev: [maxchar-main] 45.3 ns +- 2.9 ns -> [maxchar-pr-4acc] 44.4 ns +- 2.8 ns: 1.02x faster
ucs1[21] slice[:-1]: Mean +- std dev: [maxchar-main] 48.0 ns +- 5.5 ns -> [maxchar-pr-4acc] 46.3 ns +- 1.9 ns: 1.04x faster
ucs1[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 120 ns +- 5 ns -> [maxchar-pr-4acc] 84.2 ns +- 3.0 ns: 1.42x faster
ucs1[1001] slice[1:] (odd ptr): Mean +- std dev: [maxchar-main] 124 ns +- 5 ns -> [maxchar-pr-4acc] 88.0 ns +- 2.1 ns: 1.41x faster
ucs1[1001] slice[3:]: Mean +- std dev: [maxchar-main] 124 ns +- 4 ns -> [maxchar-pr-4acc] 91.4 ns +- 4.4 ns: 1.36x faster
ucs1[100001] slice[:-1]: Mean +- std dev: [maxchar-main] 6.71 us +- 0.22 us -> [maxchar-pr-4acc] 2.60 us +- 0.16 us: 2.59x faster
ucs1[10_000_001] slice[:-1]: Mean +- std dev: [maxchar-main] 788 us +- 34 us -> [maxchar-pr-4acc] 319 us +- 39 us: 2.47x faster
ucs2[21] slice[:-1]: Mean +- std dev: [maxchar-main] 48.4 ns +- 4.2 ns -> [maxchar-pr-4acc] 47.2 ns +- 2.9 ns: 1.03x faster
ucs2[1002] slice[:-1] (issue): Mean +- std dev: [maxchar-main] 195 ns +- 7 ns -> [maxchar-pr-4acc] 114 ns +- 4 ns: 1.72x faster
ucs2[1001] latin1 body slice[:-1]: Mean +- std dev: [maxchar-main] 195 ns +- 5 ns -> [maxchar-pr-4acc] 115 ns +- 3 ns: 1.70x faster
ucs2[1001] slice[1:]: Mean +- std dev: [maxchar-main] 195 ns +- 5 ns -> [maxchar-pr-4acc] 117 ns +- 4 ns: 1.67x faster
ucs2[1001] wide body slice[:-1]: Mean +- std dev: [maxchar-main] 91.5 ns +- 8.0 ns -> [maxchar-pr-4acc] 87.2 ns +- 4.8 ns: 1.05x faster
ucs4[21] slice[:-1]: Mean +- std dev: [maxchar-main] 50.7 ns +- 2.1 ns -> [maxchar-pr-4acc] 48.2 ns +- 3.0 ns: 1.05x faster
ucs4[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 309 ns +- 8 ns -> [maxchar-pr-4acc] 256 ns +- 9 ns: 1.21x faster
ucs4[1001] wide body slice[:-1]: Mean +- std dev: [maxchar-main] 101 ns +- 4 ns -> [maxchar-pr-4acc] 95.1 ns +- 2.6 ns: 1.07x faster
bytes[10] isascii: Mean +- std dev: [maxchar-main] 36.4 ns +- 1.8 ns -> [maxchar-pr-4acc] 35.9 ns +- 1.4 ns: 1.01x faster
bytes[1000] isascii: Mean +- std dev: [maxchar-main] 61.5 ns +- 2.2 ns -> [maxchar-pr-4acc] 48.6 ns +- 1.7 ns: 1.27x faster
bytes[1000] decode latin-1: Mean +- std dev: [maxchar-main] 134 ns +- 4 ns -> [maxchar-pr-4acc] 91.4 ns +- 2.5 ns: 1.46x faster
bytes[1000] non-ascii decode latin-1: Mean +- std dev: [maxchar-main] 82.7 ns +- 4.6 ns -> [maxchar-pr-4acc] 80.7 ns +- 2.0 ns: 1.02x faster
ucs1 200 lines x 51 split: Mean +- std dev: [maxchar-main] 5.69 us +- 0.17 us -> [maxchar-pr-4acc] 5.61 us +- 0.15 us: 1.01x faster
ucs1 200 lines x 11 split: Mean +- std dev: [maxchar-main] 3.67 us +- 0.14 us -> [maxchar-pr-4acc] 3.39 us +- 0.11 us: 1.08x faster
ucs2 200 lines x 51 split: Mean +- std dev: [maxchar-main] 8.57 us +- 0.17 us -> [maxchar-pr-4acc] 7.39 us +- 0.16 us: 1.16x faster

Benchmark hidden because not significant (1): ucs1[1001] non-ascii body slice[:-1]

Geometric mean: 1.26x faster

Intel(R) Core(TM) i5-7500T CPU @ 2.70GHz, release-build, GCC 15.2.1, Linux-6.14.0-63

control: ascii[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 228 ns +- 13 ns -> [maxchar-pr-4acc] 220 ns +- 8 ns: 1.04x faster
ucs1[8] slice[:-1]: Mean +- std dev: [maxchar-main] 143 ns +- 1 ns -> [maxchar-pr-4acc] 139 ns +- 2 ns: 1.03x faster
ucs1[21] slice[:-1]: Mean +- std dev: [maxchar-main] 142 ns +- 4 ns -> [maxchar-pr-4acc] 141 ns +- 1 ns: 1.01x faster
ucs1[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 286 ns +- 2 ns -> [maxchar-pr-4acc] 251 ns +- 2 ns: 1.14x faster
ucs1[1001] slice[1:] (odd ptr): Mean +- std dev: [maxchar-main] 295 ns +- 4 ns -> [maxchar-pr-4acc] 253 ns +- 2 ns: 1.17x faster
ucs1[1001] slice[3:]: Mean +- std dev: [maxchar-main] 293 ns +- 3 ns -> [maxchar-pr-4acc] 252 ns +- 4 ns: 1.16x faster
ucs1[1001] non-ascii body slice[:-1]: Mean +- std dev: [maxchar-main] 227 ns +- 1 ns -> [maxchar-pr-4acc] 230 ns +- 2 ns: 1.02x slower
ucs1[100001] slice[:-1]: Mean +- std dev: [maxchar-main] 7.60 us +- 0.14 us -> [maxchar-pr-4acc] 6.37 us +- 0.09 us: 1.19x faster
ucs1[10_000_001] slice[:-1]: Mean +- std dev: [maxchar-main] 1.24 ms +- 0.01 ms -> [maxchar-pr-4acc] 1.09 ms +- 0.01 ms: 1.13x faster
ucs2[21] slice[:-1]: Mean +- std dev: [maxchar-main] 145 ns +- 1 ns -> [maxchar-pr-4acc] 145 ns +- 1 ns: 1.00x faster
ucs2[1002] slice[:-1] (issue): Mean +- std dev: [maxchar-main] 483 ns +- 6 ns -> [maxchar-pr-4acc] 296 ns +- 6 ns: 1.63x faster
ucs2[1001] latin1 body slice[:-1]: Mean +- std dev: [maxchar-main] 521 ns +- 2 ns -> [maxchar-pr-4acc] 336 ns +- 4 ns: 1.55x faster
ucs2[1001] slice[1:]: Mean +- std dev: [maxchar-main] 526 ns +- 3 ns -> [maxchar-pr-4acc] 338 ns +- 4 ns: 1.56x faster
ucs4[21] slice[:-1]: Mean +- std dev: [maxchar-main] 148 ns +- 1 ns -> [maxchar-pr-4acc] 147 ns +- 1 ns: 1.01x faster
ucs4[1001] slice[:-1]: Mean +- std dev: [maxchar-main] 808 ns +- 6 ns -> [maxchar-pr-4acc] 582 ns +- 31 ns: 1.39x faster
ucs4[1001] wide body slice[:-1]: Mean +- std dev: [maxchar-main] 257 ns +- 6 ns -> [maxchar-pr-4acc] 259 ns +- 8 ns: 1.01x slower
bytes[10] isascii: Mean +- std dev: [maxchar-main] 92.9 ns +- 0.5 ns -> [maxchar-pr-4acc] 95.4 ns +- 0.4 ns: 1.03x slower
bytes[1000] isascii: Mean +- std dev: [maxchar-main] 151 ns +- 2 ns -> [maxchar-pr-4acc] 119 ns +- 1 ns: 1.27x faster
bytes[1000] decode latin-1: Mean +- std dev: [maxchar-main] 308 ns +- 2 ns -> [maxchar-pr-4acc] 270 ns +- 4 ns: 1.14x faster
bytes[1000] non-ascii decode latin-1: Mean +- std dev: [maxchar-main] 256 ns +- 8 ns -> [maxchar-pr-4acc] 251 ns +- 8 ns: 1.02x faster
ucs1 200 lines x 51 split: Mean +- std dev: [maxchar-main] 15.0 us +- 0.2 us -> [maxchar-pr-4acc] 14.5 us +- 0.4 us: 1.04x faster
ucs1 200 lines x 11 split: Mean +- std dev: [maxchar-main] 9.74 us +- 0.21 us -> [maxchar-pr-4acc] 8.89 us +- 0.16 us: 1.10x faster
ucs2 200 lines x 51 split: Mean +- std dev: [maxchar-main] 17.2 us +- 1.2 us -> [maxchar-pr-4acc] 14.8 us +- 0.2 us: 1.16x faster

Benchmark hidden because not significant (1): ucs2[1001] wide body slice[:-1]

Geometric mean: 1.14x faster

The slowdown in the control in the PGO+LTO build is, as far as I can tell, just a build loosing in the PGO lottery. As expected in the release build, there should be no difference other than noise.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
StanFromIreland requested a review from eendebakpt October 30, 2026 19:24
@StanFromIreland StanFromIreland added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Oct 30, 2026
@bedevere-bot

bedevere-bot commented Oct 30, 2026

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @StanFromIreland for commit 1daa7ee 🤖

Results will be shown at:

https://buildbot.python.org/all/#/grid?branch=refs%2Fpull%2F122902%2Fmerge

If you want to schedule another build, you need to add the 🔨 test-with-buildbots label again.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Oct 30, 2026
@StanFromIreland

StanFromIreland commented Oct 30, 2026

Copy link
Copy Markdown
Member

I think I'm pretty happy with this, @vstinner, @eendebakpt and @picnixz what do you think?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@eendebakpt

eendebakpt commented Oct 30, 2026 •
edited by StanFromIreland
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

The general idea is good, but there are quite some variations possible. The latest commit (small workaround for the compiler not vectorizing) is not great.

I tried prompting Claude to come up with simpler approaches. One result is here: pr122902..find-max-char-reduce. Less code, easier to read (imo) and a bit faster (on my noisy system).

Benchmark details
Benchmark main PR 122902 find-max-char-reduce
control: ascii[1001] slice[:-1] 194 ns not significant 212 ns: 1.09x slower
ucs1[8] slice[:-1] 160 ns 170 ns: 1.06x slower not significant
ucs1[21] slice[:-1] 160 ns not significant 177 ns: 1.10x slower
ucs1[1001] slice[:-1] 239 ns 258 ns: 1.08x slower not significant
ucs1[1001] slice[1:] (odd ptr) not significant not significant
ucs1[1001] slice[3:] not significant not significant
ucs1[1001] non-ascii body slice[:-1] 189 ns 211 ns: 1.12x slower 200 ns: 1.06x slower
ucs1[100001] slice[:-1] 4.98 us 4.57 us: 1.09x faster 4.01 us: 1.24x faster
ucs1[10_000_001] slice[:-1] 1.98 ms 2.46 ms: 1.24x slower not significant
ucs2[21] slice[:-1] 150 ns 157 ns: 1.04x slower not significant
ucs2[1002] slice[:-1] (issue) 405 ns 256 ns: 1.58x faster 251 ns: 1.62x faster
ucs2[1001] latin1 body slice[:-1] 566 ns 430 ns: 1.32x faster 438 ns: 1.29x faster
ucs2[1001] slice[1:] 627 ns 456 ns: 1.38x faster 445 ns: 1.41x faster
ucs2[1001] wide body slice[:-1] not significant not significant
ucs4[21] slice[:-1] 156 ns 168 ns: 1.07x slower not significant
ucs4[1001] slice[:-1] 528 ns 482 ns: 1.09x faster 484 ns: 1.09x faster
ucs4[1001] wide body slice[:-1] 216 ns 229 ns: 1.06x slower 223 ns: 1.03x slower
bytes[10] isascii not significant not significant
bytes[1000] isascii 173 ns not significant 138 ns: 1.25x faster
bytes[1000] decode latin-1 298 ns 326 ns: 1.09x slower 272 ns: 1.10x faster
bytes[1000] non-ascii decode latin-1 286 ns 258 ns: 1.11x faster 246 ns: 1.16x faster
ucs1 200 lines x 51 split 10.2 us 9.19 us: 1.10x faster 9.56 us: 1.06x faster
ucs1 200 lines x 11 split 7.17 us 6.34 us: 1.13x faster 6.62 us: 1.08x faster
ucs2 200 lines x 51 split 11.6 us 9.11 us: 1.27x faster 9.14 us: 1.27x faster
Geometric mean (ref) 1.04x faster 1.08x faster

Edited by Stan to fix table not rendering.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland

StanFromIreland commented Oct 30, 2026 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

Hmm, what build were the benchmarks run on? I'll test it.

What I'm curious is what happens if the vectorizer does not run?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland

StanFromIreland commented Oct 30, 2026 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

Benchmarking your branch @eendebakpt, as I feared, on an LTO+PGO build:

Benchmark maxchar-main maxchar-pr-4acc maxchar-pieter
control: ascii[1001] slice[:-1] 85.1 ns 107 ns: 1.26x slower 91.4 ns: 1.07x slower
ucs1[8] slice[:-1] 45.3 ns 44.4 ns: 1.02x faster 44.5 ns: 1.02x faster
ucs1[21] slice[:-1] 48.0 ns 46.3 ns: 1.04x faster not significant
ucs1[1001] slice[:-1] 120 ns 84.2 ns: 1.42x faster 108 ns: 1.11x faster
ucs1[1001] slice[1:] (odd ptr) 124 ns 88.0 ns: 1.41x faster 112 ns: 1.10x faster
ucs1[1001] slice[3:] 124 ns 91.4 ns: 1.36x faster 112 ns: 1.11x faster
ucs1[1001] non-ascii body slice[:-1] 73.6 ns not significant 79.4 ns: 1.08x slower
ucs1[100001] slice[:-1] 6.71 us 2.60 us: 2.59x faster 4.84 us: 1.39x faster
ucs1[10_000_001] slice[:-1] 788 us 319 us: 2.47x faster 585 us: 1.35x faster
ucs2[21] slice[:-1] 48.4 ns 47.2 ns: 1.03x faster not significant
ucs2[1002] slice[:-1] (issue) 195 ns 114 ns: 1.72x faster 112 ns: 1.74x faster
ucs2[1001] latin1 body slice[:-1] 195 ns 115 ns: 1.70x faster 115 ns: 1.70x faster
ucs2[1001] slice[1:] 195 ns 117 ns: 1.67x faster 119 ns: 1.64x faster
ucs2[1001] wide body slice[:-1] 91.5 ns 87.2 ns: 1.05x faster 88.2 ns: 1.04x faster
ucs4[21] slice[:-1] 50.7 ns 48.2 ns: 1.05x faster 52.6 ns: 1.04x slower
ucs4[1001] slice[:-1] 309 ns 256 ns: 1.21x faster 270 ns: 1.15x faster
ucs4[1001] wide body slice[:-1] 101 ns 95.1 ns: 1.07x faster not significant
bytes[10] isascii 36.4 ns 35.9 ns: 1.01x faster 38.5 ns: 1.06x slower
bytes[1000] isascii 61.5 ns 48.6 ns: 1.27x faster 269 ns: 4.37x slower
bytes[1000] decode latin-1 134 ns 91.4 ns: 1.46x faster 117 ns: 1.14x faster
bytes[1000] non-ascii decode latin-1 82.7 ns 80.7 ns: 1.02x faster 91.3 ns: 1.10x slower
ucs1 200 lines x 51 split 5.69 us 5.61 us: 1.01x faster 5.62 us: 1.01x faster
ucs1 200 lines x 11 split 3.67 us 3.39 us: 1.08x faster 3.41 us: 1.08x faster
ucs2 200 lines x 51 split 8.57 us 7.39 us: 1.16x faster 9.60 us: 1.12x slower
Geometric mean (ref) 1.26x faster 1.04x faster

And indeed, it was not vectorised, looking at the disassembly:

0000000000621710 <stringlib_find_max_char.lto_priv.0>:
  621710:	xor    %eax,%eax
  621712:	mov    %rsi,%rdx
  621715:	sub    %rdi,%rdx
  621718:	cmp    $0x3f,%rdx
  62171c:	jle    621727 <stringlib_find_max_char.lto_priv.0+0x17>
  62171e:	jmp    62173c <stringlib_find_max_char.lto_priv.0+0x2c>
  621720:	add    $0x1,%rdi
  621724:	or     -0x1(%rdi),%al
  621727:	cmp    %rsi,%rdi
  62172a:	jb     621720 <stringlib_find_max_char.lto_priv.0+0x10>
  62172c:	test   %al,%al
  62172e:	mov    $0xff,%edx
  621733:	mov    $0x7f,%eax
  621738:	cmovs  %edx,%eax
  62173b:	ret
  62173c:	xor    %edx,%edx
  62173e:	xor    %ecx,%ecx
  621740:	or     (%rdi,%rdx,1),%cl
  621743:	add    $0x1,%rdx
  621747:	cmp    $0x40,%rdx
  62174b:	jne    621740 <stringlib_find_max_char.lto_priv.0+0x30>
  62174d:	or     %cl,%al
  62174f:	js     621757 <stringlib_find_max_char.lto_priv.0+0x47>
  621751:	add    $0x40,%rdi
  621755:	jmp    621712 <stringlib_find_max_char.lto_priv.0+0x2>
  621757:	mov    $0xff,%eax
  62175c:	ret
  62175d:	nopl   (%rax)
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@eendebakpt

eendebakpt commented Oct 30, 2026

Copy link
Copy Markdown
Contributor

Hmm, what build were the benchmarks run on? I'll test it.

Windows, MSVC. One thing here is that in the PGO run the path for size > 64 (my branch) or >SIZEOF_SIZE_T * 16 (this PR) is not exercised in find_max_char. Could you add a case to the tests in a PGO run and see whether that impacts the vectorization?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland

StanFromIreland commented Oct 30, 2026

Copy link
Copy Markdown
Member

Could you add a case to the tests in a PGO run and see whether that impacts the vectorization?

I can try, but I'd really rather not rely on such finicky things. We don't want to slow down platforms that don't vectorize for whatever reason, or strictly rely on the tests (distributors may use different sets for example).
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
eendebakpt
eendebakpt reviewed Oct 31, 2026
View reviewed changes
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
@github-actions github-actions Bot removed the stale Stale PR or inactive for long period of time. label Nov 3, 2026
@StanFromIreland

StanFromIreland commented Nov 3, 2026

Copy link
Copy Markdown
Member

I'll merge in a few days if there are no more comments.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@vstinner

vstinner commented Nov 5, 2026

Copy link
Copy Markdown
Member

There are a few small cases where the approaches here are a bit slower. E.g. with b = b'\xe9' + b'a'*999 a call to b.isascii(). Minor compared to the gains for larger strings though.

I'm a bit concerned by the overhead of this change when first bytes/characters take this code path:

        if (value & MASK_MAX_CHAR) {
            return MAX_CHAR;
        }

Currently, we load one size_t (8 bytes). With this change, 16 size_t are loaded (128 bytes). The change may make this case slower. My question is: how much slower is it?

'ucs1[8] slice[:-1]': (slice_tail, 'a' * 7 + LATIN1),
'ucs1[21] slice[:-1]': (slice_tail, 'a' * 20 + LATIN1),
'ucs1[1001] slice[:-1]': (slice_tail, 'a' * 1000 + LATIN1),

The benchmark seems to only measure cases when the fast-path is taken (when it's expected to be faster).

I would be interested by a benchmark on the worst case. For example, (slice_tail, LATIN1 + 'a' * 1000 + LATIN1).
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland

StanFromIreland commented Nov 6, 2026

Copy link
Copy Markdown
Member

That case is covered by the benchmark already, just under a different name. The ucs1[1001] non-ascii body slice[:-1] row is '\xe9' * 1000 + 'a', so the very first word has the mask bit set and the function returns at the first check, like it would for LATIN1 + 'a' * 1000 + LATIN1. The unread bytes after the first word don't matter for the timing. There are three more rows with a similar shape, bytes[1000] non-ascii decode latin-1 (b'\xe9' * 1000), ucs2[1001] wide body (first char > 0xff) and ucs4[1001] wide body (first char > 0xffff). The results for those rows, main vs. this PR:

PGO+LTO release build
ucs1[1001] non-ascii body slice[:-1] not significant 1.02x slower
bytes[1000] non-ascii decode latin-1 1.02x faster 1.02x faster
ucs2[1001] wide body slice[:-1] 1.05x faster not significant
ucs4[1001] wide body slice[:-1] 1.07x faster not significant

So the extra reads are within noise in both directions. That matches what I would expect, the extra work is 15 word loads (8 SSE loads when vectorized) from data that is already in L1, which is a few nanoseconds against the ~45 ns for the slice operation. It is also why the block was reduced from the original 32 words to 16.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
StanFromIreland requested a review from vstinner November 6, 2026 15:56
vstinner
vstinner reviewed Nov 6, 2026
View reviewed changes

@vstinner vstinner left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

On Intel, memcpy(size_t) may be cheap on unaligned memory addresses, but on other architectures it might be more expensive. Would it be interesting to replace memcpy() with a size_t* pointer (and do the boring work to get an aligned pointer)?

For example, utf8_decode() checks _Py_IS_ALIGNED(s, ALIGNOF_SIZE_T) to get a const size_t * pointer and avoid memcpy().

Maybe switching to size_t* pointer can be investigated in a follow-up PR.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland @vstinner
Style nit.
0d6bed1 
Co-authored-by: Victor Stinner <[email protected]>
@StanFromIreland
StanFromIreland requested a review from vstinner November 6, 2026 20:23
@StanFromIreland
Align the pointer first and use plain word loads in the loops
03dd976
@StanFromIreland

StanFromIreland commented Nov 6, 2026

Copy link
Copy Markdown
Member

On Intel, memcpy(size_t) may be cheap on unaligned memory addresses, but on other architectures it might be more expensive. Would it be interesting to replace memcpy() with a size_t* pointer (and do the boring work to get an aligned pointer)?

For example, utf8_decode() checks _Py_IS_ALIGNED(s, ALIGNOF_SIZE_T) to get a const size_t * pointer and avoid memcpy().

Maybe switching to size_t* pointer can be investigated in a follow-up PR.

The PR originally had exactly that, but I switched to memcpy() because it removed the prologue and on x86-64 it compiles to the same single load. But, testing now in Compiler Explorer, while that's true for x86-64 (GCC, Clang, MSVC), AArch64 and s390x, on RISC-V it becomes eight byte loads plus stores and a reload, and on SPARC64 it becomes a memcpy call per word, both of which would be slower than the current code. So I reverted that, the pointer is aligned first and the loops use size_t * loads again.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
Read the short tail from the buffer start
ce16f35
vstinner
vstinner reviewed Nov 7, 2026
View reviewed changes

@vstinner vstinner left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I wrote a variant to address my suggestions: https://gist.github.com/vstinner/b47d2d3340607510a3d46b26955d83de

I wrote a stress test to check that find_max_char() works as expected:

import _testcapi
unicode_kind = _testcapi.unicode_kind

def kind(s):
    if s.isascii():
        return 0
    else:
        return unicode_kind(s)

for before in range(1, 10+1):
    for after in range(1, 10+1):
        for repeat in (1, 10, 100, 200, 1000):
            for ch, next_ch, expected in (
                ('x', '\xe9', 1),
                ('\xe9', '\u20ac', 2),
                ('\u20ac', '\U0010ffff', 4),
            ):
                # test different memory alignments
                for start in range(16):
                    s = '#' * start + next_ch * before + ch * repeat + next_ch * after
                    assert kind(s[start + before:]) == expected
                    assert kind(s[start:-after]) == expected
                    assert kind(s[start + before:-after]) == kind(ch)

                    s = '#' * start + ch * repeat + next_ch + ch * repeat
                    assert kind(s[start:]) == expected

print("All good.")

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
@vstinner vstinner mentioned this pull request Nov 7, 2026
gh-161145: Test more bytes simultaneously in find_first_nonascii #161147
Draft
@StanFromIreland @vstinner
Apply Victor's suggestions
864423a 
Co-Authored-By: Victor Stinner <[email protected]>
@StanFromIreland

StanFromIreland commented Nov 7, 2026

Copy link
Copy Markdown
Member

Thanks Victor, I applied your suggestions. A little change from your gist is that the tail's if (n >= 4) is no longer inside #if SIZEOF_SIZE_T == 8, since the following else if would otherwise be a dangling else on 32-bit builds with 1- or 2-byte characters.
vstinner reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
StanFromIreland requested a review from vstinner November 7, 2026 19:42
@vstinner

vstinner commented Nov 7, 2026 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

I checked ucs1lib_find_max_char() assembly code on Linux x86-64: Fedora 45 with GCC 16.2.1. Python built with ./configure: gcc -O3.

The core of the while (p + SIZEOF_SIZE_T * 16 <= _end) { loop uses 16 or instructions on 64-bit:

   0x0000000000783078 <+120>:	mov    rax,QWORD PTR [rdx-0x80]
   0x000000000078307c <+124>:	or     rax,QWORD PTR [rdx-0x78]
   0x0000000000783080 <+128>:	or     rax,rdi
   0x0000000000783083 <+131>:	or     rax,QWORD PTR [rdx-0x70]
   0x0000000000783087 <+135>:	or     rax,QWORD PTR [rdx-0x68]
   0x000000000078308b <+139>:	or     rax,QWORD PTR [rdx-0x60]
   0x000000000078308f <+143>:	or     rax,QWORD PTR [rdx-0x58]
   0x0000000000783093 <+147>:	or     rax,QWORD PTR [rdx-0x50]
   0x0000000000783097 <+151>:	or     rax,QWORD PTR [rdx-0x48]
   0x000000000078309b <+155>:	or     rax,QWORD PTR [rdx-0x40]
   0x000000000078309f <+159>:	or     rax,QWORD PTR [rdx-0x38]
   0x00000000007830a3 <+163>:	or     rax,QWORD PTR [rdx-0x30]
   0x00000000007830a7 <+167>:	or     rax,QWORD PTR [rdx-0x28]
   0x00000000007830ab <+171>:	or     rax,QWORD PTR [rdx-0x20]
   0x00000000007830af <+175>:	or     rax,QWORD PTR [rdx-0x18]
   0x00000000007830b3 <+179>:	or     rax,QWORD PTR [rdx-0x10]
   0x00000000007830b7 <+183>:	or     rax,QWORD PTR [rdx-0x8]

   0x00000000007830bb <+187>:	mov    rdi,rax
   0x00000000007830be <+190>:	test   rax,rcx
   0x00000000007830c1 <+193>:	jne    0x7831b8 <ucs1lib_find_max_char+440>

With a small change, the loop uses 8 por instructions on 128-bits + 8 movdqu (128-bit):

   0x000000000078309e <+158>:	movdqu xmm0,XMMWORD PTR [rdx-0x80]
   0x00000000007830a3 <+163>:	movdqu xmm2,XMMWORD PTR [rdx-0x70]
   0x00000000007830a8 <+168>:	movdqu xmm1,XMMWORD PTR [rdx-0x50]
   0x00000000007830ad <+173>:	movdqu xmm5,XMMWORD PTR [rdx-0x60]
   0x00000000007830b2 <+178>:	movdqu xmm3,XMMWORD PTR [rdx-0x40]
   0x00000000007830b7 <+183>:	movdqu xmm6,XMMWORD PTR [rdx-0x30]
   0x00000000007830bc <+188>:	por    xmm0,xmm2
   0x00000000007830c0 <+192>:	movdqu xmm4,XMMWORD PTR [rdx-0x20]
   0x00000000007830c5 <+197>:	movdqu xmm7,XMMWORD PTR [rdx-0x10]
   0x00000000007830ca <+202>:	por    xmm1,xmm5
   0x00000000007830ce <+206>:	por    xmm0,xmm3
   0x00000000007830d2 <+210>:	por    xmm1,xmm6
   0x00000000007830d6 <+214>:	por    xmm1,xmm7
   0x00000000007830da <+218>:	por    xmm0,xmm4
   0x00000000007830de <+222>:	por    xmm0,xmm1

   0x00000000007830e2 <+226>:	movdqa xmm1,xmm0
   0x00000000007830e6 <+230>:	psrldq xmm1,0x8
   0x00000000007830eb <+235>:	por    xmm0,xmm1
   0x00000000007830ef <+239>:	movq   rax,xmm0

   0x00000000007830f4 <+244>:	test   rax,r8
   0x00000000007830f7 <+247>:	je     0x783088 <ucs1lib_find_max_char+136>

The small change: use size_t local_value = 0; in the loop, rather than directly updating the "global" value variable.

diff --git a/Objects/stringlib/find_max_char.h b/Objects/stringlib/find_max_char.h
index 9f818b6abc7..8f8f750206e 100644
--- a/Objects/stringlib/find_max_char.h
+++ b/Objects/stringlib/find_max_char.h
@@ -84,12 +84,16 @@ STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
                 p += sizeof(uint32_t);
             }
 #endif
+            if (value & MASK_MAX_CHAR) {
+                return MAX_CHAR;
+            }
             assert(_Py_IS_ALIGNED(p, ALIGNOF_SIZE_T));
         }
 
         while (p + SIZEOF_SIZE_T * 16 <= _end) {
             /* Four independent accumulators so the loop does not serialize on
                one register when the compiler does not vectorize it. */
+            size_t local_value = 0;
             size_t v0 = 0, v1 = 0, v2 = 0, v3 = 0;
             for (int i = 0; i < 16 * SIZEOF_SIZE_T; i += 4 * SIZEOF_SIZE_T) {
                 const size_t *w = (const size_t *)(p + i);
@@ -98,11 +102,12 @@ STRINGLIB(find_max_char)(const STRINGLIB_CHAR *begin, const STRINGLIB_CHAR *end)
                 v2 |= w[2];
                 v3 |= w[3];
             }
-            value |= v0 | v1 | v2 | v3;
-            if (value & MASK_MAX_CHAR) {
+            local_value |= v0 | v1 | v2 | v3;
+            if (local_value & MASK_MAX_CHAR) {
                 return MAX_CHAR;
             }
             p += SIZEOF_SIZE_T * 16;
+            value |= local_value;
         }
 
         for (; p + SIZEOF_SIZE_T <= _end; p += SIZEOF_SIZE_T) {
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@vstinner

vstinner commented Nov 7, 2026

Copy link
Copy Markdown
Member

I also checked clang, still with my size_t local_value = 0; change: also 8 movdqu (128-bit) with 8 por (128-bit), but a little bit different code to process the xmmN vectors

   0x0000000000727efc <+172>:	movdqu xmm0,XMMWORD PTR [rax+0x50]
   0x0000000000727f01 <+177>:	movdqu xmm1,XMMWORD PTR [rax+0x70]
   0x0000000000727f06 <+182>:	movdqu xmm2,XMMWORD PTR [rax+0x40]
   0x0000000000727f0b <+187>:	movdqu xmm3,XMMWORD PTR [rax+0x60]
   0x0000000000727f10 <+192>:	movdqu xmm4,XMMWORD PTR [rax]
   0x0000000000727f14 <+196>:	por    xmm4,xmm2
   0x0000000000727f18 <+200>:	movdqu xmm2,XMMWORD PTR [rax+0x10]
   0x0000000000727f1d <+205>:	por    xmm2,xmm0
   0x0000000000727f21 <+209>:	movdqu xmm0,XMMWORD PTR [rax+0x20]
   0x0000000000727f26 <+214>:	por    xmm0,xmm3
   0x0000000000727f2a <+218>:	por    xmm0,xmm4
   0x0000000000727f2e <+222>:	movdqu xmm3,XMMWORD PTR [rax+0x30]
   0x0000000000727f33 <+227>:	por    xmm3,xmm1
   0x0000000000727f37 <+231>:	por    xmm3,xmm2
   0x0000000000727f3b <+235>:	por    xmm3,xmm0

   0x0000000000727f3f <+239>:	pshufd xmm0,xmm3,0xee
   0x0000000000727f44 <+244>:	por    xmm0,xmm3

   0x0000000000727f48 <+248>:	movq   r8,xmm0
   0x0000000000727f4d <+253>:	or     rdx,r8
   0x0000000000727f50 <+256>:	mov    rax,rdi

   0x0000000000727f53 <+259>:	test   r8,rcx
   0x0000000000727f56 <+262>:	je     0x727ef0 <ucs1lib_find_max_char+160>
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
Test blocks before folding into the acc
ca3ce0c
@StanFromIreland

StanFromIreland commented Nov 8, 2026

Copy link
Copy Markdown
Member

Aargh, I missed that it regressed. Thank you Victor! I applied your patch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@vstinner

vstinner commented Nov 8, 2026

Copy link
Copy Markdown
Member

Multiple Windows jobs failed with Download error: it should be related to https://www.githubstatus.com/incidents/pyynvrm1vskw (and unrelated to this change).
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@vstinner

vstinner commented Nov 8, 2026

Copy link
Copy Markdown
Member

I checked ucs1lib_find_max_char() in the latest version of the PR on Fedora 45 (GCC 16.2.1) with gcc -O3 (no PGO, no LTO).

The core of the function while (p + SIZEOF_SIZE_T * 16 <= _end) { uses 8 movdqu (128-bit) + 8 por (128-bit):

   0x00000000007830de <+158>:	movdqu xmm0,XMMWORD PTR [rdx-0x80]
   0x00000000007830e3 <+163>:	movdqu xmm2,XMMWORD PTR [rdx-0x70]
   0x00000000007830e8 <+168>:	movdqu xmm1,XMMWORD PTR [rdx-0x50]
   0x00000000007830ed <+173>:	movdqu xmm5,XMMWORD PTR [rdx-0x60]
   0x00000000007830f2 <+178>:	movdqu xmm3,XMMWORD PTR [rdx-0x40]
   0x00000000007830f7 <+183>:	movdqu xmm6,XMMWORD PTR [rdx-0x30]
   0x00000000007830fc <+188>:	por    xmm0,xmm2
   0x0000000000783100 <+192>:	movdqu xmm4,XMMWORD PTR [rdx-0x20]
   0x0000000000783105 <+197>:	movdqu xmm7,XMMWORD PTR [rdx-0x10]
   0x000000000078310a <+202>:	por    xmm1,xmm5
   0x000000000078310e <+206>:	por    xmm0,xmm3
   0x0000000000783112 <+210>:	por    xmm1,xmm6
   0x0000000000783116 <+214>:	por    xmm1,xmm7
   0x000000000078311a <+218>:	por    xmm0,xmm4
   0x000000000078311e <+222>:	por    xmm0,xmm1
   0x0000000000783122 <+226>:	movdqa xmm1,xmm0
   0x0000000000783126 <+230>:	psrldq xmm1,0x8
   0x000000000078312b <+235>:	por    xmm0,xmm1
   0x000000000078312f <+239>:	movq   rax,xmm0
   0x0000000000783134 <+244>:	test   rax,r8
   0x0000000000783137 <+247>:	je     0x7830c8 <ucs1lib_find_max_char+136>

The surprising part for me is that GCC decided to also unroll (6 iterations) and vectorize the smaller loop for (; p + SIZEOF_SIZE_T <= _end; p += SIZEOF_SIZE_T) {: 6 movdqu (128-bit) and 6 por (128-bit).

   0x000000000078e3b1 <+657>:	movdqu xmm2,XMMWORD PTR [rdx+0x10]
   0x000000000078e3b6 <+662>:	por    xmm0,xmm2
   0x000000000078e3ba <+666>:	cmp    r10,0x2
   0x000000000078e3be <+670>:	je     0x78e405 <_PyUnicode_FromUCS1+741>
   0x000000000078e3c0 <+672>:	movdqu xmm3,XMMWORD PTR [rdx+0x20]
   0x000000000078e3c5 <+677>:	por    xmm0,xmm3
   0x000000000078e3c9 <+681>:	cmp    r10,0x3
   0x000000000078e3cd <+685>:	je     0x78e405 <_PyUnicode_FromUCS1+741>
   0x000000000078e3cf <+687>:	movdqu xmm4,XMMWORD PTR [rdx+0x30]
   0x000000000078e3d4 <+692>:	por    xmm0,xmm4
   0x000000000078e3d8 <+696>:	cmp    r10,0x4
   0x000000000078e3dc <+700>:	je     0x78e405 <_PyUnicode_FromUCS1+741>
   0x000000000078e3de <+702>:	movdqu xmm5,XMMWORD PTR [rdx+0x40]
   0x000000000078e3e3 <+707>:	por    xmm0,xmm5
   0x000000000078e3e7 <+711>:	cmp    r10,0x5
   0x000000000078e3eb <+715>:	je     0x78e405 <_PyUnicode_FromUCS1+741>
   0x000000000078e3ed <+717>:	movdqu xmm6,XMMWORD PTR [rdx+0x50]
   0x000000000078e3f2 <+722>:	por    xmm0,xmm6
   0x000000000078e3f6 <+726>:	cmp    r10,0x6
   0x000000000078e3fa <+730>:	je     0x78e405 <_PyUnicode_FromUCS1+741>
   0x000000000078e3fc <+732>:	movdqu xmm7,XMMWORD PTR [rdx+0x60]
   0x000000000078e401 <+737>:	por    xmm0,xmm7
   0x000000000078e405 <+741>:	movdqa xmm1,xmm0
   0x000000000078e409 <+745>:	psrldq xmm1,0x8
   0x000000000078e40e <+750>:	por    xmm0,xmm1
   0x000000000078e412 <+754>:	movq   r8,xmm0
   0x000000000078e417 <+759>:	or     rcx,r8
   0x000000000078e41a <+762>:	lea    r8,[r10+r10*1]
   0x000000000078e41e <+766>:	cmp    r8,rbx
   0x000000000078e421 <+769>:	je     0x78e42d <_PyUnicode_FromUCS1+781>
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
vstinner
vstinner approved these changes Nov 8, 2026
View reviewed changes

@vstinner vstinner left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM. But I just have one last coding style suggestion :-)

I checked the PR on my stress test and it passed!

Using size_t* should help the compiler to vectorize the code and use the most efficient available instructions for that task. At least, I could check that on x86-64, SIMD is used.

I didn't run a benchmark, but I expected that SMID working on 128-bit vectors should be more efficient than the current code!

The current code is more pessimistic: it checks that each size_t word (8 bytes) exceeds the limit. This PR is more optimistic and only check every 16 size_t words (128 bytes) that the limite is exceeded. The optimistic approach is more efficient and it seems like only have a "minor" impact on the unlucky code path (when we hit the limit). It just reads too many bytes, but it's not a big deal. CPUs like to read multiple bytes forward, they should be well optimized for that (CPU cache lines).

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Objects/stringlib/find_max_char.h Resolved

Uh oh!

There was an error while loading. Please reload this page.
@vstinner

vstinner commented Nov 8, 2026

Copy link
Copy Markdown
Member

@StanFromIreland: I understand that the benchmark numbers were on the memcpy() PR. You rewrote the PR to use size_t* pointers instead. Would you mind to re-run benchmarks?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
Use for loop instead
0803510
@StanFromIreland

StanFromIreland commented Nov 8, 2026

Copy link
Copy Markdown
Member

Sure, here are benchmarks at the current commit:

So, after some testing I pushed a little change to use four accumulators and a 16-word block so the loop is faster even when it's not vectorised. Benchmarking again, some more promising results:

AMD Ryzen 7 8845HS, --enable-optimizations & --with-lto, GCC 15.3.1, Linux-7.1.13-100

Benchmark maxchar-main maxchar-pr-final
control: ascii[1001] slice[:-1] 85.1 ns 84.3 ns: 1.01x faster
ucs1[8] slice[:-1] 45.3 ns 43.6 ns: 1.04x faster
ucs1[21] slice[:-1] 48.0 ns 43.9 ns: 1.09x faster
ucs1[1001] slice[:-1] 120 ns 118 ns: 1.02x faster
ucs1[1001] slice[1:] (odd ptr) 124 ns 122 ns: 1.01x faster
ucs1[1001] slice[3:] 124 ns 123 ns: 1.01x faster
ucs1[1001] non-ascii body slice[:-1] 73.6 ns 74.0 ns: 1.01x slower
ucs1[100001] slice[:-1] 6.71 us 6.05 us: 1.11x faster
ucs1[10_000_001] slice[:-1] 788 us 660 us: 1.19x faster
ucs2[21] slice[:-1] 48.4 ns 45.0 ns: 1.08x faster
ucs2[1002] slice[:-1] (issue) 195 ns 111 ns: 1.77x faster
ucs2[1001] latin1 body slice[:-1] 195 ns 113 ns: 1.73x faster
ucs2[1001] slice[1:] 195 ns 117 ns: 1.66x faster
ucs2[1001] wide body slice[:-1] 91.5 ns 88.0 ns: 1.04x faster
ucs4[21] slice[:-1] 50.7 ns 49.1 ns: 1.03x faster
ucs4[1001] slice[:-1] 309 ns 247 ns: 1.25x faster
ucs4[1001] wide body slice[:-1] 101 ns 97.9 ns: 1.04x faster
bytes[10] isascii 36.4 ns 36.2 ns: 1.00x faster
bytes[1000] isascii 61.5 ns 50.1 ns: 1.23x faster
bytes[1000] decode latin-1 134 ns 132 ns: 1.01x faster
bytes[1000] non-ascii decode latin-1 82.7 ns 84.5 ns: 1.02x slower
ucs1 200 lines x 51 split 5.69 us 5.82 us: 1.02x slower
ucs1 200 lines x 11 split 3.67 us 3.45 us: 1.07x faster
ucs2 200 lines x 51 split 8.57 us 7.59 us: 1.13x faster
Geometric mean (ref) 1.13x faster

Intel(R) Core(TM) i5-7500T CPU @ 2.70GHz, release-build, GCC 15.2.1, Linux-6.14.0-63

Benchmark maxchar-main maxchar-pr-8nov
control: ascii[1001] slice[:-1] 228 ns 218 ns: 1.05x faster
ucs1[8] slice[:-1] 143 ns 138 ns: 1.04x faster
ucs1[1001] slice[:-1] 286 ns 245 ns: 1.17x faster
ucs1[1001] slice[1:] (odd ptr) 295 ns 252 ns: 1.17x faster
ucs1[1001] slice[3:] 293 ns 250 ns: 1.17x faster
ucs1[1001] non-ascii body slice[:-1] 227 ns 229 ns: 1.01x slower
ucs1[100001] slice[:-1] 7.60 us 4.95 us: 1.54x faster
ucs1[10_000_001] slice[:-1] 1.24 ms 991 us: 1.25x faster
ucs2[21] slice[:-1] 145 ns 146 ns: 1.01x slower
ucs2[1002] slice[:-1] (issue) 483 ns 278 ns: 1.74x faster
ucs2[1001] latin1 body slice[:-1] 521 ns 317 ns: 1.65x faster
ucs2[1001] slice[1:] 526 ns 320 ns: 1.64x faster
ucs4[21] slice[:-1] 148 ns 148 ns: 1.00x slower
ucs4[1001] slice[:-1] 808 ns 482 ns: 1.68x faster
ucs4[1001] wide body slice[:-1] 257 ns 254 ns: 1.01x faster
bytes[10] isascii 92.9 ns 96.4 ns: 1.04x slower
bytes[1000] isascii 151 ns 119 ns: 1.26x faster
bytes[1000] decode latin-1 308 ns 264 ns: 1.17x faster
bytes[1000] non-ascii decode latin-1 256 ns 249 ns: 1.03x faster
ucs1 200 lines x 51 split 15.0 us 11.8 us: 1.28x faster
ucs1 200 lines x 11 split 9.74 us 8.11 us: 1.20x faster
ucs2 200 lines x 51 split 17.2 us 12.2 us: 1.41x faster
Geometric mean (ref) 1.20x faster

Benchmark hidden because not significant (2): ucs1[21] slice[:-1], ucs2[1001] wide body slice[:-1]

PGO+LTO is a little slower than before, but that seems to be because of PGO poorly optimising _PyUnicode_FromUCS1 based on some debugging.

If there are no more comments, I will merge this tomorrow. :-)
vstinner reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@StanFromIreland
StanFromIreland merged commit ff042f1 into python:main Nov 9, 2026
56 checks passed

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the awaiting merge label Nov 9, 2026
@vstinner

vstinner commented Nov 9, 2026

Copy link
Copy Markdown
Member

Yeah! That's a cool change, I like it!
StanFromIreland reacted with heart emoji
All reactions
  • ❤️ 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@eendebakpt eendebakpt eendebakpt left review comments
@StanFromIreland StanFromIreland StanFromIreland left review comments
@vstinner vstinner vstinner approved these changes
@picnixz picnixz picnixz approved these changes

Uh oh!

There was an error while loading. Please reload this page.

Assignees

@StanFromIreland StanFromIreland

Labels

type-feature A feature request or enhancement

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

7 participants

@ruema @bedevere-bot @StanFromIreland @eendebakpt @chris-eibl @picnixz @vstinner
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.