gh-129724: Make marshalled code output deterministic - #156862

Summary

This makes marshalled code-object output deterministic in free-threaded builds, including when multiple threads compile modules concurrently.

Fixes #129724.
Fixes #156504.

The standard build retains current main compiler-cache and marshal behavior.

Problem

Marshal decides whether to add an object to its reference table using _PyObject_IsUniquelyReferenced(). In a free-threaded build, that result can depend on object ownership and shared-reference state. The same code object can therefore receive different FLAG_REF placements depending on thread timing and prior accesses.

Because a .pyc file contains the marshalled code object after its 16-byte header, this makes otherwise identical parallel compilations produce byte-different .pyc files. Running a free-threaded interpreter with -X gil=1 does not avoid the problem because it does not change the free-threaded object's reference representation.

Approach

For a top-level code object in a free-threaded build, marshal now uses deterministic reference tracking:

• supported objects are registered independently of their live reference counts;
• aliases and recursive containers continue to round-trip correctly;
• set and frozenset elements are ordered by deterministic marshal encodings;
• set elements with identical encodings but distinguishable alias graphs are rejected rather than ordered by process-specific identity;
• detailed marshal errors are preserved instead of being overwritten by generic container errors.

In free-threaded builds, the compiler also avoids sharing rebuildable constant containers across code units. Frozensets and slices use a code-unit-local cache instead of the compiler-wide cache. This preserves same-code-unit deduplication while preventing compilation order from changing the object graph later passed to marshal.

Valid source can create distinct NaN constants whose marshal encodings compare equal. In free-threaded builds, constant folding therefore leaves NaN-containing set displays as runtime BUILD_SET operations instead of creating an ambiguously ordered constant.

Marshal versions 0 through 2 do not have a reference table, so their reference-tracking behavior is unchanged. The new ambiguous-set rejection applies to every marshal version when deterministic code-object mode is active. Generic non-code-object marshaling retains the existing path.

Compatibility

• Standard builds retain current main sharing behavior. Baseline and candidate bytes matched for both tested compilation histories.
• Current main can itself produce different standard-build bytes after an unrelated compilation changes frozenset sharing. This pre-existing behavior is outside the free-threaded scope of this change.
• Free-threaded output changes to a deterministic canonical representation but unmarshals to equivalent code.
• Payload size was unchanged in the current benchmark workload: 68,172 bytes.
• A 24-module synthetic package was unchanged at 1,067,465 bytes.
• In real-wheel integration tests, total .pyc size increased by 77 bytes for
  pip across 17 of 404 files and by 63 bytes for Plotly across 4 of 1,507
  files. The largest per-file change was 23 bytes, and each total change was
  below 0.002%.
• Repeated constants in one code unit remain deduplicated.
• Free-threaded cross-code-unit identity sharing of rebuildable constant containers is no longer relied on.

Determinism results

Testing used x64 Release standard and free-threaded interpreters built from current main (42de93a62e) and the core implementation (eae9b877a7) on the same 8-vCPU Windows VM. The final compatibility follow-up is 3f056a9782; it narrows standard-build compiler behavior without changing the free-threaded marshal algorithm.

That is 80 candidate stress attempts with no differing output.

The exact final tree also completed 10 attempts for each combination locally: 40 additional attempts with no differing output.

Performance

The same 8-vCPU VM ran eight paired current-main/candidate rounds, alternating process order. Ratios below are the median paired candidate/baseline ratio; values above 1 are slower.

The stable tradeoff is the synthetic repeated free-threaded marshal.dumps(code) case: about 51% more time and 35% more peak memory because deterministic mode records all supported references. marshal.loads is about 5% slower with 4.5% more peak memory. Compile-plus-marshal was neutral, and the synthetic cold-import result was about 1.4% slower. Generic and threaded measurements had wider VM variance and should not be interpreted as performance improvements.

Integrated pip workload

The change was tested end-to-end with pip PR 14286, which parallelizes Windows wheel bytecode compilation. The benchmark copy removed only pip's guard that keeps free-threaded builds serial. Both CPython variants and both GIL modes used eight worker threads.

Each timing is the median of six balanced runs on the same eight-vCPU Windows VM with Defender antivirus, real-time, IOAV, and behavior monitoring enabled.
The benchmark fixed SOURCE_DATE_EPOCH=1704067200 and PYTHONHASHSEED=0 to
isolate thread-order effects.

Current main produced serial/parallel artifact differences in 14 of 48
full-matrix parallel installs. The deterministic build produced zero
differences in all 48.

The exact-final follow-up used four counterbalanced runs per wheel, filesystem,
and GIL mode. Current main differed in 9 of 32 parallel installs; exact
3f056a9782 differed in 0 of 32, and its 32 serial repeats were identical.
Together, the full and exact-final matrices successfully unmarshalled 305,760
measured .pyc payloads.

