Repository navigation
TypedPython: binary-trees is allocation-bound (1.7x); compiled New pays CPython's full alloc + GC tracking #125
Description
Measured on PR #124 (interleaved, 11 pairs, load 9–13): binary-trees compiled is 1.7–1.8x CPython (both with __slots__), against 29–30x for nbody. The per-access class checks cost at most ~7% (within noise), so they are not the cause.
Hypothesis, not yet measured: each New goes through cls->tp_alloc (PyType_GenericAlloc: zeroing, GC header, PyObject_GC_Track), and dropping a tree runs subtype_dealloc with GC untrack and slot clearing. Compiled and interpreted code pay these alike, so they bound the speedup.
To do:
- Profile compiled binary-trees, splitting time across alloc, dealloc, GC (gen-0 collections triggered by allocation count) and compiled code.
- Only then consider options that keep CPython's observable behaviour, for example a per-type freelist or batching. Changing GC participation is observable (
gc.get_objects, cycles), so it needs a decision.
Done when: the profile breakdown is posted and a decision is recorded on whether anything goes into M2b (2026-11-21).
Activity
b-re-w commentedon Oct 3, 2026
Design-level comparison with Cython, numba and LPython landed in develop via #145 (
docs/investigations/typedpython-vs-cython-numba-lpython.md). The gaps it names have their own issues: #147 (fast entry and inlining), #148 (interval proofs), #149 (zero-copy buffers), #150 (dict/str fast path), #143 (N-12, which covers this issue's allocation cost) and #151 (parallel loops). The decisions are in #152 and #153.Merge pull request #269 from thisisthepy/feat/tp-alloc-prof
b-re-w commentedon Oct 24, 2026
Profile posted: benchmarks/typedpython/results/2026-10-25-binary-trees-alloc-profile.md (via PR above). Largest block is thread-state access (31%, partly the compiled code's own tp_enter_call/tp_impl_check), then dealloc 17%, alloc 14.5%, GC 8%. Unobservable options: cache tstate per compiled call, direct slot reads/writes, cheaper N-11 dealloc, skip redundant zeroing. Observable (need a decision): per-type freelist (id reuse), batched GC accounting. Untracking overlaps #143.
b-re-w commentedon Oct 24, 2026
Decision (leader, 2026-10-25): (1) tstate/TLS once per call: PR #273. (2) Direct slot reads/writes: on 3.15t a shared object's slot needs the same atomic load + TryIncref / critical section as PyMember_GetOne/SetOne, so the gain is only the call (~5%); it is merged into #143 step 2 and applied only to objects proven thread-local. (3) Cheaper N-11 dealloc: deferred. Replacing tp_dealloc is observable once the class later gains del or weakref or a subclass, so it needs a design that survives those changes. Freelist and batched GC accounting: not done (observable).
Merge pull request #273 from thisisthepy/feat/tp-tstate
b-re-w commentedon Oct 25, 2026
Leader (2026-10-25): close after the quiet-window measurement (binary-trees before/after #273) is recorded here, together with the other deferred measurements.
b-re-w commentedon Nov 4, 2026
Before/after #273 binary-trees measurement (2026-11-05), NOT the quiet window: load 7.7 to 12.3 during all 11 rounds, so this does not meet the close condition.
Method: one script, four commands rotated per round (CPython, compiled at 7c0d63f^1 = before #273, at 7c0d63f = #273 merge, at develop HEAD), n=16, python-multiplatform-ksp/.venv 3.15.0rc1t. Compiled functions identical on all three sides: make, check.
Median per-round ratio before/after #273: 1.09x; before/develop: 1.15x. Per-round times varied up to 2x under this load; the spread is large and I do not claim more than the direction. The quiet-window run is still owed.
Merge pull request #371 from thisisthepy/feat/tp-new-fixed-direct
b-re-w commentedon Nov 5, 2026
Implementation step landed in develop via #371: tp_new_fixed fills a fresh object's slots by direct release stores instead of PyMember_SetOne (safety argument in docs/design/typedpython.md 4.3.4). Reference measurement only (load 24 to 27): binary-trees check(make(18)) CPU time median 1.08x vs develop. Freelist and later GC tracking were not done; reasons in the same section (both need an owner decision). Issue stays open.