7 ms·

The linked paper [0] by Xu and Kjolstad on copy-and-patch JIT is delightfully intriguing! For its original "C-like language" implementation it promises: > We h

The linked paper [0] by Xu and Kjolstad on copy-and-patch JIT is delightfully intriguing! For its original "C-like language" implementation it promises: > We have implemented an SQL database query compiler on top of this metaprogramming system and show that on TPC-H database benchmarks, copy-and-patch generates code two orders of magnitude faster than LLVM -O0 and three orders of magnitude faster than higher optimization levels. The generated code runs an order of magnitude faster than interpretation and 14% faster than LLVM -O0. Unless I misunderstand, its mechanism is a caching system on top of clang+llvm: it recognises AST patterns and their corresponding bytecode – copying the "stencils" and patching in variables. I'd be very eager to see the CPython benchmarks! [0] https://dl.acm.org/doi/10.1145/3485513 https://dl.acm.org/doi/10.1145/3485513

chc4 3y ago
It doesn't cache ASTs or bytecode, or invoke clang/LLVM at runtime. It copies as bytes the assembly body of the compiled functions that act as stencils, using ELF relocations as locations of where to patch in values.
- Retr0id 3y ago
  My first impression is that this sounds clever but also quite fragile, because compilers love to change the minutiae how they emit their relocations between versions or compilation options.
  - lifthrasiir 3y ago
    The stencil is compiled with a separate tool and checked into the repository, so if the stencil didn't change there is no additional compile issue at all. This also means that the aforementioned tool should be able to resolve all relocations beforehand, and the exact method should be standardized in the ELF spec, so the tool only has to track the ELF spec, not the compiler. (In reality the tool would also do some cleanup jobs that are complier-dependent, of course.)
  - Joker_vD 3y ago
    They emit the relocations into the relocation section(s), clearly marked as such. The only fragility may come from the copy-and-patch compiler not supporting all kinds of relocations that exist for a particular ABI or from the ELF itself changing but those things don't happen very often.
