Skip to content

TypedPython stage 2: typed IR lowered to C (replaces the Cython backend) #41

Open
Open
TypedPython stage 2: typed IR lowered to C (replaces the Cython backend)#41
Milestone
TypedPython: M2 IR to C on desktop

Description

@b-re-w
b-re-w
opened on Oct 2, 2026

What

TypedPython stage 2, starting now and replacing the Cython backend (maintainer decision 2026-10-03: "Cython 의존 별로야. 2단계로 바로 진행"). The pipeline:

  1. Front end: the Pyrefly inference the gate already runs (expression types plus probed assignment targets) and the AST produce a typed IR (typedpython/ir.py).
  2. Back end: the IR is turned straight into C that uses the CPython C API, and compiled into a CPython extension with the platform's own C compiler (clang for desktop now; NDK and Xcode in M3 through pypackpack).
  3. Order:
    • scalar int/float/bool code and calls between compiled functions;
    • list[float]/list[int] lowered to native arrays;
    • fixed-layout classes.

Why C, not LLVM

  • Every target already ships a C compiler (clang, NDK, Xcode), so this adds no new dependency and no LLVM build per platform.
  • C debugs with the platform's own tools, and the CPython C API is a C API.
  • LLVM would add little at this stage: the C compiler already gives the optimisations that matter for typed scalar code and arrays (inlining, vectorisation).
  • A later LLVM path stays open: the IR is the stable layer, and C is one back end of it.

Semantics (unchanged contract, INTENT §1.4: same results as CPython)

These carry over from #39:

  • int is i64 behind an entry range check. Pure functions use checked arithmetic, and on overflow the call is redone by the interpreted module.
  • A runtime argument type other than the declared one takes the interpreted path.
  • Python's floor division and modulo hold, and so do its exceptions (ZeroDivisionError, math domain and range errors).

New in this issue:

  • Native arrays: a list[float] parameter is copied into a C array at entry when the call cannot observe it otherwise. That means no calls out, no aliasing between list parameters (checked by identity at entry, falling back before any effect), and every element exactly float at entry. The array is written back on every exit, including exceptions.

Done when (M2)

  • python -m typedpython demo runs on the new back end, and its output is identical to the interpreted run for all five benchmarks.
  • nbody and spectral-norm run ≥ 10× faster than CPython, measured alone.
  • Differential tests compare compiled and interpreted results over integer and float edge cases: overflow boundaries, negative floor division and modulo, division by zero, NaN and inf.

