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