Skip to content

Amortize in-place string concatenation - #4

Draft
moreal wants to merge 18 commits into
mainfrom
perf/str-inplace-concat
Draft

Amortize in-place string concatenation#4
moreal wants to merge 18 commits into
mainfrom
perf/str-inplace-concat

Conversation

@moreal

@moreal moreal commented Aug 31, 2026

Copy link
Copy Markdown
Owner
  • Closes #xxxx

One of the checkboxes below must be checked before this draft is submitted upstream.

  • I did not use AI to write the code of this patch.
  • This PR follows our AI policy

Summary

Repeated in-place string concatenation previously allocated an exactly sized buffer and copied the entire left-hand string for every append. A loop using s += piece therefore scaled quadratically.

Store owned string data in a capacity-bearing Wtf8Buf and reuse that allocation when the left operand is uniquely owned. String kind and character length are packed into one atomic metadata word so the payload remains five machine words. Shared left operands retain copy-on-write behavior, and cached hash/index state is invalidated when a unique string is extended.

This is an internal performance change. Python-visible string immutability and concatenation behavior are unchanged.

Performance

benches/microbenchmarks/str_inplace_concat.py repeatedly appends a short string to an initially empty string. Comparing the benchmark-only baseline with this change:

Appends Baseline This PR Change
2,000 300.09 µs 118.53 µs -60.5%
6,000 1.5901 ms 358.20 µs -77.1%
10,000 3.7417 ms 599.05 µs -83.9%
14,000 6.7585 ms 840.36 µs -87.5%
18,000 10.701 ms 1.0819 ms -89.7%

The widening improvement as the input grows is consistent with replacing repeated full-prefix copies with amortized buffer growth.

Testing

  • Two focused append/reallocation tests
  • Targeted RustPython script covering Unicode/WTF-8 content, shared left operands, cached hashes, and indexing after concatenation
  • cargo run --release -- -m test test_str (138 passed, 10 skipped)
  • Three relevant snippet tests
  • cargo fmt --all -- --check
  • cargo clippy -p rustpython-vm --all-targets -- -D warnings
  • cargo test --workspace --exclude rustpython_wasm --exclude rustpython-venvlauncher --exclude rustpython-capi
  • (cd crates/capi && cargo test) (103 passed)

AI assistance

Codex (gpt-5.6-sol) assisted extensively with the implementation, tests, benchmark setup and analysis, automated validation, code review, and drafting this PR description. Before submission upstream, the contributor must personally review the final diff and complete the hands-on verification required by the project AI policy.

@moreal
moreal force-pushed the perf/str-inplace-concat branch from 9e11753 to 1c58b2a Compare September 2, 2026 17:21
@github-actions

github-actions Bot commented Sep 2, 2026 •
edited
Loading

Copy link
Copy Markdown

📦 Library Dependencies

The following Lib/ modules were modified. Here are their dependencies:

[ ] lib: cpython/Lib/profiling
[ ] test: cpython/Lib/test/test_profiling

dependencies:

  • profiling (native: main, _child_monitor, _css_utils, _format_utils, _lsprof, _remote_debugging, binary_collector, binary_reader, cli, collector, constants, display, dump, errors, gecko_collector, heatmap_collector, importlib.machinery, importlib.resources, importlib.util, itertools, jsonl_collector, live_collector, marshal, math, module_utils, opcode_utils, profiling.tracing, profiling.tracing._utils, pstats_collector, sample, stack_collector, string_table, sys, time, trend_tracker, widgets)
    • curses (native: _curses, _curses_panel, curses.ascii, has_key, sys)
    • io (native: _io, _thread, errno, msvcrt, sys)
    • opcode (native: _opcode, builtins)
    • platform (native: _wmi, itertools, sys, vms_lib, winreg)
    • site (native: _io, _pyrepl.main, _pyrepl.pager, _pyrepl.readline, _pyrepl.unix_console, _pyrepl.windows_console, atexit, builtins, errno, readline, sitecustomize, sys, usercustomize)
    • sysconfig (native: _sysconfig, _winapi, importlib.machinery, importlib.util, os.path, sys)
    • _colorize, abc, argparse, base64, collections, contextlib, dataclasses, functools, html, json, linecache, locale, optparse, os, pathlib, pstats, re, runpy, selectors, socket, statistics, subprocess, tempfile, threading, traceback, types, typing, uuid, webbrowser

dependent tests: (3 tests)

  • profiling: test_profiling
    • cProfile: test_cprofile test_pstats

[x] test: cpython/Lib/test/test_external_inspection.py

dependencies:

dependent tests: (no tests depend on external_inspection)

[ ] test: cpython/Lib/test/test_set.py (TODO: 1)

dependencies:

dependent tests: (no tests depend on set)

[x] lib: cpython/Lib/traceback.py
[x] test: cpython/Lib/test/test_traceback.py (TODO: 2)