adrian17 3y ago
> I'd be very eager to see the CPython benchmarks! In the talk on youtube, the author mentions that it’s not faster than mainline CPython yet (it is slightly faster than experimental off-by-default microoperation support it’s built on top of, but it was already slower than mainline, so it cancels out at best). I think the idea is for it to be merged, but only enabled by default once it becomes worth it; and that’s why the perf numbers aren’t advertised yet. Still, I wonder what the expected peak improvement is. Looking at the current generated assembly, there’s definitely room to improve, but there’s only so much one can do without touching the data model.
- lifthrasiir 3y ago
  The goal is to enable JIT codegen without sacrificing too much performance and adding too much maintenance burden, and a functional JIT implementation needs a few more components other than that---most notably a facility to monitor and trace function calls for the eventual JIT compilation. Consider the OP to be one of intermediate goals, not the eventual goal.
  - adrian17 3y ago
    I don't think we disagree that the long-term goal is to _eventually_ make it faster :) I rather meant to temper the enthusiasm that some could have upon seeing "JIT" and immediately trying to compare with, say, PyPy. > enable JIT codegen without sacrificing too much performance This is the part I don't buy. The main point of a JIT is performance, so by definition I don't see it being enabled unless it improves performance across the board. What I wonder is if the current approach, stated as "copy-and-patch auto-generated code for each opcode", can ever reach that point without being replaced by a completely different design along the way. AFAIK, as is, the main difference between running the interpreter loop composed of normally compiled opcodes and JIT copy-and-patching these opcodes is lack of the opcode dispatch logic running between each op - which is good, but also countered by slightly worse quality of the copied code.
    - lifthrasiir 3y ago
      > What I wonder is if the current approach, stated as "copy-and-patch auto-generated code for each opcode", can ever reach that point without being replaced by a completely different design along the way. Of course this approach produces a worse code than a full compiler by definition---stencils would be too rigid to be further optimized. A stencil conceptually maps to a single opcode, so the only way to break out of this restriction is to add more opcodes. And there are only so many opcodes and stencils you can prefare. But I think you are thinking too much about a possibility to make Python as fast as, say, C for at least some cases. I believe that it won't happen at all, and the current approach clearly points why. Let's consider a simple CPython opcode named `BINARY_ADD` which has a stack effect of `(a b -- sum)`. Ideally it should eventually be compiled down to a fully specialized machine code something like `add rax, r12`, plus some guards. But the actual implementation (`PyNumber_Add` [1]) is far more complex: it may call at most 3 "slot" calls that may add or concatenate arguments, some of them may call back to a Python code. So let's assume that we have done type specialization and arguments are known to be integers. That will result in a single slot call to `PyLong_Add` [2], which again is still complex because CPython has two integer representations. Even when they are both "compact", i.e. at most 31/63 bits long, it may still have to switch to another representation when the resulting sum is no longer compact. So a fully specialized machine code would be only possible when both arguments are known to be integers and compact and have one more spare bit to prevent an overflow. That sounds way more restrictive. [1] https://github.com/python/cpython/blob/36adc79041f4d2764e1daf7db5bb478923e89a1f/Objects/abstract.c#L904-L971 https://github.com/python/cpython/blob/36adc79041f4d2764e1da... [2] https://github.com/python/cpython/blob/36adc79041f4d2764e1daf7db5bb478923e89a1f/Objects/longobject.c#L3440-L3470 https://github.com/python/cpython/blob/36adc79041f4d2764e1da... An uncomfortable truth is that all these explanations also almost perfectly apply to JavaScript---the slot resolution would be the `[[ToNumber]]` internal function and multiple representations will be something like V8's Smi. Modern JS engines do exploit most of them, but at the expense of extremely large codebase with tons of potential attack surfaces. It is really expensive to maintain, and people don't really realize that no performant JS engine was ever developed by a small group of developers. You have to cut some corners. In comparison, CPython's approach is essentially inside out. Any JIT implementation will require you to split all those subtasks into small bits that can be either optimized out or baked into a generated machine code. So what if we start with subtasks without thinking about JIT in the first place? This is what a specializing adaptive interpreter [3] did. The current CPython already has two tiers of interpreters, and micro-opcodes can only appear in the second tier. With them we can split larger opcodes into smaller ones, possibly with optimizations, but its performance is limited by the dispatch logic. The copy-and-patch JIT is not as powerful, but it does eliminate the dispatch logic without large design changes and it's a good choice for this purpose. In the best scenario, it will eventually hit the limit of what's possible with copy-and-patch and a full compiler will be required at that point. But until that point (which may never come as well), this approach allows for a long time of incremental improvements without disruption. [3] https://peps.python.org/pep-0659/ https://peps.python.org/pep-0659/
adontz 3y ago
Their use of words is quite misleading. Code generation as a process of generating code is orders of magnitude faster, but not the generated code, result of code generation.
- e12e 3y ago
  Thank you. I was trying to figure out why clang -O0 was faster than -O3...
  - fatherzine 3y ago
    "14% faster than LLVM -O0" is fairly misleading too. How does the generated code compare with LLVM -O2/-O3? These are SQL queries, which are usually fairly short programs, where I would presume the cost of compiling is negligible compared to the cost of execution.
    - mkesper 3y ago
      The generated code runs an order of magnitude faster than interpretation and 14% faster than LLVM -O0. An order of magnitude faster than interpretation. That's the interesting part for Python, I'd think.
    - stuaxo 3y ago
      I'd say it's a starting point, and also how else would you measure a baseline ? You're right that O2/O3 should be compared too, though they will be more moved targets.
      - fatherzine 3y ago
        Measure time-to-results = compile-time + execution-time, for jit/O0/O2/O3. Fairly basic.
- zodiac 3y ago
  I think there’s syntactic ambiguity whether “faster” modifies “generates” or “code”