Across the six-run matrix, aggregate serial timing for the fixed runtime was
about 1% slower than current main and within run-to-run variance, with no
consistent parallel penalty. In the exact-final matrix,
candidate/current-main peak committed/pagefile ratios ranged from 0.998-1.004
serial and 0.960-1.020 parallel, so there was no consistent whole-process
memory increase attributable to this change. Absolute fixed-runtime peak
committed usage was 133.5-134.8 MiB serial and 239.6-300.6 MiB parallel; peak
working set was 98.7-107.5 MiB serial and 169.3-196.5 MiB parallel. These
whole-process measurements do not replace the marshal-only peak-memory result.

Default GIL-off PythonT retained a 1.44x-3.64x speedup. With the GIL re-enabled, NTFS still benefited substantially, while the trusted Dev Drive was neutral to slightly slower.

The pip implementation used eight workers on a VM with eight logical CPUs;
these measurements do not establish the optimal worker count elsewhere.

WSL cross-platform confirmation

The exact candidate was also built with GCC 15.2 on x86-64 Ubuntu 26.04 WSL2
and tested on native ext4 storage. The CPython diff has no OS- or
CPU-architecture-specific branch; its conditional behavior uses only
Py_GIL_DISABLED. This run therefore adds Linux ABI/toolchain coverage, but
not Arm64 coverage.

The standalone reproducer found a current-main difference on attempt 1 for
both marshal and py_compile, with the GIL both disabled and enabled. Exact
3f056a9782 completed all 40 corresponding attempts with no difference.
Focused test_marshal, test_compile, and test_code runs passed 313 tests
in each GIL mode.

For an integrated check, the pip PR copy was temporarily enabled on Linux and
free-threaded builds. Six counterbalanced runs used four workers:

Current main differed from serial output in 13 of 24 parallel installs. The
candidate differed in 0 of 24, and all 91,728 measured .pyc payloads
unmarshalled successfully. Candidate/current-main geometric-mean timing ratios
were 0.993 serial and 1.018 parallel. The approximately 1.8% aggregate
parallel difference varied by workload and is small relative to the GIL-off
pip gain. Peak virtual size was effectively identical; geometric-mean peak
RSS ratios were 1.001 serial and 1.014 parallel.

The size effect matched Windows: pip .pyc files grew by 77 total bytes and
Plotly by 63, with a maximum per-file change of 23 bytes. The result also
confirms the pip policy distinction: default GIL-off PythonT benefits on ext4,
while GIL-on PythonT was 21-29% slower with four workers.

Alternatives measured

• Borrowing deterministic hashtable keys improved direct dumps by about 5% but did not reduce memory and regressed compile-plus-marshal in the sample.
• A graph-counting two-pass writer reduced reader peak memory by about 27% but made direct dumps another 39% slower than register-all.
• A one-probe hashtable API was neutral for direct dumps in stable VM rounds and about 6% slower in the threaded batch, while adding broad internal API surface.
• Skipping immortal small ints made direct dumps about 2% slower and did not change measured peak memory.

The set-sort ordinal is normally a cached small integer, so replacing it with a temporary set or dict would add hashing and table allocation to save one tuple slot. That was not retained as a promising optimization.

Validation

• Exact-final-tree x64 Release standard and free-threaded builds completed with no warnings.
• x64 Debug standard and free-threaded builds completed with no warnings.
• Tools/patchcheck/patchcheck.py passed.
• Standard default test suite: 49,911 tests in the parallel run plus the isolated Windows-flaky modules, all successful.
• Free-threaded default test suite: 50,178 tests in the parallel run plus the isolated Windows-flaky modules, all successful.
• Free-threaded -X gil=1 focused suite: 1,812 tests successful.
• Exact-final-tree tests for the changed compiler/marshal behavior passed in standard, free-threaded GIL-disabled, and free-threaded GIL-enabled modes.
• Debug refleak checks for test_marshal, test_compile, and test_code passed in both standard and free-threaded builds with -R 3:3.
• Regression tests cover compile order, thread interleavings, aliases, recursion, sets, ambiguous encodings, NaNs, marshal versions, cross-code-unit isolation, and same-code-unit deduplication.

One test_device_encoding assertion was excluded from the final clean host run because the automation pseudo-console reports stdin as a TTY while os.device_encoding(0) is None. Current main fails the same isolated assertion in that environment.

AI-assisted development disclosure

GitHub Copilot was used to assist investigation, implementation, test drafting, and benchmark organization.

• Issue: Bytecode compilation output depends on order of files compiled #129724