codegen: index constant dedup and cache nested-global lookup - #37

Summary

Reduce repeated searches, recursive traversal, hashing, allocation and copying in RustPython's compiler, without changing Python semantics or bytecode.

Implementation details

1. Narrow constant-dedup searches. Build on the original PR's digest indexes so insertion compares only relevant candidates rather than scanning every stored constant. Structural equality remains authoritative when hashes collide. Repair index lifecycle after clearing and compaction, preserving signed-zero, numeric-type, NaN and frozenset semantics.

2. Avoid rehashing nested constants at every ancestor. Use shallow structural digests to narrow compiler code-constant comparisons, and exploit bottom-up canonicalization in the runtime constant cache so already-canonicalized child constants do not require repeated recursive hashing. The identity-based shortcut is private to the compiler cache and relies on canonicalized children; public code-object equality and hashing semantics are not replaced by pointer identity.

3. Borrow analyzed symbol-table subtrees. Replace recursive subtree copies on scope activation with private active frames that borrow immutable analysis results. Keep replay and annotation cursors activation-local; copy symbol maps only when comprehensions temporarily override them. Collect nested-global names once instead of rewalking the tree for every module-level name, and avoid cloning skipped scopes.

4. Reduce temporary allocation and copying. Move constants during compaction instead of deeply cloning them, borrow read-only constant operands, use amortized capacity growth, combine duplicate cache lookups, and avoid temporary tuples/integers used only to calculate a code object's hash. These changes remove redundant implementation work while retaining the same results and error behavior.

5. Shrink private linear instruction storage. Separate CFG-only data and optional Python-export location snapshots from the native linear payload, and use bulk movement for instruction insertion. Entries shrink from 120 to 96 bytes on this arm64 build. Public instruction APIs, raw/semantic source locations, exception metadata and bytecode remain unchanged; the separately measured memory improvement below is not an additional general CPU-speedup claim.

Compile-only measurements

Measured on macOS arm64 with Rust 1.99.0 and CPython 3.15.1. Base is d1c3cb745af41fef0b1d273c24b4b7658daa3fa5; candidate compiler source is 0fc3ddab93b03ed530ed4318397b55631e200a13.

The latest comparison contains 16 inputs, three independent rounds with rotating interpreter order, one warmup and three retained samples per input/round: nine samples per input/interpreter. All inputs succeeded. Values below are median milliseconds; raw samples are retained rather than discarded.

Only compile(source, filename, "exec", flags=0, dont_inherit=True, optimize=0) is timed: parsing, symbol analysis, code generation and runtime code-object conversion. Startup, source generation, code execution and result destruction are excluded. Automatic cyclic GC is disabled during each case. No builds or tests run concurrently with timing.

These are single-machine observations, not universal speedup or asymptotic guarantees. The two RustPython builds use the same Rust toolchain/profile/features; CPython is a reference, not an identically configured build. The standard-library cases and nested lambdas still take longer than CPython. Earlier development experiments also covered all 46 default inputs, with repeated 45/75-sample comparisons where needed.

Real framework source corpus

The same compile-only workers also measured every .py file shipped under the framework's own package directory in official, SHA-256-verified pure-Python wheels. No framework or dependency was installed, imported or executed; transitive dependencies are not included.

The confirmation run used nine rounds, rotating interpreter order and reversing file order in alternating rounds, two warmups and five retained samples per file/round. All 1,063 files compiled successfully on all three interpreters, without dropped files or failed measurements. Base/candidate binaries and compiler flags are the same as above.

For each project and sample index within a round, sum the separately timed per-file compile durations, then take the median of those 45 sums. This is summed pure compilation time, not a contiguous package-import/startup or batch wall-time measurement. Timings are median ± sample standard deviation, in milliseconds:

Every confirmation round's project-level median improved versus base. An initial nine-sample run also succeeded and is retained separately. CPython's Flask samples contain large outliers; none were discarded, and the high standard deviation limits a precise CPython-versus-candidate ranking. These results do not establish framework runtime compatibility, request throughput, startup latency, universal file-level improvements or statistical significance.

The corpus contains 5,918,998 source bytes for Django, 337,446 for Flask and 878,043 for Sanic. Wheel SHA-256 values are 141efee6ec64d1db6db90683bf734c550102450f444fb099063b0be1bd27d991, f4bcbefc124291925f1a26446da31a5178f9483862233b23c0c96a20701f670c and 3874f1fe0442e3b12ce4a3f6524f676d5d3c43839c6a4967d1b82fd8db53c0f3, respectively.

