Skip to content

TypedPython: binary-trees is allocation-bound (1.7x); compiled New pays CPython's full alloc + GC tracking #125

Open

Description

@b-re-w

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:

  1. Profile compiled binary-trees, splitting time across alloc, dealloc, GC (gen-0 collections triggered by allocation count) and compiled code.
  2. 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

  1. b-re-w commented on Oct 3, 2026

    @b-re-w
    MemberAuthor

    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.

  2. added a commit that references this issue on Oct 24, 2026
  3. b-re-w commented on Oct 24, 2026

    @b-re-w
    MemberAuthor

    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.

  4. b-re-w commented on Oct 24, 2026

    @b-re-w
    MemberAuthor

    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).

  5. added a commit that references this issue on Oct 25, 2026
  6. b-re-w commented on Oct 25, 2026

    @b-re-w
    MemberAuthor

    Leader (2026-10-25): close after the quiet-window measurement (binary-trees before/after #273) is recorded here, together with the other deferred measurements.

  7. b-re-w commented on Nov 4, 2026

    @b-re-w
    MemberAuthor

    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.

    side median speedup vs CPython
    before #273 1.12x
    after #273 1.24x
    develop 1.31x

    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.

  8. added a commit that references this issue on Nov 5, 2026
  9. b-re-w commented on Nov 5, 2026

    @b-re-w
    MemberAuthor

    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.

  10. added 2 commits that reference this issue on Nov 13, 2026
  11. b-re-w commented on Nov 13, 2026

    @b-re-w
    MemberAuthor

    Semantics-preserving step landed in develop via #405 (merge cee0b92). Constraint (owner's standing intent, leader 2026-11-13): no GIL-only features, no observable change; freelist, deferred GC tracking and batched GC accounting rejected.

    • New moves its argument temporaries' references into the fresh object's slots (tp_new_fixed_move; on failure nothing is taken). Is, IsExact, FieldGet and C-to-C Call arguments borrow a plain OBJ local's own reference. Removes +1/-1 pairs with nothing in between that can run code. Gain on binary-trees estimated 3 to 8%, not measured.
    • Tests: test_alloc_preserving.py (3 generated-C tests red on develop, observed in run 43362634405; 12 behaviour tests vs the interpreter; 3 mutants). Green on all 5 jobs: run 43409361265 (merged head 9bcc2f8). A first Windows run did not catch the copy mutant (function-like -D macro under cl.exe); fixed with an object-like switch.
    • Design 4.3.4 바 lists every other candidate with CPython v3.15.0rc1 references.
    • Next step in review: TypedPython: read the Python frame depth once per wrapper call (#125) #412 (Python frame depth read once per wrapper call).

    Stays open: the quiet-window measurement, and the per-call depth step.

  12. added a commit that references this issue on Nov 13, 2026
  13. b-re-w commented on Nov 13, 2026

    @b-re-w
    MemberAuthor

    Per-call depth step landed in develop via #412 (merge 10bad50). PyThreadState_GetFrame's frame walk now runs once per wrapper call (reset around the impl call, so a nested wrapper's return re-measures where develop's cache swapped); Py_GetRecursionLimit and Py_EnterRecursiveCall stay per frame (a del can change the limit mid-call; 3.15's check is a C-stack check). Design 4.3.3b. CI: run 43467463250 on the merged head d0ce2e9, all 5 jobs green; cgen-only tests red on develop observed as plain Python. Gain estimated about 5%, not measured.

    Still open on #125: a quiet-window binary-trees measurement of #405 + #412 against the earlier develop, and the two identity gaps found while reading (a pure-Python frame above compiled frames counts only its own frames; a callback's locals can be freed late), raised to the leader.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions