perf: amortize in-place string concatenation - #8629
Conversation
|
Important Draft PR not reviewedDraft PRs are not automatically reviewed by default.
To automatically review draft PRs, update your CodeRabbit configuration: reviews:
auto_review:
drafts: trueThanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
Merging this PR will degrade performance by 21.51%
|
Assisted-by: Codex:gpt-5.6-sol
Assisted-by: Codex:gpt-5.6-sol
9e11753 to
1c58b2a
Compare
1 participant
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 += piecetherefore scaled quadratically.Store owned string data in a capacity-bearing
Wtf8Bufand 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.pyrepeatedly appends a short string to an initially empty string. Comparing the benchmark-only baseline with this change:From 2,000 to 18,000 appends, the final implementation takes about 9.1× as long for 9× the work, showing approximately linear scaling. The baseline takes about 35.7× as long over the same range.
Appendix:
builtin_hashsnippet failureThe Ubuntu snippet job fails in
extra_tests/snippets/builtin_hash.pyat the first assertion that hashing a tuple nested 100,000 levels must raiseRecursionError. On that build,hash(deep_tuple)completes normally, so the following dictionary and set assertions are not reached.This PR does not change tuple hashing or the native-stack guard. The test uses a fixed nesting depth as a proxy for reaching that guard, but the guard checks the actual stack pointer and therefore only raises when the native stack approaches its soft limit. Optimized native frame size is platform- and code-generation-dependent.
A local arm64 macOS comparison used identical
--release --features=threading,jitbuilds of the benchmark-only parent (the same interpreter code as the branch base) and this PR:RecursionErrorPyObject::hashnative frame0x90)0x70)The runtime measurement and disassembly agree on an exact 32-byte reduction per recursive level. Both local builds still reach the same physical stack margin, raise
RecursionErrorwell before 100,000 levels, and pass the snippet. The Ubuntu result is consistent with its optimized frame becoming small enough that 100,000 levels no longer reach the guard. In other words, the failure is caused by the fixed-depth test depending on generated native frame size, not by a change to string semantics or by disabling the stack guard. A local CPython 3.14.7 build also hashes the same 100,000-level value successfully, so raising at that exact depth is not a Python-visible compatibility requirement.AI assistance
Codex (
gpt-5.6-sol) assisted extensively with the design, implementation, tests, correctness validation, benchmark construction and measurement, code review, and drafting this PR description.