The wheel archives, manifest, exact per-file sources/hashes, one-off corpus adapter, initial/confirmation raw samples and aggregation results are retained locally under target/compile-bench/frameworks-20261027/. The adapter reuses the existing benchmark worker rather than adding framework-specific production code. Its package totals were independently recomputed from the raw per-round file results and checked against the saved summary.

Instruction-storage follow-up

On this arm64 build, private instruction-sequence entries shrink from 120 to 96 bytes, a 20% reduction per backing-array slot. The sequence header grows from 112 to 136 bytes; this is not a claim of 20% lower total compiler memory.

A separate depth-800 experiment used five fresh processes per interpreter. The control here is the ten-optimization snapshot immediately before the instruction-layout changes, not the PR base:

These values include interpreter startup and all compilation phases. They describe one workload on one machine, not compiler-phase allocations or universal savings. An intermediate 104-byte layout did not reduce process RSS and was refined further. Isolated 45/75-sample comparisons found no robust general compile-time speedup from the final layout changes; retain this as a storage/memory improvement, not an additional CPU speedup. Sampled profiles still show instruction allocation/initialization and memory movement as remaining costs.

Reproduction

Build base and candidate with the same release configuration in separate target directories, then run the controller under CPython:

cargo +1.99.0 build --release --locked --bin rustpython

python3.15 scripts/compile_bench.py \
  --cpython /absolute/path/to/python3.15 \
  --base /absolute/path/to/base/rustpython \
  --head /absolute/path/to/head/rustpython \
  --base-ref d1c3cb745af41fef0b1d273c24b4b7658daa3fa5 \
  --head-ref 0fc3ddab93b03ed530ed4318397b55631e200a13 \
  --workloads unique_defs,folded_lists,nested_lambdas,stdlib:functools,stdlib:dataclasses,stdlib:typing \
  --rounds 3 --samples 3 --warmups 1 --output target/compile-bench/comparison

Use actual executables rather than version-manager shims, keep the machine idle, and choose a fresh output directory. Each run writes report.md, raw/per-round results.json, and exact inputs in sources.json, including executable/source hashes and the reproduction command. Failures remain errors and cannot appear as speedups. Revision labels are caller-supplied; RustPython can retain an older embedded Git version string, so that string alone is not provenance.

Measured executable SHA-256 values:

• Base: 548afe03bf05879c4473e977fb978c87172f6cd6bdde906e8bcaa4f67d1c5622
• Candidate: 78d238b987428d3f1231f5f8b1c13ab84847006d2939b0d3470e829acdc2ab82
• CPython: cd353074fb2780e9ed5bdaf2ed6aeab5bd9fc0c883041ea2228da4b653d97903
• Pre-layout memory control: 14a114077bf5e526a6da4ff67afd06e20a5527e61fbe9a8d397753e16436799e

The latest raw comparison is retained locally as target/compile-bench/pr37-pr-summary-20261027-0fc3ddab9/; earlier experiment data are also retained locally, not committed as generated artifacts.

Correctness and local validation

Regression coverage includes constant-index lifecycle/compaction, digest collisions, signed zero, numeric type distinctions, NaN-bearing constants, frozenset order independence, canonical constant-cache hashing, skipped/nested scopes, finally replay, annotations, comprehensions, and instruction-location/label/handler preservation. Hashes only narrow candidates; equality still decides deduplication. Compiler-private canonical hashing does not replace public code-object hash semantics.

• Workspace tests excluding wasm, venvlauncher and C-API: 1,477 passed, 20 ignored, zero failed.
• Separate C-API tests: 128 passed, four ignored, zero failed.
• Workspace and separate C-API Clippy with --all-targets -- -D warnings: passed.
• Release Python tests: all nine selected modules passed (test_code, test_compile, test_symtable, test_scope, test_marshal, test_listcomps, test_setcomps, test_dictcomps, test_genexps; reported run=460, skipped=85).
• Benchmark measurement contracts passed under both RustPython and CPython; formatting/lint hooks and diff whitespace checks passed. These are local results, not a statement that remote CI has completed.

Related prior work: the older perf/compile-time branch. This PR is written against its stated base rather than rebasing that branch.

AI assistance

The original implementation disclosed choco-pi:deepseek-v4.1-flash-1017 in its commit. Subsequent design, implementation, regression tests, performance experiments and review were assisted by Codex (gpt-6.1-sol), with disclosure in the corresponding commit messages. This does not substitute for human review.

• This PR follows the AI policy.