{"article":{"slug":"adapting-cpython-for-yk","title":"Adapting CPython for yk","subtitle":null,"summary":"Laurence Tratt describes ykifying CPython: using the yk meta-tracing system to add a JIT compiler to the large CPython interpreter, walking through optimising interpreter dispatch, tracing, unrolling and indirect inlining, and showing ykcpython can be surprisingly competitive on performance.","content_type":"research","language":"en","canonical_url":"https://tratt.net/laurie/blog/2026/adapting_cpython_for_yk.html","author":{"name":"Laurence Tratt","url":"https://tratt.net/laurie/","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Laurence Tratt's blog","url":"https://tratt.net/laurie/blog/","listing_slug":null,"listing":null},"topics":[{"name":"compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"},{"name":"performance","slug":"performance","url":"https://listedarticles.com/topics/performance"},{"name":"programming-languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"},{"name":"research","slug":"research","url":"https://listedarticles.com/topics/research"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":6157,"reading_minutes":27,"published_at":"2026-11-12T12:10:00.000Z","added_at":"2026-11-12T23:08:38.494Z","updated_at":"2026-11-12T23:08:38.494Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/adapting-cpython-for-yk","markdown_url":"https://listedarticles.com/articles/adapting-cpython-for-yk.md","example":false,"citation":"Laurence Tratt, Laurence Tratt's blog. \"Adapting CPython for yk.\" 12 Nov 2026. https://tratt.net/laurie/blog/2026/adapting_cpython_for_yk.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://tratt.net/laurie/blog/2026/adapting_cpython_for_yk.html"},"body_markdown":"# Adapting CPython for yk\n\nEarlier this year I [wrote a post on\nyk](https://tratt.net/laurie/blog/2026/retrofitting_jit_compilers_into_c_interpreters.html),\nwhich can automatically add JIT compilers to C interpreters. Since then we’ve\napplied yk to more interpreters, fixed various bugs, and improved\nperformance notably. Towards the end of October I showed some data where on our\nbenchmark suite[1] yklua is 2× faster than the PUC Lua interpreter it takes as a\nbase.\n\nI was quite pleased with myself until someone brought me down to earth by\nasking “how do you know if this works for large interpreters?” It’s a fair\nquestion: PUC Lua is at least an order of magnitude smaller[2] than CPython or CRuby and who’s\nto say if it would work with much bigger interpreters? We had looked at CPython a year or so ago, but\nat that point yk was missing several obvious things that CPython would need, so\nwe quickly moved on. A lot has changed since then, and a quick LLM experiment\ngot far enough to suggest it would be worth looking again.\n\nHappily, having taken a deeper look, CPython not only works when adapted for yk\nas [ykcpython](https://github.com/ykjit/ykcpython)[3], but there are\nmeaningful performance gains to be had — not only relative to normal CPython,\nbut also relative to Python’s experimental JIT[4]. Roughly speaking,\nthis is the result of 3-4 days’ work on ykcpython directly; there was a separate\nweek and a half of generic yk bug fixing necessary to get to the point that I\ncould look at ykcpython itself.\n\nHere are the “final” numbers from my brief odyssey on ykcpython and the AWFY\nbenchmark suite:\n\n|  | cpython | cpython\\_jit | ykcpython |\n| --- | --- | --- | --- |\n| Bounce | 19.27±0.20 | 11.09±0.05 | **10.09±0.04** |\n| CD | 32.21±0.23 | **26.10±0.08** | 29.33±0.16 |\n| DeltaBlue | 7.43±0.02 | **6.21±0.02** | 7.62±0.04 |\n| Json | 11.81±0.08 | 10.93±0.05 | **9.98±0.03** |\n| List | 15.01±0.22 | **8.10±0.05** | 10.44±0.09 |\n| Mandelbrot | 11.66±0.28 | 6.94±0.27 | **4.20±0.07** |\n| NBody | 18.97±0.13 | 12.77±0.12 | **10.98±0.02** |\n| Permute | 22.97±0.34 | **17.95±0.13** | 21.04±0.05 |\n| Queens | 13.18±0.14 | 9.65±0.11 | **8.32±0.03** |\n| Richards | 54.80±0.20 | 40.56±0.40 | **33.18±0.17** |\n| Sieve | 23.34±0.06 | 17.02±0.07 | **13.74±0.06** |\n| Storage | 22.03±0.19 | 19.94±0.08 | **19.67±0.04** |\n| Towers | 20.46±0.25 | **12.65±0.05** | 13.67±0.04 |\n\nIn this table `cpython` is “normal” CPython 3.15.1; `cpython_jit` is CPython\n3.15.1 with the experimental JIT turned on; and `ykcpython` is commit\n[31b4d387](https://github.com/ykjit/ykcpython/commit/31b4d3875a9a63184546d7065863d42b4e24c2fc).\nTimes are in seconds (lower is better) with means and 99% confidence intervals bootstrapped from 30 process\nexecutions, running on a 64 core AMD EPYC 7773X Debian machine in `performance`\nmode ([download the repeatable experiment and the raw\ndata](https://tratt.net/laurie/blog/extra/2026/adapting_cpython_for_yk/adapting_experiment.tgz)).\nOn each row the fastest entry(s) are shown in bold.\n\nA simple summary of the table is: `ykcpython` is faster than `cpython` on every\nbenchmark except DeltaBlue (where it’s about 2.5% slower); and faster than\n`cpython_jit` on 8 out of 13 benchmarks.\n\nThe point of this post is not to pretend that ykcpython is in any way ready for\npeople to use — it definitely is not! Nor is it to pretend that one can\nexpect performance on a wider set of programs to be as good as the numbers\nabove — it definitely won’t! My view is that benchmark suite performance\nis a hoop to jump through rather than an end in itself: a system which\nbenchmarks well might perform poorly in the real world; but a system which\nbenchmarks poorly nearly always performs poorly in the real world.\n\nRather, I wanted to use this post as a way of showing what it’s like to adapt\nan interpreter for yk[5]: the stages I went through; and to give a sense\nof how the just under 450LoC I added were enough to achieve a meaningful\neffect. Luckily I had a sense that this might be a useful journey, so I was\nable to write enough stuff down to be able to flesh out this full post.\n\n## A quick refresher\n\nIf you haven’t read [the earlier yk\npost](https://tratt.net/laurie/blog/2026/retrofitting_jit_compilers_into_c_interpreters.html),\nhere’s a very brief refresher. Given a lightly modified C interpreter[6]\nas input, yk produces a VM with a meta-tracing JIT compiler as output[7].\nyk doesn’t aim to produce the fastest possible JIT compiling language\nimplementation: rather, it aims to make the language implementation you know and love\nsomewhat faster while retaining 100% compatibility. Put another way a “ykified”\ninterpreter is a fork of the existing C version of the interpreter, with\n(hopefully!) a handful of adjustments.\n\nAs with any meta-tracing JIT compiler, yk identifies *hot* loops in the *guest*\nlanguage (e.g. Lua or Python), and *traces* the interpreter (i.e. records what\nthe C code is executing while it is interpreting the guest language). It then\noptimises those traces and converts them to machine code.\n\nyk requires interpreters to tell it where potential loops in the guest language are via\nthe `YkLocation` struct. Optionally – though if you want to get good\nperformance, definitely necessary! – interpreter authors can add *optimisation hints* that\nembed knowledge about the language or its common idioms of use such as “at\nthis point this seemingly dynamic value almost never changes”. In general,\nworking out where to put `YkLocation`s is relatively easy, but working out where to\nput hints requires a much greater understanding of the interpreter, and careful\nmeasurement to understand which do and don’t help.\n\nThe challenge I face when adapting an interpreter for yk is that I rarely know\nthe interpreter well, if at all. Rather than trying to do everything at once, I\nhave learnt to start off as simple as possible: I try and do the minimum\nchanges that lead to some traces being recorded and compiled to machine code.\nThis can be trickier than it seems: I’ve got to understand the build system[8], and work out where to put some semi-sensible `YkLocation`s.\nI’ve also learnt to make sure that the language’s test suite works from this very\nfirst step: keeping it working thereafter is not only much easier, but it\nlessens the number of times one attempts optimisations that are unsound.\n\nFor a simple interpreter, you might get a basic JIT compiler from an\ninterpreter with fewer than 10LoC (Lines-of-Code) changed. For somewhat bigger\ninterpreters, a few more changes tend to be necessary. For example, yk doesn’t\nlike “threaded” interpreters that use `goto` between opcodes, because it\ndoesn’t give it enough opportunities to intercede and see what’s going on.\nFortunately, such changes are not generally too big.\n\n## Finding the right starting point\n\nSince it had been a long time since I looked at CPython’s internals[9],\nI started with the part I was vaguely familiar with. As I later discovered, this is now called the “tier 1” interpreter.\nQuickly hacking in support for yk highlighted several missing things in yk\n(from [basic atomic loads](https://github.com/ykjit/yk/pull/2426) to\n[not-implemented-bit-widths in `sub`](https://github.com/ykjit/yk/pull/2418),\nminor incompatibilities (e.g. [reading an environment variable after a CPython\ntest had wiped it](https://github.com/ykjit/yk/pull/2441)), and flat out bugs\n(from [stackmap fixes](https://github.com/ykjit/ykllvm/pull/374/changes) to\n[not doing silly things after `fork`](https://github.com/ykjit/yk/pull/2438)).\nFixing all those took me around a week and a half; I’m not going to talk about\nthem in detail in this post, because they’re generic fixes that aren’t\nykcpython specific.\n\nMy [adaption of the tier 1\ninterpreter](https://github.com/ykjit/ykcpython/pull/11) is deliberately\nminimalistic. Most of the changes in the 200LoC diff are small one-offs that\naren’t hugely interesting: we need CPython to use its (builtin but non-default)\n`switch`-based interpreter; and yk uses a shadow stack, so CPython’s C stack\nresizing needs to take that into account too. The most interesting thing I did\n[was to add `YkLocation`s at backwards jump opcodes](https://github.com/ykjit/ykcpython/pull/11/changes#diff-6f869eb8beb7cbe4bc6817584b99ad567f88962fa67f7beca25d009dc401234dR603),\nwhich I expected to be enough for some half-sensible traces to be created.\n\nI wasn’t expecting this first version of ykcpython to be faster\nthan CPython – if nothing else, it contained almost no optimisation hints – but it was\n*much* slower than I expected. It was definitely creating traces, and they were\nexecuting correctly – the test suite passed, albeit taking more memory\nthan I’d like[10] – but something clearly wasn’t right.\n\nFortunately, it didn’t take very long to work out what. 4 years ago, CPython\nadded support for [*quickening*](https://peps.python.org/pep-0659/) under the\nheading of “specialisation”. Quickening is a simple, clever technique for\n[improving interpreter\nperformance](https://www.unibw.de/ucsrl/pubs/ecoop10.pdf/@@download/file/ecoop10.pdf)\nthat rewrites “generic” opcodes (e.g. “add objects”) to “specialised”, faster,\nopcodes (e.g. “add two ints”) when possible, deoptimising back to the generic\nopcodes if necessary. I tend to think of quickening as giving a decent portion\nof the benefit of a JIT compiler without all the bother of generating machine\ncode[11]. The problem for yk is that sometimes a program’s opcodes\ncan transition between specialised and unspecialised opcodes a large number of times,\nand the simple way I’d added yk support meant that each transition implicitly\nthrew away the associated trace and created a new one. In most cases, traces weren’t\nused long enough to overcome the cost of creating them.\n\nThere are techniques which can overcome this problem, and I did briefly\nexperiment with them, but I then recalled a conversation I had with some\nCPython developers last year. A quick look inside CPython confirmed my\nrecollection: CPython contains a “tier 2” interpreter as well. This isn’t a\ncompletely new interpreter; rather it is an alternative implementation of core\nparts of the main interpreter loop, mostly intended for CPython’s experimental\nJIT compiler.\n\nA very quick experiment later suggested that the tier 2 interpreter was – at\nleast at a basic level – a better fit for yk[12]. I thus ripped out\nthe tier 1 support and added [support for yk in the tier 2\ninterpreter](https://github.com/ykjit/ykcpython/pull/12). Happily, tier 2\nsupport is even easier than tier 1 support, consisting of a mere [80\nLoC](https://github.com/ykjit/ykcpython/pull/12/changes/06e91ccc5a34cb8be58a398413c56e92b5b534eb).\nTo give you a quick idea of what yk support looks like, here’s the part that\nattaches `YkLocation`s[13] to the (start of) loops:\n\n```\nfor (uint32_t i = 0; i < executor->code_size; i++) {\n  const _PyUOpInstruction *uop = &executor->trace[i];\n  if (_PyUop_Uncached[uop->opcode] == _JUMP_TO_TOP) {\n    uint16_t target = uop_get_jump_target(uop);\n    if (yk_location_is_null(executor->yk_locs[target])) {\n      executor->yk_locs[target] = yk_location_new();\n    }\n  }\n}\n```\n\nFor the rest of this post, I’m going to be using yk and the tier 2 interpreter as the\nstarting point for ykcpython.\n\n## What’s being benchmarked\n\nWhen optimising any language implementation, it’s important to know where its\nperformance sits in the wider performance landscape. To understand how\nykcpython was doing, I used two other baselines: “stock” CPython; and CPython\nwith the experimental JIT. I configured `cpython` as follows:\n\n```\nCC=clang-21 CXX=clang++-21 \\\n  ./configure \\\n  --enable-optimizations \\\n  --with-lto\n```\n\nNote that I’m deliberately using the same version of LLVM for both `cpython`\nand `cpython_jit` because the latter requires LLVM-21. ykllvm – the fork of\nLLVM used in yk – is [based off a version of LLVM about 6 months\nlater](https://github.com/ykjit/ykllvm/pull/312) than LLVM-21. That might\nslightly distort comparisons, but it’s a small enough difference that the\neffects hopefully are fairly minor. Bearing that in mind, `ykcpython` is\nconfigured as follows:\n\n```\n../configure \\\n  --without-computed-gotos \\\n  --without-tail-call-interp \\\n  --enable-experimental-jit=interpreter \\\n  --without-ensurepip\n```\n\nI used [our fork](https://github.com/ykjit/yk-benchmarks/tree/main/suites/awfy/Python)[14] of the [AWFY](https://github.com/smarr/are-we-fast-yet) benchmark\nsuite, simply because I know how to run it without thinking.\n\nThe next challenge is to define a metric, or metrics, to report performance.\nEvery metric has the potential to mislead and\nmany are difficult to understand. In my opinion, the least worst single metric\nis wall-clock time: how long does my program take to run from start to\nfinish? This doesn’t capture everything we want to know, but it captures a lot,\nand it’s easy to understand.\n\nMost importantly this metric implicitly includes [start-up and warm-up\ntime](https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_mount_tratt__virtual_machine_warmup_blows_hot_and_cold_v6/).\nIn other words I’m deliberately choosing a timing metric which tends to favour\nnormal interpreters and “penalise” JIT compilers. To somewhat offset that, we\nrun each AWFY benchmark for 10 in-process iterations (i.e. run the whole\nbenchmark in a `for 0..10` loop) so that we also get some sense of how\noptimisation benefits longer-running programs.\n\nThe big performance table at the start of this post uses a custom benchmark\nrunner on an idle machine. All the timings from now on in the post are from me\nrunning `time` once as a normal user without being too careful if the machine\nis completely idle or not: when starting to optimise an interpreter, it’s not\npractical to wait an hour to benchmark every change on many benchmarks, when\nthe effects are generally quite large[15].\n\n## Optimising interpreter dispatch\n\nThere are various ways one can go about optimising an interpreter for\nmeta-tracing, all of which have pros and cons: the sequence of optimisations\nI’m showing here is just one way of going about things[16].\n\nLet’s start with the [mandelbrot\nbenchmark](https://github.com/ykjit/yk-benchmarks/blob/main/suites/awfy/Python/mandelbrot.py)\non `cpython`:\n\n```\n$ time cpython harness.py Mandelbrot 10 500\nStarting Mandelbrot benchmark ...\nMandelbrot: iterations=1 runtime: 1166072us\nMandelbrot: iterations=1 runtime: 1163564us\nMandelbrot: iterations=1 runtime: 1166220us\nMandelbrot: iterations=1 runtime: 1164960us\nMandelbrot: iterations=1 runtime: 1166583us\nMandelbrot: iterations=1 runtime: 1166431us\nMandelbrot: iterations=1 runtime: 1168500us\nMandelbrot: iterations=1 runtime: 1168757us\nMandelbrot: iterations=1 runtime: 1165289us\nMandelbrot: iterations=1 runtime: 1170343us\nMandelbrot: iterations=10 average: 1166672us total: 11666719us\n\nTotal Runtime: 11666719us\ncpython/python harness.py Mandelbrot 10 500  11.67s user 0.01s system 99% cpu 11.687 total\n```\n\nIn other words, I ran the benchmark with 10 in-process iterations and a\nparameter of 500. The AWFY harness prints out how long each iteration took. As\nis common – but definitely not universal! – for an interpreter, `cpython`\nhad fairly consistent times from one iteration to the next.\n\nFor this benchmark, `cpython_jit` takes 6.746s (0.58× CPython) and `ykcpython`\ntakes a whopping 13.70s (1.17× CPython)[17]:\n\n```\n$ time ykcpython harness.py Mandelbrot 10 500\nStarting Mandelbrot benchmark ...\nMandelbrot: iterations=1 runtime: 1488078us\nMandelbrot: iterations=1 runtime: 1353013us\nMandelbrot: iterations=1 runtime: 1354018us\nMandelbrot: iterations=1 runtime: 1350854us\nMandelbrot: iterations=1 runtime: 1351681us\nMandelbrot: iterations=1 runtime: 1351815us\nMandelbrot: iterations=1 runtime: 1351454us\nMandelbrot: iterations=1 runtime: 1352860us\nMandelbrot: iterations=1 runtime: 1352099us\nMandelbrot: iterations=1 runtime: 1352516us\nMandelbrot: iterations=10 average: 1365839us total: 13658388us\n\nTotal Runtime: 13658388us\nykcpython/build-yk/python harness.py Mandelbrot 10 500  13.94s user 0.07s system 102% cpu 13.691 total\n```\n\nThere are a couple of useful things to notice here. First, we can see warm-up\noccurring: `ykcpython`’s first iteration is slower than subsequent iterations.\nThat’s OK in my book: yk isn’t really intended for programs running in a\nfraction of a second. Second, the `102% cpu` and user time\nthat is higher than wall-clock time are due to yk running trace compilation in threads.\nThat allows the interpreter to continue executing, reducing perceived pauses.\n\nThe first thing I do in this situation is look at the “high-level IR” (HIR) of\nthe traces that yk has produced to see if things look sensible:\n\n```\n$ YKD_LOG_IR=/tmp/l1:hir ykcpython harness.py Mandelbrot 10 500\n...\n$ rg Begin /tmp/l1 | wc -l\n11\n$ rg Loop /tmp/l1 | wc -l\n1\n```\n\nThe logfile contains 11 traces, of which 1 is a “loop” trace. In general,\nloop traces are where yk is most effective, and the non-loop traces are\nthe price we have to pay to get the promised land of loop traces. In this\ncase, a simple profile showed that most execution time is spent in the\nsolitary loop trace, which is a promising start for yk.\n\nAt this point, doing much more with the HIR than this high-level analysis is\ndifficult, because the output is 20,772 lines of this sort of thing:\n\n```\n%68: ptr = 0x13D581D4\n%69: i8 = 0\nstore %69, %68\n%71: i16 = load %64\n%72: i32 = zext %71\n%73: i32 = 32767\n%74: i32 = and %72, %73\n%75: i16 = trunc %74\n%76: ptr = 0x13D58218\n%77: ptr = load %76\n%78: ptr = 0x0\n%79: i1 = icmp eq %77, %78\nguard false, %79, [%0, %2, %2, %3, %4, %5, %6, %7, %8, %9, %10, %11, %12, %13, %14, %15, %16, %17, %18, %19, %20, %21, %22, %23, %24, %25, %26, %27, %28, %29, %30, %31, %32, %33, %34, %35, %36, %37, %38, %39, %40, %41, %42, %43, %44, %45, %64, %74, %75, %78, %56, %49, %50, %51, %52, %53]\n```\n\nEven if you’re used to this syntax and way of thinking, it can be incredibly\nhard to see the forest for the trees: there’s just too much *stuff*. And that\nisn’t just a problem for humans (or AIs) reading this: more HIR means more\nmachine code which implies slower execution.\n\nMy first port of call when optimising an interpreter is to tackle interpreter\ndispatch. When an interpreter is executing a program, it continually asks “what\nis the opcode of the current instruction? Is it an `add` or a `sub` or …?”\nand then it *dispatches* to the code that performs the appropriate action. It’s\nprobable that a large chunk of that 20KLoC of HIR is the interpreter loading an\nopcode from memory and checking what kind it is. yk’s trace optimiser has\nvarious classic compiler tricks up its sleeve, but in this case they don’t\nreally help, because in most cases between the same instruction being loaded\ntwice from memory, some other code will be called that yk has to assume might\nhave mutated that memory. This isn’t unnecessary conservatism: Python programs\nreally can mutate their function’s instructions!\n\nI was particularly lucky because the tier2 interpreter uses “executors” which\nare traces of (optimised) instructions. Those instructions are immutable in the\ncontext of a given executor: should a Python function’s instructions change,\nany associated executors will be invalidated. That means that we can attach a\nsimple monotonically increasing integer *code ID* to a `_PyExecutorObject` and\nknow that for a given code ID, an opcode at index *I* will always be the same.\n\nThis allows us to use the single most effective optimisation hint in yk:\nidempotent functions. In essence, an idempotent function says “for the same\ninputs this function will always produce the same output”[18].\n“Always” here really means “always”! Idempotent is a *very* strong guarantee\nthat yk cannot help you uphold: if you fail to do so, your system will go wrong\nin weird ways.\n\nAlthough yk provides a helper `yk_idempotent_load` function, we need something\nmore specialised. Fortunately it’s not hard to write what we need:\n\n```\n__attribute__((yk_idempotent))\nuint16_t idempotent_load_opcode(uint64_t code_id, const _PyUOpInstruction *pc)\n{\n    __asm__ volatile(\"\" : \"+r\"(code_id));\n    return pc->opcode;\n}\n```\n\nUnsurprisingly, the `yk_idempotent` attribute tells yk that\n`idempotent_load_opcode` is an idempotent function. That means that if, in a\nparticular trace, the function is called with parameters that are constant\nvalues then yk can remove the idempotent function call and replace it with its\noutput. The `__asm__` line is there to encourage LLVM not to inline the\nfunction[19] (if the function is inlined, yk no longer knows there is\nanything idempotent there).\n\nUsing this requires [changing just a few lines in the core\ninterpreter loop](https://github.com/ykjit/ykcpython/pull/13). The most important\nlines are simply this:\n\n```\nyk_promote(next_uop);\nyk_promote_code_id(yk_code_id);\nuopcode = idempotent_load_opcode(yk_code_id, next_uop);\n```\n\nPromotion (e.g. `yk_promote`)[20] says “this variable is expected to be\nsemi-constant: record its concrete value and specialise the trace to it, but\ninsert a guard in case that value later changes”. Imagine I have\n`yk_promote(x)` and when a trace is later recorded, `x` happens to be `3`. The trace\nwill record `guard true (x == 3)`: if on later runs `x` is not `3`, the guard\nwill fail and the trace will deoptimise; if the guard succeeds we know henceforth\nthat `x` is definitely `3`.\n\nIn other words, in the context of the traces we’re recording, yk will see calls\nto `idempotent_load_opcode` with constant arguments, allowing it to replace the\nfunction call with a constant result. The point of this isn’t just to remove\nthe cost of a load: rather, exposing constant data to yk’s trace optimiser allows it to\ndo a much better job of optimising traces. The effect in this case is quite\nsomething:\n\n```\n$ time ykcpython harness.py Mandelbrot 10 500\nStarting Mandelbrot benchmark ...\nMandelbrot: iterations=1 runtime: 606714us\nMandelbrot: iterations=1 runtime: 485324us\nMandelbrot: iterations=1 runtime: 485994us\nMandelbrot: iterations=1 runtime: 484999us\nMandelbrot: iterations=1 runtime: 483824us\nMandelbrot: iterations=1 runtime: 485431us\nMandelbrot: iterations=1 runtime: 484752us\nMandelbrot: iterations=1 runtime: 486160us\nMandelbrot: iterations=1 runtime: 486125us\nMandelbrot: iterations=1 runtime: 483481us\nMandelbrot: iterations=10 average: 497280us total: 4972804us\n\nTotal Runtime: 4972804us\nykcpython/build-yk/python harness.py Mandelbrot 10 500  5.09s user 0.08s system 103% cpu 5.005 total\n```\n\nIn other words, that simple change has not only made `ykcpython` 2.7× faster,\nbut it is now 0.43× `cpython` and 0.74× `cpython_jit`! In other words, a simple\nPR that changes 30LoC has made this benchmark over twice as fast as CPython and\n25% faster than CPython’s JIT. Another way of judging the effectiveness of this\noptimisation is that it has reduced the 20,772 lines of HIR output to 7,648\nlines[21].\n\n## Code needs to be traced to be optimised\n\nHowever, before we get carried away, this isn’t enough to make all benchmarks\nmagically quicker. I have learnt from experience to rotate between benchmarks\nto avoid over-training[22]. In this case I decided to look at the\ndeltablue benchmark, which I know from yklua can be a tough target.\nThe situation in ykcpython turned out to be worse than I expected: `cpython` takes 7.67s,\n`cpython_jit` takes 6.20s, and `ykcpython` (with our idempotent change) takes\n37.51s. Ouch!\n\nMy next port of call is to run `YKD_LOG=2` which prints warnings if a trace\ncan’t be compiled. Sure enough:\n\n```\n$ ykcpython harness.py DeltaBlue 10 12000\nStarting DeltaBlue benchmark ...\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nDeltaBlue: iterations=1 runtime: 3362822us\nyk-warning: trace-compilation-aborted: Unimplemented: '%188 = atomicrmw or ptr %187, i64 16 seq_cst, align 8'\n...\n```\n\nFor now I’m going to skip “trace too long”. In essence yk has a fixed limit for\n“this trace looks to be so long that it’s probably not useful”. The limit was\ntoo low, so I [increased it unilaterally](https://github.com/ykjit/yk/pull/2453)\nbefore doing the work for this post. Exactly what the right value is I don’t\nknow. Indeed, I think that this crude heuristic probably needs replacing with\nsomething more sophisticated: doing that is a problem for another day.\n\nLet’s move onto the “unimplemented” warning: I haven’t got around to\nimplementing complex atomic instructions yet, so as soon as one of those is\nencountered, yk has no choice but to give up on that trace entirely. If it\nhappens to be a hot part of a benchmark, that can absolutely kill performance.\nIn this case, happily, the `atomicrmw` warnings just so happened to come from\nfunctions which we really don’t want to inline into the trace anyway.\n\nOne of tracing’s virtues is that it aggressively\ninlines functions, but that can inline checks which fail too often on\nsubsequent executions. For example, one function we inline by default is\n`_PyObject_GC_Link` which checks to see if enough objects have been allocated\nfor garbage collection to be worth scheduling. If we’re unlucky, we may trace\nan iteration of a loop which happens to schedule garbage collection: in nearly\nevery subsequent execution, the resulting guard will fail, and we’ll take a\nsomewhat slower path. The solution here is to mark such functions as\n`yk_outline`:\n\n```\n__attribute__((yk_outline))\nvoid _PyObject_GC_Link(PyObject *op) { ... }\n```\n\nFunctions marked `yk_outline` become `call`s in a trace. There are probably a\nnumber of functions which should be marked as `yk_outline`, but I\n[marked the two](https://github.com/ykjit/ykcpython/pull/14) that happened to\ncause the `aborted` warnings and that also obviously we don’t want to include\nin a trace anyway. Doing so improved execution time to 36.63s (about 2.5%\nfaster), so they’re clearly not the major cause of the slowdown in this case.\n\nJust when I was starting to fret, profiling execution showed that, to my\nsurprise, deltablue was only spending about half its running time in\nJIT-compiled code, where one would expect it to be spending 90%+. It turns out\nthat the main reason for this is that not all executors have a `_JUMP_TO_TOP`\nopcode and weren’t being traced.\n\nMy quick fix was to add a `YkLocation` at the first opcode in an executor. The\n[one line fix](https://github.com/ykjit/ykcpython/pull/15) does just that: it\nmeans that yk starts tracing as soon as it enters an executor. Doing so\nimproves deltablue’s execution time to 8.64s (4.23× faster than before). That’s\nstill 1.13× CPython, but it’s a lot better than before!\n\nAt the time I made this change I didn’t fully think about how adding a\n`YkLocation` at the start of an executor might interact with the `YkLocation`\nalready added to `_JUMP_TO_TOP`. As luck would have it, I accidentally stumbled\non a reasonable combination: `_JUMP_TO_TOP` tends to jump to the instruction at\nindex 1. Still, I suspect that there might be a better way to add `YkLocation`s\nto executors, but one can’t solve every problem all at once: it’s time to move\nonto the next thing!\n\n## Further into interpreter dispatch\n\nOur earlier use of idempotent loads made such a huge impact on interpreter\ndispatch that it’s easy to overlook that it was a simple, shallow, change: it\nonly optimised loading an instruction’s opcode kind. Instructions contain a\nnumber of other fields that are equally amenable to idempotent loading.\n\nThere are various ways one can go about optimising these additional fields. I\ncould, for example, have replaced the definitions of some `static` functions in\nheader files. To keep things simple, I defined a macro which can generate the\ntwo-parameter functions we need, and then nobbled some other macros to call it\nat appropriate points. With the [resulting change](https://github.com/ykjit/ykcpython/pull/16) deltablue’s performance\nimproves to 8.09s — we’re now within 10% of `cpython`’s performance.\n\n## Unrolling\n\nAs we saw earlier, not all functions are good candidates for inlining into a\ntrace. yk has a very simple heuristic – stolen shamelessly from RPython/PyPy\n– which is to mark functions containing loops as “outlined”. In other words,\nif C calls a function `f()` and `f` contains `for (...) { ... }` then yk\nwill not inline calls to `f`.\n\nThe fundamental reason not to inline functions-with-loops is that tracing\nunrolls loops, and that tends not to be a good idea. First, some loops execute\nvast numbers of iterations, which would cause counter-productively-long traces.\nSecond, loops’ iterations are often controlled by dynamic, ever-changing\nvalues: unrolling would specialise the trace to just one of those values, giving\nsuboptimal performance on every other value.\n\nThere are however a small number of functions in an interpreter which we\nactively want to unroll. Typically those functions’ loops satisfy two\nproperties: they only run a small number of iterations; and the number of\niterations depends on an aspect of the user’s program that changes rarely. For\nexample, a function called `unpack_args(int num_args)` which contains `for (int i=0; i<num_args; i++)` would be an excellent candidate, since it probably\nunpacks the same number of parameters every time it is called at the same place\nin a trace.\n\nyk thus provides a `yk_unroll` attribute, which informs yk that a function that\nmight otherwise be outlined should in fact be inlined and its loops unrolled.\nRather than slog through every function in CPython looking for candidates, I\ndid a simple grep/sort in hir to see which (implicitly non-inlined) C functions\nappear most often in traces[23]:\n\n```\n$ YKD_LOG_IR=/tmp/l1:hir ykcpython harness.py Json 10 100\n...\n$ rg call /tmp/l1|grep \"@\"|cut -d \"@\" -f 2|sort|uniq -c|sort -n\n   2 PyLong_FromLong\n   6 _Py_HandlePending\n   6 do_lookup\n  24 _PyList_FromStackRefStealOnSuccess\n  50 _PyEvalFramePushAndInit\n  50 _PyObject_GC_Link\n  50 _PyObject_InitInlineValues\n 263 PyLong_FromSsize_t\n1035 _PyFrame_Initialize.5328\n1158 _PyFrame_ClearLocals\n1194 bcmp\n```\n\n`bcmp` is the standard `libc` function: all of the other functions are in CPython itself.\nNot all of those functions will have loops in them, but the chances are that\nmost do. What I do in such a situation is go down (or, depending how you look at it,\nup) the list and look at the code in each function. I did that for a couple of\nbenchmarks to ensure I got some coverage of common functions.\n\nThe two most commonly called CPython functions immediately looked like good candidates.\n`_PyFrame_Initialize` is the most obvious of the two, containing almost exactly\nthe pattern I most like to match on:\n\n```\n_PyFrame_Initialize(..., int null_locals_from, ...) {\n  ...\n  for (int i = null_locals_from; i < code->co_nlocalsplus; i++) {\n    frame->localsplus[i] = PyStackRef_NULL;\n  }\n  ...\n}\n```\n\n`_PyFrame_ClearLocals` is slightly trickier: it contains a `while` loop involving pointer\narithmetic, but it didn’t take me long to convince myself that it was a good\ncandidate.\n\nEarlier we made `_PyObject_GC_Link` not inlineable, so we don’t want to reverse\nthat! Similarly, `do_lookup` looks values up in a dictionary, so we want to\nkeep that outlined: it depends on an often-changing dynamic value.\n\n`PyLong_FromSsize_t` and `PyLong_FromLong` were harder to judge. These\nfunctions’ inner loops depend on dynamic values, but my best guess is that they\ntend to be fairly stable in practice. I will be keeping an eye on these\nfunctions in the future, because I only have medium confidence that I made the\nright initial call.\n\nAs these examples suggest, I am generally fairly cautious about adding\n`yk_unroll`: inappropriate placings can easily help one benchmark and make many\nothers worse. I thus tend to only mark one or two functions as `yk_unroll`,\nbenchmark, and then move on. In this case, I did 5 small PRs, with the end\neffect that json went from 11.52s to 10.85s.\n\n## Indirect inlining\n\nIn general most function calls in C are *direct*: `f()` calls a function called\n`f`. However a minority of functions are *indirect*: `f` is a generic pointer\nwhose value can be any compatible function. This is commonly used in\ninterpreters to allow run-time dispatch to type specific code.\n\nBy default, yk cannot inline through indirect function calls, because without\nknowing exactly what pointer is being called, it can’t reliably reconstruct\nthe path that execution took[24]. Fortunately, we already have\nthe tool we need to solve this problem: `yk_promote`! If yk sees an indirect\nfunction call with a constant pointer it knows exactly what function is being\ncalled and can inline as normal. The common pattern I use is:\n\n```\nfunction_type f = ...;\nif (!yk_is_interpreting())\n  yk_promote(f);\n(f)(...);\n```\n\n`yk_is_interpreting()` is `true` during “normal” interpretation; `false` during\ntracing; and (because it’s a constant `false`) removed during tracing. In other\nwords, `yk_promote` is only called during the tracing phase.\n`yk_is_interpreting()` is fairly fast (much faster than `yk_promote()`) so this\nidiom is a small but useful performance win.\n\nHowever, there is often a second problem. yk only puts the tracing machinery\ninto a function if it can statically prove that it is reachable from a\ntraceable path. Commonly, functions called from indirect calls cannot be\nstatically proven to be traceable and thus they still leave an outlined call in\nthe trace. We can solve that with the `yk_indirect_inline` function which tells\nyk “this function can be reached from an indirect call and should be considered\nfor tracing”[25].\n\nProfiling a couple of benchmarks quickly showed several potential candidates[26]. My\nexperience is that not all indirect call sites are good targets for promotion:\nfor example, of the interpreters I’ve looked at so far, inlining malloc and\nfree indirect calls has rarely been profitable. However, I quickly alighted\nupon a couple of promising candidates.\n\nLet’s start with the less promising, but easier to explain, one: benchmarks\nlike deltablue and json call `len` on lists and strings. Simplifying slightly,\n`sq_length` is a pointer to a function inside a CPython type, so this becomes\nan indirect call in traces. In the case of `len([...])` the function that’s\nultimately called is `list_length`:\n\n```\nstatic Py_ssize_t list_length(PyObject *a) {\n  return PyList_GET_SIZE(a);\n}\n```\n\nwhere `PyList_GET_SIZE` boils down (slightly elided) to a simple load\n`a->ob_size`. That’s the sort of code that yk loves to see inlined in a trace!\n\nThe [resulting PR](https://github.com/ykjit/ykcpython/pull/22) has to do a\nslightly annoying dance to make yk accept the `yk_promote` call. In essence, if\n`yk_promote` were to be statically inlined into a function which ykllvm\ndetermines doesn’t need to be traced, odd things happen, and so ykllvm throws a\nstatic error. In this case, the function that “should” contain the `yk_promote`\ncan get inlined in multiple paths, one of which falls foul of this check. A\nhacky fix is to pull the promote out into a function which isn’t statically\ninlined[27]. I then did a [second PR](https://github.com/ykjit/ykcpython/pull/23) to\ninline `range` construction and iteration.\n\nYou may notice that in both of these PRs I have marked a much larger number of\nfunctions `yk_indirect_inline` than I have benchmark evidence for. The reason\nfor this is a variant of something I mentioned above: my experience of indirect\ncall sites is that either nearly all targets benefit from indirect inlining or\nnone do. This clearly isn’t an iron law of the universe, but what it means is\nthat I tend to look at all the possible targets, and mark them as\n`yk_indirect_inline` if they look sensible. So far, I have rarely regretted\ndoing so.\n\nCollectively these two PRs drive json’s performance down to 10.41s, though the\neffect on deltablue was too small to say anything either way. As I get further\ninto optimising an interpreter for yk this is common: not all benchmarks\nbenefit from all optimisations.\n\n## Wrapping up\n\nAt this point, you’ve probably got a good sense of how I approach ykifying an\ninterpreter. I raised a few more PRs before realising that I wasn’t going to add\nmuch useful conceptually to this post: it was time to finish this stage of work\noff and write it up.\n\nBefore I started this little journey, I wasn’t entirely sure if yk would work\nat all – let alone “well”! – on an interpreter the size and complexity of\nCPython. The early stages didn’t entirely dispel my worries: there were lots of\nmissing pieces, and quite a few bugs, that needed fixing in yk for ykcpython to\nwork at all. The fact that ykcpython does work, and works fairly well, is proof\nthat at least one big, complex, interpreter can be ykified with relative ease\n— and that it can be surprisingly competitive on performance.\n\nOf course, I am lucky in many ways. yk already had decent foundations, thanks\nto several people’s hard work. The tier 2 interpreter in CPython made my life a\nlot easier than it might otherwise have been. Small benchmarks, like the ones\nI’ve used in this post, tend to flatter (meta-)tracing as a JIT compiling\ntechnique. And when it comes to ykifying interpreters, well, I’ve been round\nthe block a few times.\n\nBut I don’t want to completely underplay things. 3-4 days isn’t that long to\nspend on an interpreter like CPython. It will take a lot longer than that –\neven with the wonder of LLMs to speed up the journey – to do a thorough job\nand squeeze all the juice that ykcpython can expose to yk. Similarly, I have\nonly looked at a handful of benchmarks: it’s unlikely that ykcpython will magically\nspeed up a wide range of programs yet, as there will be many other parts\nof CPython that need to be considered for optimisation. A lot of this will\nnot be rocket science, but it is work, and not all of it can yet be automated.\n\nI also haven’t made any performance optimisations (yet!) to yk for ykcpython\nspecifically (though I have fixed a couple of bottlenecks that I had previously\nbeen able to ignore). In particular, one thing I am entirely confident in is\nthat ykcpython will generate HIR patterns that yk doesn’t yet optimise\neffectively: fixing those will improve ykcpython’s performance for free,\npossibly quite a bit. Even without that, ykcpython has highlighted additional\nbottlenecks in yk that had never previously been an issue: each time one of\nthose is fixed, ykcpython will magically get faster.\n\nIn a sense, this is one of the nice things that yk offers: improvements to yk\nnearly always benefit every ykified interpreter. It’s why I could bring\nykcpython up to speed in a short period of time: I wasn’t writing a JIT\ncompiler from scratch, I was reusing a generic toolkit. For example, the\nvarious missing pieces and bugs that ykcpython highlighted in yk will almost\ncertainly make ykifying the next interpreter that bit easier — and hopefully\nfuture improvements to yk will benefit ykcpython even further!\n\n**Acknowledgments**: [Edd Barrett](https://www.eddbarrett.co.uk/) and [Lukas\nDiekmann](https://diekmann.uk/) did much of the original work on yk. Shopify\nand the Royal Academy of Engineering generously funded the underlying research.\nChris Seaton was the person who made the work on yk possible.\n","body_html":"<h1 id=\"adapting-cpython-for-yk\">Adapting CPython for yk</h1>\n<p>Earlier this year I <a href=\"https://tratt.net/laurie/blog/2026/retrofitting_jit_compilers_into_c_interpreters.html\" rel=\"nofollow ugc noopener\">wrote a post on\nyk</a>,\nwhich can automatically add JIT compilers to C interpreters. Since then we’ve\napplied yk to more interpreters, fixed various bugs, and improved\nperformance notably. Towards the end of October I showed some data where on our\nbenchmark suite[1] yklua is 2× faster than the PUC Lua interpreter it takes as a\nbase.</p>\n<p>I was quite pleased with myself until someone brought me down to earth by\nasking “how do you know if this works for large interpreters?” It’s a fair\nquestion: PUC Lua is at least an order of magnitude smaller[2] than CPython or CRuby and who’s\nto say if it would work with much bigger interpreters? We had looked at CPython a year or so ago, but\nat that point yk was missing several obvious things that CPython would need, so\nwe quickly moved on. A lot has changed since then, and a quick LLM experiment\ngot far enough to suggest it would be worth looking again.</p>\n<p>Happily, having taken a deeper look, CPython not only works when adapted for yk\nas <a href=\"https://github.com/ykjit/ykcpython\" rel=\"nofollow ugc noopener\">ykcpython</a>[3], but there are\nmeaningful performance gains to be had — not only relative to normal CPython,\nbut also relative to Python’s experimental JIT[4]. Roughly speaking,\nthis is the result of 3-4 days’ work on ykcpython directly; there was a separate\nweek and a half of generic yk bug fixing necessary to get to the point that I\ncould look at ykcpython itself.</p>\n<p>Here are the “final” numbers from my brief odyssey on ykcpython and the AWFY\nbenchmark suite:</p>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th>cpython</th><th>cpython_jit</th><th>ykcpython</th></tr></thead><tbody><tr><td>Bounce</td><td>19.27±0.20</td><td>11.09±0.05</td><td><strong>10.09±0.04</strong></td></tr><tr><td>CD</td><td>32.21±0.23</td><td><strong>26.10±0.08</strong></td><td>29.33±0.16</td></tr><tr><td>DeltaBlue</td><td>7.43±0.02</td><td><strong>6.21±0.02</strong></td><td>7.62±0.04</td></tr><tr><td>Json</td><td>11.81±0.08</td><td>10.93±0.05</td><td><strong>9.98±0.03</strong></td></tr><tr><td>List</td><td>15.01±0.22</td><td><strong>8.10±0.05</strong></td><td>10.44±0.09</td></tr><tr><td>Mandelbrot</td><td>11.66±0.28</td><td>6.94±0.27</td><td><strong>4.20±0.07</strong></td></tr><tr><td>NBody</td><td>18.97±0.13</td><td>12.77±0.12</td><td><strong>10.98±0.02</strong></td></tr><tr><td>Permute</td><td>22.97±0.34</td><td><strong>17.95±0.13</strong></td><td>21.04±0.05</td></tr><tr><td>Queens</td><td>13.18±0.14</td><td>9.65±0.11</td><td><strong>8.32±0.03</strong></td></tr><tr><td>Richards</td><td>54.80±0.20</td><td>40.56±0.40</td><td><strong>33.18±0.17</strong></td></tr><tr><td>Sieve</td><td>23.34±0.06</td><td>17.02±0.07</td><td><strong>13.74±0.06</strong></td></tr><tr><td>Storage</td><td>22.03±0.19</td><td>19.94±0.08</td><td><strong>19.67±0.04</strong></td></tr><tr><td>Towers</td><td>20.46±0.25</td><td><strong>12.65±0.05</strong></td><td>13.67±0.04</td></tr></tbody></table></div>\n<p>In this table <code>cpython</code> is “normal” CPython 3.15.1; <code>cpython_jit</code> is CPython\n3.15.1 with the experimental JIT turned on; and <code>ykcpython</code> is commit\n<a href=\"https://github.com/ykjit/ykcpython/commit/31b4d3875a9a63184546d7065863d42b4e24c2fc\" rel=\"nofollow ugc noopener\">31b4d387</a>.\nTimes are in seconds (lower is better) with means and 99% confidence intervals bootstrapped from 30 process\nexecutions, running on a 64 core AMD EPYC 7773X Debian machine in <code>performance</code>\nmode (<a href=\"https://tratt.net/laurie/blog/extra/2026/adapting_cpython_for_yk/adapting_experiment.tgz\" rel=\"nofollow ugc noopener\">download the repeatable experiment and the raw\ndata</a>).\nOn each row the fastest entry(s) are shown in bold.</p>\n<p>A simple summary of the table is: <code>ykcpython</code> is faster than <code>cpython</code> on every\nbenchmark except DeltaBlue (where it’s about 2.5% slower); and faster than\n<code>cpython_jit</code> on 8 out of 13 benchmarks.</p>\n<p>The point of this post is not to pretend that ykcpython is in any way ready for\npeople to use — it definitely is not! Nor is it to pretend that one can\nexpect performance on a wider set of programs to be as good as the numbers\nabove — it definitely won’t! My view is that benchmark suite performance\nis a hoop to jump through rather than an end in itself: a system which\nbenchmarks well might perform poorly in the real world; but a system which\nbenchmarks poorly nearly always performs poorly in the real world.</p>\n<p>Rather, I wanted to use this post as a way of showing what it’s like to adapt\nan interpreter for yk[5]: the stages I went through; and to give a sense\nof how the just under 450LoC I added were enough to achieve a meaningful\neffect. Luckily I had a sense that this might be a useful journey, so I was\nable to write enough stuff down to be able to flesh out this full post.</p>\n<h2 id=\"a-quick-refresher\">A quick refresher</h2>\n<p>If you haven’t read <a href=\"https://tratt.net/laurie/blog/2026/retrofitting_jit_compilers_into_c_interpreters.html\" rel=\"nofollow ugc noopener\">the earlier yk\npost</a>,\nhere’s a very brief refresher. Given a lightly modified C interpreter[6]\nas input, yk produces a VM with a meta-tracing JIT compiler as output[7].\nyk doesn’t aim to produce the fastest possible JIT compiling language\nimplementation: rather, it aims to make the language implementation you know and love\nsomewhat faster while retaining 100% compatibility. Put another way a “ykified”\ninterpreter is a fork of the existing C version of the interpreter, with\n(hopefully!) a handful of adjustments.</p>\n<p>As with any meta-tracing JIT compiler, yk identifies <em>hot</em> loops in the <em>guest</em>\nlanguage (e.g. Lua or Python), and <em>traces</em> the interpreter (i.e. records what\nthe C code is executing while it is interpreting the guest language). It then\noptimises those traces and converts them to machine code.</p>\n<p>yk requires interpreters to tell it where potential loops in the guest language are via\nthe <code>YkLocation</code> struct. Optionally – though if you want to get good\nperformance, definitely necessary! – interpreter authors can add <em>optimisation hints</em> that\nembed knowledge about the language or its common idioms of use such as “at\nthis point this seemingly dynamic value almost never changes”. In general,\nworking out where to put <code>YkLocation</code>s is relatively easy, but working out where to\nput hints requires a much greater understanding of the interpreter, and careful\nmeasurement to understand which do and don’t help.</p>\n<p>The challenge I face when adapting an interpreter for yk is that I rarely know\nthe interpreter well, if at all. Rather than trying to do everything at once, I\nhave learnt to start off as simple as possible: I try and do the minimum\nchanges that lead to some traces being recorded and compiled to machine code.\nThis can be trickier than it seems: I’ve got to understand the build system[8], and work out where to put some semi-sensible <code>YkLocation</code>s.\nI’ve also learnt to make sure that the language’s test suite works from this very\nfirst step: keeping it working thereafter is not only much easier, but it\nlessens the number of times one attempts optimisations that are unsound.</p>\n<p>For a simple interpreter, you might get a basic JIT compiler from an\ninterpreter with fewer than 10LoC (Lines-of-Code) changed. For somewhat bigger\ninterpreters, a few more changes tend to be necessary. For example, yk doesn’t\nlike “threaded” interpreters that use <code>goto</code> between opcodes, because it\ndoesn’t give it enough opportunities to intercede and see what’s going on.\nFortunately, such changes are not generally too big.</p>\n<h2 id=\"finding-the-right-starting-point\">Finding the right starting point</h2>\n<p>Since it had been a long time since I looked at CPython’s internals[9],\nI started with the part I was vaguely familiar with. As I later discovered, this is now called the “tier 1” interpreter.\nQuickly hacking in support for yk highlighted several missing things in yk\n(from <a href=\"https://github.com/ykjit/yk/pull/2426\" rel=\"nofollow ugc noopener\">basic atomic loads</a> to\n<a href=\"https://github.com/ykjit/yk/pull/2418\" rel=\"nofollow ugc noopener\">not-implemented-bit-widths in <code>sub</code></a>,\nminor incompatibilities (e.g. <a href=\"https://github.com/ykjit/yk/pull/2441\" rel=\"nofollow ugc noopener\">reading an environment variable after a CPython\ntest had wiped it</a>), and flat out bugs\n(from <a href=\"https://github.com/ykjit/ykllvm/pull/374/changes\" rel=\"nofollow ugc noopener\">stackmap fixes</a> to\n<a href=\"https://github.com/ykjit/yk/pull/2438\" rel=\"nofollow ugc noopener\">not doing silly things after <code>fork</code></a>).\nFixing all those took me around a week and a half; I’m not going to talk about\nthem in detail in this post, because they’re generic fixes that aren’t\nykcpython specific.</p>\n<p>My <a href=\"https://github.com/ykjit/ykcpython/pull/11\" rel=\"nofollow ugc noopener\">adaption of the tier 1\ninterpreter</a> is deliberately\nminimalistic. Most of the changes in the 200LoC diff are small one-offs that\naren’t hugely interesting: we need CPython to use its (builtin but non-default)\n<code>switch</code>-based interpreter; and yk uses a shadow stack, so CPython’s C stack\nresizing needs to take that into account too. The most interesting thing I did\n<a href=\"https://github.com/ykjit/ykcpython/pull/11/changes#diff-6f869eb8beb7cbe4bc6817584b99ad567f88962fa67f7beca25d009dc401234dR603\" rel=\"nofollow ugc noopener\">was to add <code>YkLocation</code>s at backwards jump opcodes</a>,\nwhich I expected to be enough for some half-sensible traces to be created.</p>\n<p>I wasn’t expecting this first version of ykcpython to be faster\nthan CPython – if nothing else, it contained almost no optimisation hints – but it was\n<em>much</em> slower than I expected. It was definitely creating traces, and they were\nexecuting correctly – the test suite passed, albeit taking more memory\nthan I’d like[10] – but something clearly wasn’t right.</p>\n<p>Fortunately, it didn’t take very long to work out what. 4 years ago, CPython\nadded support for <a href=\"https://peps.python.org/pep-0659/\" rel=\"nofollow ugc noopener\"><em>quickening</em></a> under the\nheading of “specialisation”. Quickening is a simple, clever technique for\n<a href=\"https://www.unibw.de/ucsrl/pubs/ecoop10.pdf/@@download/file/ecoop10.pdf\" rel=\"nofollow ugc noopener\">improving interpreter\nperformance</a>\nthat rewrites “generic” opcodes (e.g. “add objects”) to “specialised”, faster,\nopcodes (e.g. “add two ints”) when possible, deoptimising back to the generic\nopcodes if necessary. I tend to think of quickening as giving a decent portion\nof the benefit of a JIT compiler without all the bother of generating machine\ncode[11]. The problem for yk is that sometimes a program’s opcodes\ncan transition between specialised and unspecialised opcodes a large number of times,\nand the simple way I’d added yk support meant that each transition implicitly\nthrew away the associated trace and created a new one. In most cases, traces weren’t\nused long enough to overcome the cost of creating them.</p>\n<p>There are techniques which can overcome this problem, and I did briefly\nexperiment with them, but I then recalled a conversation I had with some\nCPython developers last year. A quick look inside CPython confirmed my\nrecollection: CPython contains a “tier 2” interpreter as well. This isn’t a\ncompletely new interpreter; rather it is an alternative implementation of core\nparts of the main interpreter loop, mostly intended for CPython’s experimental\nJIT compiler.</p>\n<p>A very quick experiment later suggested that the tier 2 interpreter was – at\nleast at a basic level – a better fit for yk[12]. I thus ripped out\nthe tier 1 support and added <a href=\"https://github.com/ykjit/ykcpython/pull/12\" rel=\"nofollow ugc noopener\">support for yk in the tier 2\ninterpreter</a>. Happily, tier 2\nsupport is even easier than tier 1 support, consisting of a mere <a href=\"https://github.com/ykjit/ykcpython/pull/12/changes/06e91ccc5a34cb8be58a398413c56e92b5b534eb\" rel=\"nofollow ugc noopener\">80\nLoC</a>.\nTo give you a quick idea of what yk support looks like, here’s the part that\nattaches <code>YkLocation</code>s[13] to the (start of) loops:</p>\n<pre><code>for (uint32_t i = 0; i &lt; executor-&gt;code_size; i++) {\n  const _PyUOpInstruction *uop = &amp;executor-&gt;trace[i];\n  if (_PyUop_Uncached[uop-&gt;opcode] == _JUMP_TO_TOP) {\n    uint16_t target = uop_get_jump_target(uop);\n    if (yk_location_is_null(executor-&gt;yk_locs[target])) {\n      executor-&gt;yk_locs[target] = yk_location_new();\n    }\n  }\n}</code></pre>\n<p>For the rest of this post, I’m going to be using yk and the tier 2 interpreter as the\nstarting point for ykcpython.</p>\n<h2 id=\"what-s-being-benchmarked\">What’s being benchmarked</h2>\n<p>When optimising any language implementation, it’s important to know where its\nperformance sits in the wider performance landscape. To understand how\nykcpython was doing, I used two other baselines: “stock” CPython; and CPython\nwith the experimental JIT. I configured <code>cpython</code> as follows:</p>\n<pre><code>CC=clang-21 CXX=clang++-21 \\\n  ./configure \\\n  --enable-optimizations \\\n  --with-lto</code></pre>\n<p>Note that I’m deliberately using the same version of LLVM for both <code>cpython</code>\nand <code>cpython_jit</code> because the latter requires LLVM-21. ykllvm – the fork of\nLLVM used in yk – is <a href=\"https://github.com/ykjit/ykllvm/pull/312\" rel=\"nofollow ugc noopener\">based off a version of LLVM about 6 months\nlater</a> than LLVM-21. That might\nslightly distort comparisons, but it’s a small enough difference that the\neffects hopefully are fairly minor. Bearing that in mind, <code>ykcpython</code> is\nconfigured as follows:</p>\n<pre><code>../configure \\\n  --without-computed-gotos \\\n  --without-tail-call-interp \\\n  --enable-experimental-jit=interpreter \\\n  --without-ensurepip</code></pre>\n<p>I used <a href=\"https://github.com/ykjit/yk-benchmarks/tree/main/suites/awfy/Python\" rel=\"nofollow ugc noopener\">our fork</a>[14] of the <a href=\"https://github.com/smarr/are-we-fast-yet\" rel=\"nofollow ugc noopener\">AWFY</a> benchmark\nsuite, simply because I know how to run it without thinking.</p>\n<p>The next challenge is to define a metric, or metrics, to report performance.\nEvery metric has the potential to mislead and\nmany are difficult to understand. In my opinion, the least worst single metric\nis wall-clock time: how long does my program take to run from start to\nfinish? This doesn’t capture everything we want to know, but it captures a lot,\nand it’s easy to understand.</p>\n<p>Most importantly this metric implicitly includes <a href=\"https://soft-dev.org/pubs/html/barrett_bolz-tereick_killick_mount_tratt__virtual_machine_warmup_blows_hot_and_cold_v6/\" rel=\"nofollow ugc noopener\">start-up and warm-up\ntime</a>.\nIn other words I’m deliberately choosing a timing metric which tends to favour\nnormal interpreters and “penalise” JIT compilers. To somewhat offset that, we\nrun each AWFY benchmark for 10 in-process iterations (i.e. run the whole\nbenchmark in a <code>for 0..10</code> loop) so that we also get some sense of how\noptimisation benefits longer-running programs.</p>\n<p>The big performance table at the start of this post uses a custom benchmark\nrunner on an idle machine. All the timings from now on in the post are from me\nrunning <code>time</code> once as a normal user without being too careful if the machine\nis completely idle or not: when starting to optimise an interpreter, it’s not\npractical to wait an hour to benchmark every change on many benchmarks, when\nthe effects are generally quite large[15].</p>\n<h2 id=\"optimising-interpreter-dispatch\">Optimising interpreter dispatch</h2>\n<p>There are various ways one can go about optimising an interpreter for\nmeta-tracing, all of which have pros and cons: the sequence of optimisations\nI’m showing here is just one way of going about things[16].</p>\n<p>Let’s start with the <a href=\"https://github.com/ykjit/yk-benchmarks/blob/main/suites/awfy/Python/mandelbrot.py\" rel=\"nofollow ugc noopener\">mandelbrot\nbenchmark</a>\non <code>cpython</code>:</p>\n<pre><code>$ time cpython harness.py Mandelbrot 10 500\nStarting Mandelbrot benchmark ...\nMandelbrot: iterations=1 runtime: 1166072us\nMandelbrot: iterations=1 runtime: 1163564us\nMandelbrot: iterations=1 runtime: 1166220us\nMandelbrot: iterations=1 runtime: 1164960us\nMandelbrot: iterations=1 runtime: 1166583us\nMandelbrot: iterations=1 runtime: 1166431us\nMandelbrot: iterations=1 runtime: 1168500us\nMandelbrot: iterations=1 runtime: 1168757us\nMandelbrot: iterations=1 runtime: 1165289us\nMandelbrot: iterations=1 runtime: 1170343us\nMandelbrot: iterations=10 average: 1166672us total: 11666719us\n\nTotal Runtime: 11666719us\ncpython/python harness.py Mandelbrot 10 500  11.67s user 0.01s system 99% cpu 11.687 total</code></pre>\n<p>In other words, I ran the benchmark with 10 in-process iterations and a\nparameter of 500. The AWFY harness prints out how long each iteration took. As\nis common – but definitely not universal! – for an interpreter, <code>cpython</code>\nhad fairly consistent times from one iteration to the next.</p>\n<p>For this benchmark, <code>cpython_jit</code> takes 6.746s (0.58× CPython) and <code>ykcpython</code>\ntakes a whopping 13.70s (1.17× CPython)[17]:</p>\n<pre><code>$ time ykcpython harness.py Mandelbrot 10 500\nStarting Mandelbrot benchmark ...\nMandelbrot: iterations=1 runtime: 1488078us\nMandelbrot: iterations=1 runtime: 1353013us\nMandelbrot: iterations=1 runtime: 1354018us\nMandelbrot: iterations=1 runtime: 1350854us\nMandelbrot: iterations=1 runtime: 1351681us\nMandelbrot: iterations=1 runtime: 1351815us\nMandelbrot: iterations=1 runtime: 1351454us\nMandelbrot: iterations=1 runtime: 1352860us\nMandelbrot: iterations=1 runtime: 1352099us\nMandelbrot: iterations=1 runtime: 1352516us\nMandelbrot: iterations=10 average: 1365839us total: 13658388us\n\nTotal Runtime: 13658388us\nykcpython/build-yk/python harness.py Mandelbrot 10 500  13.94s user 0.07s system 102% cpu 13.691 total</code></pre>\n<p>There are a couple of useful things to notice here. First, we can see warm-up\noccurring: <code>ykcpython</code>’s first iteration is slower than subsequent iterations.\nThat’s OK in my book: yk isn’t really intended for programs running in a\nfraction of a second. Second, the <code>102% cpu</code> and user time\nthat is higher than wall-clock time are due to yk running trace compilation in threads.\nThat allows the interpreter to continue executing, reducing perceived pauses.</p>\n<p>The first thing I do in this situation is look at the “high-level IR” (HIR) of\nthe traces that yk has produced to see if things look sensible:</p>\n<pre><code>$ YKD_LOG_IR=/tmp/l1:hir ykcpython harness.py Mandelbrot 10 500\n...\n$ rg Begin /tmp/l1 | wc -l\n11\n$ rg Loop /tmp/l1 | wc -l\n1</code></pre>\n<p>The logfile contains 11 traces, of which 1 is a “loop” trace. In general,\nloop traces are where yk is most effective, and the non-loop traces are\nthe price we have to pay to get the promised land of loop traces. In this\ncase, a simple profile showed that most execution time is spent in the\nsolitary loop trace, which is a promising start for yk.</p>\n<p>At this point, doing much more with the HIR than this high-level analysis is\ndifficult, because the output is 20,772 lines of this sort of thing:</p>\n<pre><code>%68: ptr = 0x13D581D4\n%69: i8 = 0\nstore %69, %68\n%71: i16 = load %64\n%72: i32 = zext %71\n%73: i32 = 32767\n%74: i32 = and %72, %73\n%75: i16 = trunc %74\n%76: ptr = 0x13D58218\n%77: ptr = load %76\n%78: ptr = 0x0\n%79: i1 = icmp eq %77, %78\nguard false, %79, [%0, %2, %2, %3, %4, %5, %6, %7, %8, %9, %10, %11, %12, %13, %14, %15, %16, %17, %18, %19, %20, %21, %22, %23, %24, %25, %26, %27, %28, %29, %30, %31, %32, %33, %34, %35, %36, %37, %38, %39, %40, %41, %42, %43, %44, %45, %64, %74, %75, %78, %56, %49, %50, %51, %52, %53]</code></pre>\n<p>Even if you’re used to this syntax and way of thinking, it can be incredibly\nhard to see the forest for the trees: there’s just too much <em>stuff</em>. And that\nisn’t just a problem for humans (or AIs) reading this: more HIR means more\nmachine code which implies slower execution.</p>\n<p>My first port of call when optimising an interpreter is to tackle interpreter\ndispatch. When an interpreter is executing a program, it continually asks “what\nis the opcode of the current instruction? Is it an <code>add</code> or a <code>sub</code> or …?”\nand then it <em>dispatches</em> to the code that performs the appropriate action. It’s\nprobable that a large chunk of that 20KLoC of HIR is the interpreter loading an\nopcode from memory and checking what kind it is. yk’s trace optimiser has\nvarious classic compiler tricks up its sleeve, but in this case they don’t\nreally help, because in most cases between the same instruction being loaded\ntwice from memory, some other code will be called that yk has to assume might\nhave mutated that memory. This isn’t unnecessary conservatism: Python programs\nreally can mutate their function’s instructions!</p>\n<p>I was particularly lucky because the tier2 interpreter uses “executors” which\nare traces of (optimised) instructions. Those instructions are immutable in the\ncontext of a given executor: should a Python function’s instructions change,\nany associated executors will be invalidated. That means that we can attach a\nsimple monotonically increasing integer <em>code ID</em> to a <code>_PyExecutorObject</code> and\nknow that for a given code ID, an opcode at index *I* will always be the same.</p>\n<p>This allows us to use the single most effective optimisation hint in yk:\nidempotent functions. In essence, an idempotent function says “for the same\ninputs this function will always produce the same output”[18].\n“Always” here really means “always”! Idempotent is a <em>very</em> strong guarantee\nthat yk cannot help you uphold: if you fail to do so, your system will go wrong\nin weird ways.</p>\n<p>Although yk provides a helper <code>yk_idempotent_load</code> function, we need something\nmore specialised. Fortunately it’s not hard to write what we need:</p>\n<pre><code>__attribute__((yk_idempotent))\nuint16_t idempotent_load_opcode(uint64_t code_id, const _PyUOpInstruction *pc)\n{\n    __asm__ volatile(&quot;&quot; : &quot;+r&quot;(code_id));\n    return pc-&gt;opcode;\n}</code></pre>\n<p>Unsurprisingly, the <code>yk_idempotent</code> attribute tells yk that\n<code>idempotent_load_opcode</code> is an idempotent function. That means that if, in a\nparticular trace, the function is called with parameters that are constant\nvalues then yk can remove the idempotent function call and replace it with its\noutput. The <code>__asm__</code> line is there to encourage LLVM not to inline the\nfunction[19] (if the function is inlined, yk no longer knows there is\nanything idempotent there).</p>\n<p>Using this requires <a href=\"https://github.com/ykjit/ykcpython/pull/13\" rel=\"nofollow ugc noopener\">changing just a few lines in the core\ninterpreter loop</a>. The most important\nlines are simply this:</p>\n<pre><code>yk_promote(next_uop);\nyk_promote_code_id(yk_code_id);\nuopcode = idempotent_load_opcode(yk_code_id, next_uop);</code></pre>\n<p>Promotion (e.g. <code>yk_promote</code>)[20] says “this variable is expected to be\nsemi-constant: record its concrete value and specialise the trace to it, but\ninsert a guard in case that value later changes”. Imagine I have\n<code>yk_promote(x)</code> and when a trace is later recorded, <code>x</code> happens to be <code>3</code>. The trace\nwill record <code>guard true (x == 3)</code>: if on later runs <code>x</code> is not <code>3</code>, the guard\nwill fail and the trace will deoptimise; if the guard succeeds we know henceforth\nthat <code>x</code> is definitely <code>3</code>.</p>\n<p>In other words, in the context of the traces we’re recording, yk will see calls\nto <code>idempotent_load_opcode</code> with constant arguments, allowing it to replace the\nfunction call with a constant result. The point of this isn’t just to remove\nthe cost of a load: rather, exposing constant data to yk’s trace optimiser allows it to\ndo a much better job of optimising traces. The effect in this case is quite\nsomething:</p>\n<pre><code>$ time ykcpython harness.py Mandelbrot 10 500\nStarting Mandelbrot benchmark ...\nMandelbrot: iterations=1 runtime: 606714us\nMandelbrot: iterations=1 runtime: 485324us\nMandelbrot: iterations=1 runtime: 485994us\nMandelbrot: iterations=1 runtime: 484999us\nMandelbrot: iterations=1 runtime: 483824us\nMandelbrot: iterations=1 runtime: 485431us\nMandelbrot: iterations=1 runtime: 484752us\nMandelbrot: iterations=1 runtime: 486160us\nMandelbrot: iterations=1 runtime: 486125us\nMandelbrot: iterations=1 runtime: 483481us\nMandelbrot: iterations=10 average: 497280us total: 4972804us\n\nTotal Runtime: 4972804us\nykcpython/build-yk/python harness.py Mandelbrot 10 500  5.09s user 0.08s system 103% cpu 5.005 total</code></pre>\n<p>In other words, that simple change has not only made <code>ykcpython</code> 2.7× faster,\nbut it is now 0.43× <code>cpython</code> and 0.74× <code>cpython_jit</code>! In other words, a simple\nPR that changes 30LoC has made this benchmark over twice as fast as CPython and\n25% faster than CPython’s JIT. Another way of judging the effectiveness of this\noptimisation is that it has reduced the 20,772 lines of HIR output to 7,648\nlines[21].</p>\n<h2 id=\"code-needs-to-be-traced-to-be-optimised\">Code needs to be traced to be optimised</h2>\n<p>However, before we get carried away, this isn’t enough to make all benchmarks\nmagically quicker. I have learnt from experience to rotate between benchmarks\nto avoid over-training[22]. In this case I decided to look at the\ndeltablue benchmark, which I know from yklua can be a tough target.\nThe situation in ykcpython turned out to be worse than I expected: <code>cpython</code> takes 7.67s,\n<code>cpython_jit</code> takes 6.20s, and <code>ykcpython</code> (with our idempotent change) takes\n37.51s. Ouch!</p>\n<p>My next port of call is to run <code>YKD_LOG=2</code> which prints warnings if a trace\ncan’t be compiled. Sure enough:</p>\n<pre><code>$ ykcpython harness.py DeltaBlue 10 12000\nStarting DeltaBlue benchmark ...\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nyk-warning: stop-tracing-aborted: Trace too long\nDeltaBlue: iterations=1 runtime: 3362822us\nyk-warning: trace-compilation-aborted: Unimplemented: &#39;%188 = atomicrmw or ptr %187, i64 16 seq_cst, align 8&#39;\n...</code></pre>\n<p>For now I’m going to skip “trace too long”. In essence yk has a fixed limit for\n“this trace looks to be so long that it’s probably not useful”. The limit was\ntoo low, so I <a href=\"https://github.com/ykjit/yk/pull/2453\" rel=\"nofollow ugc noopener\">increased it unilaterally</a>\nbefore doing the work for this post. Exactly what the right value is I don’t\nknow. Indeed, I think that this crude heuristic probably needs replacing with\nsomething more sophisticated: doing that is a problem for another day.</p>\n<p>Let’s move onto the “unimplemented” warning: I haven’t got around to\nimplementing complex atomic instructions yet, so as soon as one of those is\nencountered, yk has no choice but to give up on that trace entirely. If it\nhappens to be a hot part of a benchmark, that can absolutely kill performance.\nIn this case, happily, the <code>atomicrmw</code> warnings just so happened to come from\nfunctions which we really don’t want to inline into the trace anyway.</p>\n<p>One of tracing’s virtues is that it aggressively\ninlines functions, but that can inline checks which fail too often on\nsubsequent executions. For example, one function we inline by default is\n<code>_PyObject_GC_Link</code> which checks to see if enough objects have been allocated\nfor garbage collection to be worth scheduling. If we’re unlucky, we may trace\nan iteration of a loop which happens to schedule garbage collection: in nearly\nevery subsequent execution, the resulting guard will fail, and we’ll take a\nsomewhat slower path. The solution here is to mark such functions as\n<code>yk_outline</code>:</p>\n<pre><code>__attribute__((yk_outline))\nvoid _PyObject_GC_Link(PyObject *op) { ... }</code></pre>\n<p>Functions marked <code>yk_outline</code> become <code>call</code>s in a trace. There are probably a\nnumber of functions which should be marked as <code>yk_outline</code>, but I\n<a href=\"https://github.com/ykjit/ykcpython/pull/14\" rel=\"nofollow ugc noopener\">marked the two</a> that happened to\ncause the <code>aborted</code> warnings and that also obviously we don’t want to include\nin a trace anyway. Doing so improved execution time to 36.63s (about 2.5%\nfaster), so they’re clearly not the major cause of the slowdown in this case.</p>\n<p>Just when I was starting to fret, profiling execution showed that, to my\nsurprise, deltablue was only spending about half its running time in\nJIT-compiled code, where one would expect it to be spending 90%+. It turns out\nthat the main reason for this is that not all executors have a <code>_JUMP_TO_TOP</code>\nopcode and weren’t being traced.</p>\n<p>My quick fix was to add a <code>YkLocation</code> at the first opcode in an executor. The\n<a href=\"https://github.com/ykjit/ykcpython/pull/15\" rel=\"nofollow ugc noopener\">one line fix</a> does just that: it\nmeans that yk starts tracing as soon as it enters an executor. Doing so\nimproves deltablue’s execution time to 8.64s (4.23× faster than before). That’s\nstill 1.13× CPython, but it’s a lot better than before!</p>\n<p>At the time I made this change I didn’t fully think about how adding a\n<code>YkLocation</code> at the start of an executor might interact with the <code>YkLocation</code>\nalready added to <code>_JUMP_TO_TOP</code>. As luck would have it, I accidentally stumbled\non a reasonable combination: <code>_JUMP_TO_TOP</code> tends to jump to the instruction at\nindex 1. Still, I suspect that there might be a better way to add <code>YkLocation</code>s\nto executors, but one can’t solve every problem all at once: it’s time to move\nonto the next thing!</p>\n<h2 id=\"further-into-interpreter-dispatch\">Further into interpreter dispatch</h2>\n<p>Our earlier use of idempotent loads made such a huge impact on interpreter\ndispatch that it’s easy to overlook that it was a simple, shallow, change: it\nonly optimised loading an instruction’s opcode kind. Instructions contain a\nnumber of other fields that are equally amenable to idempotent loading.</p>\n<p>There are various ways one can go about optimising these additional fields. I\ncould, for example, have replaced the definitions of some <code>static</code> functions in\nheader files. To keep things simple, I defined a macro which can generate the\ntwo-parameter functions we need, and then nobbled some other macros to call it\nat appropriate points. With the <a href=\"https://github.com/ykjit/ykcpython/pull/16\" rel=\"nofollow ugc noopener\">resulting change</a> deltablue’s performance\nimproves to 8.09s — we’re now within 10% of <code>cpython</code>’s performance.</p>\n<h2 id=\"unrolling\">Unrolling</h2>\n<p>As we saw earlier, not all functions are good candidates for inlining into a\ntrace. yk has a very simple heuristic – stolen shamelessly from RPython/PyPy\n– which is to mark functions containing loops as “outlined”. In other words,\nif C calls a function <code>f()</code> and <code>f</code> contains <code>for (...) { ... }</code> then yk\nwill not inline calls to <code>f</code>.</p>\n<p>The fundamental reason not to inline functions-with-loops is that tracing\nunrolls loops, and that tends not to be a good idea. First, some loops execute\nvast numbers of iterations, which would cause counter-productively-long traces.\nSecond, loops’ iterations are often controlled by dynamic, ever-changing\nvalues: unrolling would specialise the trace to just one of those values, giving\nsuboptimal performance on every other value.</p>\n<p>There are however a small number of functions in an interpreter which we\nactively want to unroll. Typically those functions’ loops satisfy two\nproperties: they only run a small number of iterations; and the number of\niterations depends on an aspect of the user’s program that changes rarely. For\nexample, a function called <code>unpack_args(int num_args)</code> which contains <code>for (int i=0; i&lt;num_args; i++)</code> would be an excellent candidate, since it probably\nunpacks the same number of parameters every time it is called at the same place\nin a trace.</p>\n<p>yk thus provides a <code>yk_unroll</code> attribute, which informs yk that a function that\nmight otherwise be outlined should in fact be inlined and its loops unrolled.\nRather than slog through every function in CPython looking for candidates, I\ndid a simple grep/sort in hir to see which (implicitly non-inlined) C functions\nappear most often in traces[23]:</p>\n<pre><code>$ YKD_LOG_IR=/tmp/l1:hir ykcpython harness.py Json 10 100\n...\n$ rg call /tmp/l1|grep &quot;@&quot;|cut -d &quot;@&quot; -f 2|sort|uniq -c|sort -n\n   2 PyLong_FromLong\n   6 _Py_HandlePending\n   6 do_lookup\n  24 _PyList_FromStackRefStealOnSuccess\n  50 _PyEvalFramePushAndInit\n  50 _PyObject_GC_Link\n  50 _PyObject_InitInlineValues\n 263 PyLong_FromSsize_t\n1035 _PyFrame_Initialize.5328\n1158 _PyFrame_ClearLocals\n1194 bcmp</code></pre>\n<p><code>bcmp</code> is the standard <code>libc</code> function: all of the other functions are in CPython itself.\nNot all of those functions will have loops in them, but the chances are that\nmost do. What I do in such a situation is go down (or, depending how you look at it,\nup) the list and look at the code in each function. I did that for a couple of\nbenchmarks to ensure I got some coverage of common functions.</p>\n<p>The two most commonly called CPython functions immediately looked like good candidates.\n<code>_PyFrame_Initialize</code> is the most obvious of the two, containing almost exactly\nthe pattern I most like to match on:</p>\n<pre><code>_PyFrame_Initialize(..., int null_locals_from, ...) {\n  ...\n  for (int i = null_locals_from; i &lt; code-&gt;co_nlocalsplus; i++) {\n    frame-&gt;localsplus[i] = PyStackRef_NULL;\n  }\n  ...\n}</code></pre>\n<p><code>_PyFrame_ClearLocals</code> is slightly trickier: it contains a <code>while</code> loop involving pointer\narithmetic, but it didn’t take me long to convince myself that it was a good\ncandidate.</p>\n<p>Earlier we made <code>_PyObject_GC_Link</code> not inlineable, so we don’t want to reverse\nthat! Similarly, <code>do_lookup</code> looks values up in a dictionary, so we want to\nkeep that outlined: it depends on an often-changing dynamic value.</p>\n<p><code>PyLong_FromSsize_t</code> and <code>PyLong_FromLong</code> were harder to judge. These\nfunctions’ inner loops depend on dynamic values, but my best guess is that they\ntend to be fairly stable in practice. I will be keeping an eye on these\nfunctions in the future, because I only have medium confidence that I made the\nright initial call.</p>\n<p>As these examples suggest, I am generally fairly cautious about adding\n<code>yk_unroll</code>: inappropriate placings can easily help one benchmark and make many\nothers worse. I thus tend to only mark one or two functions as <code>yk_unroll</code>,\nbenchmark, and then move on. In this case, I did 5 small PRs, with the end\neffect that json went from 11.52s to 10.85s.</p>\n<h2 id=\"indirect-inlining\">Indirect inlining</h2>\n<p>In general most function calls in C are <em>direct</em>: <code>f()</code> calls a function called\n<code>f</code>. However a minority of functions are <em>indirect</em>: <code>f</code> is a generic pointer\nwhose value can be any compatible function. This is commonly used in\ninterpreters to allow run-time dispatch to type specific code.</p>\n<p>By default, yk cannot inline through indirect function calls, because without\nknowing exactly what pointer is being called, it can’t reliably reconstruct\nthe path that execution took[24]. Fortunately, we already have\nthe tool we need to solve this problem: <code>yk_promote</code>! If yk sees an indirect\nfunction call with a constant pointer it knows exactly what function is being\ncalled and can inline as normal. The common pattern I use is:</p>\n<pre><code>function_type f = ...;\nif (!yk_is_interpreting())\n  yk_promote(f);\n(f)(...);</code></pre>\n<p><code>yk_is_interpreting()</code> is <code>true</code> during “normal” interpretation; <code>false</code> during\ntracing; and (because it’s a constant <code>false</code>) removed during tracing. In other\nwords, <code>yk_promote</code> is only called during the tracing phase.\n<code>yk_is_interpreting()</code> is fairly fast (much faster than <code>yk_promote()</code>) so this\nidiom is a small but useful performance win.</p>\n<p>However, there is often a second problem. yk only puts the tracing machinery\ninto a function if it can statically prove that it is reachable from a\ntraceable path. Commonly, functions called from indirect calls cannot be\nstatically proven to be traceable and thus they still leave an outlined call in\nthe trace. We can solve that with the <code>yk_indirect_inline</code> function which tells\nyk “this function can be reached from an indirect call and should be considered\nfor tracing”[25].</p>\n<p>Profiling a couple of benchmarks quickly showed several potential candidates[26]. My\nexperience is that not all indirect call sites are good targets for promotion:\nfor example, of the interpreters I’ve looked at so far, inlining malloc and\nfree indirect calls has rarely been profitable. However, I quickly alighted\nupon a couple of promising candidates.</p>\n<p>Let’s start with the less promising, but easier to explain, one: benchmarks\nlike deltablue and json call <code>len</code> on lists and strings. Simplifying slightly,\n<code>sq_length</code> is a pointer to a function inside a CPython type, so this becomes\nan indirect call in traces. In the case of <code>len([...])</code> the function that’s\nultimately called is <code>list_length</code>:</p>\n<pre><code>static Py_ssize_t list_length(PyObject *a) {\n  return PyList_GET_SIZE(a);\n}</code></pre>\n<p>where <code>PyList_GET_SIZE</code> boils down (slightly elided) to a simple load\n<code>a-&gt;ob_size</code>. That’s the sort of code that yk loves to see inlined in a trace!</p>\n<p>The <a href=\"https://github.com/ykjit/ykcpython/pull/22\" rel=\"nofollow ugc noopener\">resulting PR</a> has to do a\nslightly annoying dance to make yk accept the <code>yk_promote</code> call. In essence, if\n<code>yk_promote</code> were to be statically inlined into a function which ykllvm\ndetermines doesn’t need to be traced, odd things happen, and so ykllvm throws a\nstatic error. In this case, the function that “should” contain the <code>yk_promote</code>\ncan get inlined in multiple paths, one of which falls foul of this check. A\nhacky fix is to pull the promote out into a function which isn’t statically\ninlined[27]. I then did a <a href=\"https://github.com/ykjit/ykcpython/pull/23\" rel=\"nofollow ugc noopener\">second PR</a> to\ninline <code>range</code> construction and iteration.</p>\n<p>You may notice that in both of these PRs I have marked a much larger number of\nfunctions <code>yk_indirect_inline</code> than I have benchmark evidence for. The reason\nfor this is a variant of something I mentioned above: my experience of indirect\ncall sites is that either nearly all targets benefit from indirect inlining or\nnone do. This clearly isn’t an iron law of the universe, but what it means is\nthat I tend to look at all the possible targets, and mark them as\n<code>yk_indirect_inline</code> if they look sensible. So far, I have rarely regretted\ndoing so.</p>\n<p>Collectively these two PRs drive json’s performance down to 10.41s, though the\neffect on deltablue was too small to say anything either way. As I get further\ninto optimising an interpreter for yk this is common: not all benchmarks\nbenefit from all optimisations.</p>\n<h2 id=\"wrapping-up\">Wrapping up</h2>\n<p>At this point, you’ve probably got a good sense of how I approach ykifying an\ninterpreter. I raised a few more PRs before realising that I wasn’t going to add\nmuch useful conceptually to this post: it was time to finish this stage of work\noff and write it up.</p>\n<p>Before I started this little journey, I wasn’t entirely sure if yk would work\nat all – let alone “well”! – on an interpreter the size and complexity of\nCPython. The early stages didn’t entirely dispel my worries: there were lots of\nmissing pieces, and quite a few bugs, that needed fixing in yk for ykcpython to\nwork at all. The fact that ykcpython does work, and works fairly well, is proof\nthat at least one big, complex, interpreter can be ykified with relative ease\n— and that it can be surprisingly competitive on performance.</p>\n<p>Of course, I am lucky in many ways. yk already had decent foundations, thanks\nto several people’s hard work. The tier 2 interpreter in CPython made my life a\nlot easier than it might otherwise have been. Small benchmarks, like the ones\nI’ve used in this post, tend to flatter (meta-)tracing as a JIT compiling\ntechnique. And when it comes to ykifying interpreters, well, I’ve been round\nthe block a few times.</p>\n<p>But I don’t want to completely underplay things. 3-4 days isn’t that long to\nspend on an interpreter like CPython. It will take a lot longer than that –\neven with the wonder of LLMs to speed up the journey – to do a thorough job\nand squeeze all the juice that ykcpython can expose to yk. Similarly, I have\nonly looked at a handful of benchmarks: it’s unlikely that ykcpython will magically\nspeed up a wide range of programs yet, as there will be many other parts\nof CPython that need to be considered for optimisation. A lot of this will\nnot be rocket science, but it is work, and not all of it can yet be automated.</p>\n<p>I also haven’t made any performance optimisations (yet!) to yk for ykcpython\nspecifically (though I have fixed a couple of bottlenecks that I had previously\nbeen able to ignore). In particular, one thing I am entirely confident in is\nthat ykcpython will generate HIR patterns that yk doesn’t yet optimise\neffectively: fixing those will improve ykcpython’s performance for free,\npossibly quite a bit. Even without that, ykcpython has highlighted additional\nbottlenecks in yk that had never previously been an issue: each time one of\nthose is fixed, ykcpython will magically get faster.</p>\n<p>In a sense, this is one of the nice things that yk offers: improvements to yk\nnearly always benefit every ykified interpreter. It’s why I could bring\nykcpython up to speed in a short period of time: I wasn’t writing a JIT\ncompiler from scratch, I was reusing a generic toolkit. For example, the\nvarious missing pieces and bugs that ykcpython highlighted in yk will almost\ncertainly make ykifying the next interpreter that bit easier — and hopefully\nfuture improvements to yk will benefit ykcpython even further!</p>\n<p><strong>Acknowledgments</strong>: <a href=\"https://www.eddbarrett.co.uk/\" rel=\"nofollow ugc noopener\">Edd Barrett</a> and <a href=\"https://diekmann.uk/\" rel=\"nofollow ugc noopener\">Lukas\nDiekmann</a> did much of the original work on yk. Shopify\nand the Royal Academy of Engineering generously funded the underlying research.\nChris Seaton was the person who made the work on yk possible.</p>","headings":[{"level":1,"text":"Adapting CPython for yk","id":"adapting-cpython-for-yk"},{"level":2,"text":"A quick refresher","id":"a-quick-refresher"},{"level":2,"text":"Finding the right starting point","id":"finding-the-right-starting-point"},{"level":2,"text":"What’s being benchmarked","id":"what-s-being-benchmarked"},{"level":2,"text":"Optimising interpreter dispatch","id":"optimising-interpreter-dispatch"},{"level":2,"text":"Code needs to be traced to be optimised","id":"code-needs-to-be-traced-to-be-optimised"},{"level":2,"text":"Further into interpreter dispatch","id":"further-into-interpreter-dispatch"},{"level":2,"text":"Unrolling","id":"unrolling"},{"level":2,"text":"Indirect inlining","id":"indirect-inlining"},{"level":2,"text":"Wrapping up","id":"wrapping-up"}]}}