rst 3y ago
... which, in a weird bit of back-to-the-future, is exactly how Grace Hopper's original "compilers" worked, compiling (hence the term) patched versions of hand-built stencils. (The first few, A-0 and immediate successors, had program text that named the stencils directly, like what we'd now call directives for a macroassembler; later, MATH-MATIC and FLOW-MATIC added what we'd now call front ends which used the stencil language as an internal intermediate code.)
nickpsecurity 3y ago
Arxiv version: https://arxiv.org/abs/2011.13127 https://arxiv.org/abs/2011.13127

chc4 3y ago

It doesn't cache ASTs or bytecode, or invoke clang/LLVM at runtime. It copies as bytes the assembly body of the compiled functions that act as stencils, using ELF relocations as locations of where to patch in values.

Retr0id 3y ago
My first impression is that this sounds clever but also quite fragile, because compilers love to change the minutiae how they emit their relocations between versions or compilation options.
- lifthrasiir 3y ago
  The stencil is compiled with a separate tool and checked into the repository, so if the stencil didn't change there is no additional compile issue at all. This also means that the aforementioned tool should be able to resolve all relocations beforehand, and the exact method should be standardized in the ELF spec, so the tool only has to track the ELF spec, not the compiler. (In reality the tool would also do some cleanup jobs that are complier-dependent, of course.)
- Joker_vD 3y ago
  They emit the relocations into the relocation section(s), clearly marked as such. The only fragility may come from the copy-and-patch compiler not supporting all kinds of relocations that exist for a particular ABI or from the ELF itself changing but those things don't happen very often.

adrian17 3y ago

> I'd be very eager to see the CPython benchmarks! In the talk on youtube, the author mentions that it’s not faster than mainline CPython yet (it is slightly faster than experimental off-by-default microoperation support it’s built on top of, but it was already slower than mainline, so it cancels out at best). I think the idea is for it to be merged, but only enabled by default once it becomes worth it; and that’s why the perf numbers aren’t advertised yet. Still, I wonder what the expected peak improvement is. Looking at the current generated assembly, there’s definitely room to improve, but there’s only so much one can do without touching the data model.

lifthrasiir 3y ago
The goal is to enable JIT codegen without sacrificing too much performance and adding too much maintenance burden, and a functional JIT implementation needs a few more components other than that---most notably a facility to monitor and trace function calls for the eventual JIT compilation. Consider the OP to be one of intermediate goals, not the eventual goal.
- adrian17 3y ago
  I don't think we disagree that the long-term goal is to _eventually_ make it faster :) I rather meant to temper the enthusiasm that some could have upon seeing "JIT" and immediately trying to compare with, say, PyPy. > enable JIT codegen without sacrificing too much performance This is the part I don't buy. The main point of a JIT is performance, so by definition I don't see it being enabled unless it improves performance across the board. What I wonder is if the current approach, stated as "copy-and-patch auto-generated code for each opcode", can ever reach that point without being replaced by a completely different design along the way. AFAIK, as is, the main difference between running the interpreter loop composed of normally compiled opcodes and JIT copy-and-patching these opcodes is lack of the opcode dispatch logic running between each op - which is good, but also countered by slightly worse quality of the copied code.
  - lifthrasiir 3y ago
    > What I wonder is if the current approach, stated as "copy-and-patch auto-generated code for each opcode", can ever reach that point without being replaced by a completely different design along the way. Of course this approach produces a worse code than a full compiler by definition---stencils would be too rigid to be further optimized. A stencil conceptually maps to a single opcode, so the only way to break out of this restriction is to add more opcodes. And there are only so many opcodes and stencils you can prefare. But I think you are thinking too much about a possibility to make Python as fast as, say, C for at least some cases. I believe that it won't happen at all, and the current approach clearly points why. Let's consider a simple CPython opcode named `BINARY_ADD` which has a stack effect of `(a b -- sum)`. Ideally it should eventually be compiled down to a fully specialized machine code something like `add rax, r12`, plus some guards. But the actual implementation (`PyNumber_Add` [1]) is far more complex: it may call at most 3 "slot" calls that may add or concatenate arguments, some of them may call back to a Python code. So let's assume that we have done type specialization and arguments are known to be integers. That will result in a single slot call to `PyLong_Add` [2], which again is still complex because CPython has two integer representations. Even when they are both "compact", i.e. at most 31/63 bits long, it may still have to switch to another representation when the resulting sum is no longer compact. So a fully specialized machine code would be only possible when both arguments are known to be integers and compact and have one more spare bit to prevent an overflow. That sounds way more restrictive. [1] https://github.com/python/cpython/blob/36adc79041f4d2764e1daf7db5bb478923e89a1f/Objects/abstract.c#L904-L971 https://github.com/python/cpython/blob/36adc79041f4d2764e1da... [2] https://github.com/python/cpython/blob/36adc79041f4d2764e1daf7db5bb478923e89a1f/Objects/longobject.c#L3440-L3470 https://github.com/python/cpython/blob/36adc79041f4d2764e1da... An uncomfortable truth is that all these explanations also almost perfectly apply to JavaScript---the slot resolution would be the `[[ToNumber]]` internal function and multiple representations will be something like V8's Smi. Modern JS engines do exploit most of them, but at the expense of extremely large codebase with tons of potential attack surfaces. It is really expensive to maintain, and people don't really realize that no performant JS engine was ever developed by a small group of developers. You have to cut some corners. In comparison, CPython's approach is essentially inside out. Any JIT implementation will require you to split all those subtasks into small bits that can be either optimized out or baked into a generated machine code. So what if we start with subtasks without thinking about JIT in the first place? This is what a specializing adaptive interpreter [3] did. The current CPython already has two tiers of interpreters, and micro-opcodes can only appear in the second tier. With them we can split larger opcodes into smaller ones, possibly with optimizations, but its performance is limited by the dispatch logic. The copy-and-patch JIT is not as powerful, but it does eliminate the dispatch logic without large design changes and it's a good choice for this purpose. In the best scenario, it will eventually hit the limit of what's possible with copy-and-patch and a full compiler will be required at that point. But until that point (which may never come as well), this approach allows for a long time of incremental improvements without disruption. [3] https://peps.python.org/pep-0659/ https://peps.python.org/pep-0659/

adontz 3y ago

Their use of words is quite misleading. Code generation as a process of generating code is orders of magnitude faster, but not the generated code, result of code generation.

e12e 3y ago
Thank you. I was trying to figure out why clang -O0 was faster than -O3...
- fatherzine 3y ago
  "14% faster than LLVM -O0" is fairly misleading too. How does the generated code compare with LLVM -O2/-O3? These are SQL queries, which are usually fairly short programs, where I would presume the cost of compiling is negligible compared to the cost of execution.
  - mkesper 3y ago
    The generated code runs an order of magnitude faster than interpretation and 14% faster than LLVM -O0. An order of magnitude faster than interpretation. That's the interesting part for Python, I'd think.
  - stuaxo 3y ago
    I'd say it's a starting point, and also how else would you measure a baseline ? You're right that O2/O3 should be compared too, though they will be more moved targets.
    - fatherzine 3y ago
      Measure time-to-results = compile-time + execution-time, for jit/O0/O2/O3. Fairly basic.
zodiac 3y ago
I think there’s syntactic ambiguity whether “faster” modifies “generates” or “code”

rst 3y ago

... which, in a weird bit of back-to-the-future, is exactly how Grace Hopper's original "compilers" worked, compiling (hence the term) patched versions of hand-built stencils. (The first few, A-0 and immediate successors, had program text that named the stencils directly, like what we'd now call directives for a macroassembler; later, MATH-MATIC and FLOW-MATIC added what we'd now call front ends which used the stencil language as an internal intermediate code.)

nickpsecurity 3y ago

Arxiv version: https://arxiv.org/abs/2011.13127 https://arxiv.org/abs/2011.13127