dependencies:

  • traceback

dependent tests: (170 tests)

  • traceback: test_asyncio test_builtin test_code_module test_concurrent_futures test_contextlib test_contextlib_async test_coroutines test_dictcomps test_exceptions test_http_cookiejar test_importlib test_iter test_listcomps test_pyexpat test_setcomps test_socket test_ssl test_subprocess test_sys test_threadedtempfile test_threading test_traceback test_unittest test_with test_zipimport
    • code:
      • pdb: test_pdb
      • sqlite3.main: test_sqlite3
    • concurrent.futures.interpreter: test_concurrent_futures
    • concurrent.futures.process: test_compileall test_concurrent_futures
    • http.cookiejar: test_urllib2
      • urllib.request: test_httpservers test_pathlib test_pydoc test_sax test_site test_urllib test_urllib2_localnet test_urllib2net test_urllibnet
    • logging: test_asyncio test_decimal test_genericalias test_hashlib test_logging test_pkgutil test_support test_unittest
      • multiprocessing.util: test_asyncio test_concurrent_futures
      • venv: test_venv
    • multiprocessing: test_fcntl test_importlib test_memoryview test_multiprocessing_forkserver test_multiprocessing_main_handling test_profiling test_re
    • profiling.sampling.dump: test_profiling
    • py_compile: test_cmd_line_script test_importlib test_modulefinder test_py_compile test_runpy
      • zipfile: test_shutil test_zipapp test_zipfile test_zipfile64 test_zipimport_support
    • pydoc: test_enum
      • xmlrpc.server: test_docxmlrpc test_xmlrpc
    • socketserver: test_imaplib test_socketserver test_wsgiref
    • threading: test_android test_asyncio test_bytes test_bz2 test_code test_concurrent_futures test_context test_ctypes test_email test_enumerate test_external_inspection test_fork1 test_frame test_ftplib test_functools test_gc test_httplib test_importlib test_inspect test_io test_ioctl test_itertools test_linecache test_opcache test_pathlib test_poll test_poplib test_pyrepl test_queue test_robotparser test_sched test_signal test_smtplib test_sqlite3 test_super test_syslog test_termios test_threading_local test_time test_weakref test_winreg test_zstd
      • bdb: test_bdb
      • dummy_threading: test_dummy_threading
      • importlib.util: test_asdl_parser test_ctypes test_doctest test_importlib test_reprlib
      • queue: test_dummy_thread
      • subprocess: test_asyncio test_atexit test_audit test_c_locale_coercion test_cmd_line test_ctypes test_dtrace test_embed test_faulthandler test_file_eintr test_gzip test_json test_launcher test_msvcrt test_ntpath test_os test_osx_env test_peg_generator test_platform test_plistlib test_profiling test_pyrepl test_quopri test_regrtest test_repl test_script_helper test_select test_sys_settrace test_sysconfig test_tempfile test_tkinter test_tstring test_unittest test_utf8_mode test_wait3 test_webbrowser test_xpickle
      • sysconfig: test_importlib test_os test_tools
      • trace: test_trace
    • timeit: test_timeit
    • tkinter: test_tkinter test_ttk test_ttk_textonly

Legend:

  • [+] path exists in CPython
  • [x] up-to-date, [ ] outdated

@youknowone
youknowone force-pushed the perf/str-inplace-concat branch from 1c58b2a to 91df720 Compare September 16, 2026 17:16
youknowdot and others added 18 commits October 25, 2026 15:09
@youknowdot @dependabot
Align profiler bindings and capability checks with Python 3.15 (RustP…
8c0c242 
…ython#9340)

* Align offline profiler argument binding with Python 3.15

Accept the canonical keyword names for binary sample writes and native
context exits. Resolve the argument layout before numeric callbacks,
then preserve float-subclass payloads while accepting numeric protocols
for required and optional profile statistics.

AI-assisted source extraction, implementation, and source review with
OpenAI Codex. Runtime validation remains pending.

Assisted-by: OpenAI Codex:model version unavailable

* Restore the offline profiler capability flag

Preserve the original mega branch's zero-valued process_vm_readv
capability export. The native live unwinder remains unsupported; this
restores the public feature query without claiming live inspection support
or changing canonical test helpers.

AI-assisted source preservation and review with OpenAI Codex.

Assisted-by: OpenAI Codex:model version unavailable

* Restore finite-EOF table bounds for offline profiles

Match CPython's EOF-wide table count and decoding windows while retaining
checked offsets, allocation limits, cursor bounds, and replay checks.
This restores the original mega's finite-file contract without changing
canonical tests or the already validated argument-binding implementation.

Assisted-by: OpenAI Codex:model version unavailable

* Preserve symtable warning exceptions and original filenames (RustPython#9282)

Keep warning-hook exceptions untouched instead of rewriting SyntaxError
subclasses. Thread the original Python filename through parser warning
emission and fresh warning-as-error SyntaxError construction, preserving
fsdecoded bytes paths and lone surrogates.

Assisted-by: OpenAI Codex:model-version-unavailable

* build(deps): align the Cranelift 0.136 dependency family (RustPython#9341)

* build(deps): bump the wasmtime group across 1 directory with 2 updates

Bumps the wasmtime group with 2 updates in the / directory: [cranelift](https://github.com/bytecodealliance/wasmtime) and [cranelift-module](https://github.com/bytecodealliance/wasmtime).


Updates `cranelift` from 0.135.2 to 0.136.3
- [Release notes](https://github.com/bytecodealliance/wasmtime/releases)
- [Changelog](https://github.com/bytecodealliance/wasmtime/blob/main/RELEASES.md)
- [Commits](https://github.com/bytecodealliance/wasmtime/commits)

Updates `cranelift-module` from 0.135.3 to 0.136.3
- [Release notes](https://github.com/bytecodealliance/wasmtime/releases)
- [Changelog](https://github.com/bytecodealliance/wasmtime/blob/main/RELEASES.md)
- [Commits](https://github.com/bytecodealliance/wasmtime/commits)

---
updated-dependencies:
- dependency-name: cranelift
  dependency-version: 0.136.3
  dependency-type: direct:production
  update-type: version-update:semver-minor
  dependency-group: wasmtime
- dependency-name: cranelift-module
  dependency-version: 0.136.3
  dependency-type: direct:production
  update-type: version-update:semver-minor
  dependency-group: wasmtime
...

Signed-off-by: dependabot[bot] <[email protected]>

* Align cranelift-jit with the 0.136 dependency family

Update cranelift-jit alongside cranelift and cranelift-module so the JIT shares their LibCall, FuncId, and Module trait identities. Regenerate only the affected dependency lock entries, preserving the original dependency PR changes.

AI assistance covered the dependency diagnosis, alignment, and static review.

Assisted-by: OpenAI Codex:model-version-unavailable

---------

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* Support selective canonical function migration

Add hash-pinned function selection to the official Lib migration tool,
preserving canonical source bytes and rejecting ambiguous dependencies.

Assisted-by: OpenAI Codex:model version unavailable

* Detect CPython runtimes for canonical inspection feature checks

Add native runtime-cookie detection and import the exact Python 3.15
inspection helpers and tests through the official Lib migration tool.
Preserve the offline profiler argument and finite-EOF corrections.

Assisted-by: OpenAI Codex:model version unavailable

---------

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@1ndahous3
Collect cycles through sets, frozensets and set iterators (RustPython…
db48780 
…#9343)

Assisted-by: Codex:GPT-6
@youknowdot
Align Python 3.15 bytecode tooling (RustPython#9344)
65ee7ba 
Extract independent bytecode tooling from the Python 3.15 integration. Decode packed import-name arguments without changing older-interpreter fallback behavior, validate canonical opcode numbering, bound deoptimization families to the enum, and reuse parsed CPython analysis.

Validated generators reproduce tracked metadata exactly; normal, lazy and eager import fallback matches canonical disassembly. No interpreter, generated metadata or test changes.

Assisted-by: OpenAI Codex: model version unavailable
@fanninpm
Specify exactly where package.json files are located (RustPython#9345)
a8ad41e
@youknowdot
Restore canonical traceback Levenshtein coverage (RustPython#9346)
2efa217 
Import the unchanged Python 3.15.0 fixture with the official library updater
and retire the missing-fixture expectedFailure after validating the existing
distance and threshold tests. Preserve all assertions and unrelated markers.

Assisted-by: OpenAI Codex: model version unavailable
@youknowdot
Handle full-width operands in the None-return scanner (RustPython#9347)
9bd84b2 
Use decoded logical instructions rather than the preceding raw operand byte. Check referenced constants by None identity and decode common constants without panicking.

Assisted-by: OpenAI Codex:model unavailable
@dependabot
build(deps): bump reviewdog/action-actionlint from 1.80.2 to 1.80.4 (R…
46c0663 
…ustPython#9348)

Bumps [reviewdog/action-actionlint](https://github.com/reviewdog/action-actionlint) from 1.80.2 to 1.80.4.
- [Release notes](https://github.com/reviewdog/action-actionlint/releases)
- [Commits](reviewdog/action-actionlint@3cbf14e...419a493)

---
updated-dependencies:
- dependency-name: reviewdog/action-actionlint
  dependency-version: 1.80.4
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps): bump mach2 from 0.4.3 to 0.7.0 (RustPython#9349)
ef6e2db 
Bumps [mach2](https://github.com/JohnTitor/mach2) from 0.4.3 to 0.7.0.
- [Release notes](https://github.com/JohnTitor/mach2/releases)
- [Commits](JohnTitor/mach2@0.4.3...0.7.0)

---
updated-dependencies:
- dependency-name: mach2
  dependency-version: 0.7.0
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps): bump memmap2 from 0.9.11 to 0.9.12 (RustPython#9350)
0cb9f13 
Bumps [memmap2](https://github.com/RazrFalcon/memmap2-rs) from 0.9.11 to 0.9.12.
- [Changelog](https://github.com/RazrFalcon/memmap2-rs/blob/master/CHANGELOG.md)
- [Commits](RazrFalcon/memmap2-rs@v0.9.11...v0.9.12)

---
updated-dependencies:
- dependency-name: memmap2
  dependency-version: 0.9.12
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps): bump @xterm/addon-fit from 0.10.0 to 0.11.0 in /wasm/demo (
cb92931 
RustPython#9352)

Bumps [@xterm/addon-fit](https://github.com/xtermjs/xterm.js) from 0.10.0 to 0.11.0.
- [Release notes](https://github.com/xtermjs/xterm.js/releases)
- [Commits](xtermjs/xterm.js@0.10...0.11)

---
updated-dependencies:
- dependency-name: "@xterm/addon-fit"
  dependency-version: 0.11.0
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps): bump object from 0.37.3 to 0.40.0 (RustPython#9351)
b7bebe6 
Bumps [object](https://github.com/gimli-rs/object) from 0.37.3 to 0.40.0.
- [Changelog](https://github.com/gimli-rs/object/blob/main/CHANGELOG.md)
- [Commits](gimli-rs/object@0.37.3...v0.40.0)

---
updated-dependencies:
- dependency-name: object
  dependency-version: 0.40.0
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps): bump xterm-readline from 1.1.2 to 1.3.1 in /wasm/demo (R…
bb08d9a 
…ustPython#9354)

Bumps [xterm-readline](https://github.com/strtok/xterm-readline) from 1.1.2 to 1.3.1.
- [Changelog](https://github.com/strtok/xterm-readline/blob/main/CHANGELOG.md)
- [Commits](https://github.com/strtok/xterm-readline/commits/v1.3.1)

---
updated-dependencies:
- dependency-name: xterm-readline
  dependency-version: 1.3.1
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps-dev): bump mini-css-extract-plugin in /wasm/demo (RustPyth…
636a967 
…on#9353)

Bumps [mini-css-extract-plugin](https://github.com/webpack/mini-css-extract-plugin) from 2.9.2 to 2.10.2.
- [Release notes](https://github.com/webpack/mini-css-extract-plugin/releases)
- [Changelog](https://github.com/webpack/mini-css-extract-plugin/blob/main/CHANGELOG.md)
- [Commits](webpack/mini-css-extract-plugin@v2.9.2...v2.10.2)

---
updated-dependencies:
- dependency-name: mini-css-extract-plugin
  dependency-version: 2.10.2
  dependency-type: direct:development
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@dependabot
build(deps-dev): bump css-loader from 7.1.2 to 7.1.5 in /wasm/demo (R…
901c014 
…ustPython#9355)

Bumps [css-loader](https://github.com/webpack/css-loader) from 7.1.2 to 7.1.5.
- [Release notes](https://github.com/webpack/css-loader/releases)
- [Changelog](https://github.com/webpack/css-loader/blob/main/CHANGELOG.md)
- [Commits](webpack/css-loader@v7.1.2...v7.1.5)

---
updated-dependencies:
- dependency-name: css-loader
  dependency-version: 7.1.5
  dependency-type: direct:development
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
@youknowdot
Add canonical sampling profiler CLI for offline replay (RustPython#9358)
901eb88 
Import the CLI, entry point, error type, coordinator dependency, and CLI
tests with scripts/update_lib migrate from CPython 3.15.0 at
d220409a13b77de7a6c30abe16ea90db01528edc.

This frontend follows the existing offline collector/codec support. Live
attach, run, and dump remain unsupported and unvalidated.

Assisted-by: OpenAI Codex: model version unavailable
@moreal
ci: remove OSCCA pull request triage workflow (RustPython#9361)
0f74d1c 
Stop automatically labeling OSCCA participants' pull requests with
z-ca-2026 and assigning them, and drop the matching zizmor ignore entry.

Assisted-by: Claude Code:claude-opus-5-5
@moreal
bench: cover in-place string concatenation
9fe3494 
Assisted-by: Codex:gpt-5.6-sol
@moreal
perf: amortize in-place string concatenation
4342bfc 
Assisted-by: Codex:gpt-5.6-sol
@moreal
moreal force-pushed the perf/str-inplace-concat branch from 91df720 to 4342bfc Compare October 25, 2026 11:01
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

See More

@moreal moreal

Labels

z-ca-2026

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@moreal @youknowdot @1ndahous3 @fanninpm