M2 completion criterion (leader decision, 2026-10-03)

  • All 5 benchmarks give output identical to CPython through run.py verify --typedpython ... and demo.
  • nbody, spectral-norm and fannkuch-redux actually compile (their hot functions are in compiled, not skipped). fannkuch needs fixed-size local list[int] arrays and a tuple return, both in M2.
  • binary-trees (recursion, classes) is M2b (TypedPython: compile recursion (direct and mutual) with CPython's RecursionError #57, 2026-11-21); wordfreq (dict/str) is outside November.
  • nbody and spectral-norm ≥ 10× CPython, measured alone (load ≈ 1, median of 5, unfiltered, time and load reported).
  • Incremental cache wired into the pipeline; ASan/UBSan in CI.

Activity

  1. b-re-w
    added this to the TypedPython: M2 @compiled on desktop milestone on Oct 2, 2026
  2. b-re-w
    added 14 commits that reference this issue on Oct 2, 2026

    Spec: TypedPython compilation, IR-level safety proof, incremental builds

    e9fe49e

    Spec: Fix the C runtime API the generated code may call

    c2c80fc

    Docs: Record the IR-to-C backend, IR safety proof, incremental builds…

    6492bed

    Spec: Let compiled code call Kotlin through opaque Python objects

    6110e47

    Spec: Settle IR ambiguities found by the verifier

    9d8edcf

    Spec: Proven i64 ops, callee-only redo, entry snapshots of globals

    957315e

    Fix: Put Function.entry_globals after the fields without defaults

    ac366e9

    Feat: Front end records proven i64 ops, redo calls and entry globals

    4c26827

    Feat: Verifier re-proves proven ops, redo calls and entry globals

    f34e238

    Feat: C back end for proven ops, redo calls and entry globals

    8e650c1

    Spec: Record the proven/redo/entry-globals rules the verifier enforce…

    43638b2

    Bench: Run the TypedPython @compiled column through the pipeline

    a6f0d37

    Spec: Local fixed-size arrays and tuple returns in the IR (fannkuch, M2)

    513f10f

    Feat: Incremental TypedPython builds (pipeline.compile_project, typed…

    fc03e83

  3. 1 remaining item

  4. b-re-w
    added 7 commits that reference this issue on Oct 3, 2026

    Feat: Verifier proves local arrays and tuples

    eb4dcb8

    Feat: Front end lowers local arrays and tuple returns (fannkuch)

    ae67e09

    Feat: Runtime helpers for local arrays and tuples

    64a7744

    Feat: C back end for local arrays and tuples

    95d96d4

    CI: Plant the ASan self-check fault in the redzone and show the repor…

    82f6d7c

    CI: Let the ASan self-check case reach ASan

    9a16536

    Bench: Official interleaved A/B result for M2 (2026-10-03 18:46)

    4634d51

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

    @b-re-w
    b-re-w
    on Oct 3, 2026
    MemberAuthor

    M2 complete (criteria in this issue): outputs identical on all 5 benchmarks; nbody, spectral-norm, fannkuch compiled; interleaved A/B measurement (PR #92, 11 pairs each, load 12–36 during pairs) — median vs CPython: nbody 28.5x, spectral-norm 17.9x, fannkuch 29.2x; incremental cache wired; ASan/UBSan CI green. A quiet-window absolute measurement will supplement it.

  6. b-re-w
    closed this as completedon Oct 3, 2026

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

    @b-re-w
    b-re-w
    on Oct 3, 2026
    MemberAuthor

    Quiet-window re-run on develop e888e7f (2026-10-03 22:04). The window opened when the 5-minute load had stayed at or below 1.5 for 10 minutes; load during the pairs was 1.9 to 2.4. Hardware: macOS arm64; CPython 3.14.7.

    Interleaved A/B, 11 pairs, ratio = CPython time / compiled time:

    benchmark median range
    nbody 31.3x 11.4 to 31.5x
    spectral-norm 6.3x 3.8 to 6.4x
    fannkuch-redux 23.5x 10.3 to 23.7x
    wordfreq 1.1x 0.9 to 1.1x
    binary-trees n/a this commit predates N-11 (#124)

    Conventional measurement, median of 5 runs, absolute times:

    • nbody: compiled 0.129 s; CPython 3.929; Node 0.117; Java 0.141; Rust 0.059.
    • spectral-norm: compiled 0.518 s; Node 0.068.
    • fannkuch-redux: compiled 0.250 s; Node 0.261; Rust 0.249.

    In the quiet window spectral-norm's range narrowed to 3.8 to 6.4x (the earlier loaded runs spread from 1.2 to 34x), and its median is 6.3x. It is still the benchmark furthest from Node, about 7.6x slower, which needs its own look. binary-trees with __slots__ and the no-slots CPython baseline will be in the next window, now that #124 is on develop. Raw JSON: benchmarks/typedpython/results/2026-10-03-* in the measurement worktree.

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

    @b-re-w
    b-re-w
    on Oct 3, 2026
    MemberAuthor

    Reopened: the quiet-window interleaved measurement (develop e888e7f, load 1.9–2.4) gives spectral-norm 6.3x vs CPython (range 3.8–6.4x), below the 10x criterion. The earlier 17.9x was taken under load 12–36 and was not reliable. nbody 31.3x and fannkuch 23.5x meet it.

  9. b-re-w
    reopened this on Oct 3, 2026

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

    @b-re-w
    b-re-w
    on Oct 3, 2026
    MemberAuthor

    spectral-norm 6.3x, plan (agreed with the leader). Everything below is a hypothesis from reading the generated C, not yet profiled.

    • mul_atav is not the cause: it stays interpreted, but it only calls the compiled mul_av/mul_atv 40 times. The hot path is eval_a, called 25.6M times from compiled loops.
    • Per-call costs:
      1. tp_enter_call/tp_leave_call (TLS, tp_python_depth(), Py_GetRecursionLimit());
      2. probably no inlining of tp_impl_eval_a;
      3. six checked i64 operations plus tp_floordiv_i64;
      4. a bounds check per v[j].
    • Step 1: profile to split the time across these four.
    • Candidate fix for (1): a callee outside every call cycle adds at most k frames, with k known statically.
      • A precheck depth + k <= limit at the cycle entry or wrapper selects a fast entry that skips enter/leave.
      • If the precheck fails, the call runs the normal per-call path, never an early RecursionError, so the point where CPython raises stays exactly the same.
      • Tests compare against the interpreter at every depth between limit-k and limit. A mutation that takes the fast path despite a failed precheck must fail them.
    • Re-check 10x with the interleaved method at load around 2.

  11. b-re-w commented on Oct 17, 2026

    @b-re-w
    b-re-w
    on Oct 17, 2026
    MemberAuthor

    spectral-norm after #210 (fast entry): 59.4x against CPython (interleaved median, quiet window, 2026-10-17), above the M2 10x criterion. nbody does not compile on develop since #209 (more than two list parameters); being decided separately.

  12. b-re-w commented on Oct 17, 2026

    @b-re-w
    b-re-w
    on Oct 17, 2026
    MemberAuthor

    Interval proofs alone (#148, landed via #218): gain about 0. Interleaved, quiet window: fannkuch 0.997 and binary-trees 1.001 against develop. The removed checks were well-predicted branches. The checks left in spectral-norm (eval_a) and wordfreq come from full-range function parameters, so cutting them needs facts across function boundaries (the callers' ranges), not more local analysis.

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

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions