10 ms·

A copy-and-patch JIT compiler for CPython

270 points by polyrand 3y ago

1f60c 3y ago
This is awesome. I don't want to spoil anything, but please read the PR description. You won't regret it (or your money back!).
- Ringz 3y ago
  I read it first and also wanted to post a corresponding note here. You were faster. It's really worth it. :•) You get downvoted on Hacker News if you don't use English?
chc4 3y ago
Sweet! I tried playing around with implementing a copy-and-patch style JIT in Rust before, but unfortunately between the lack of `ghccc`-style register-heavy calling convention and (still!) having no way to guarantee tailcalls, rustc doesn't make it very easy and I gave up.
yunruse 3y ago
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
nialse 3y ago
I believe this is the talk about the python JIT by Brandt Bucher. https://youtu.be/HxSHIpEQRjs https://youtu.be/HxSHIpEQRjs
vidarh 3y ago
Their "binary stencils" reminds me of Michael Franz' "Code Generation on the Fly: A Key to Portable Software". Franz generated the templates at runtime by caching parameterized code fragments from doing code gen on a version of the AST effective encoded in an lzw like way, so that each partial AST node would just have code generated once, so it didn't go as far as this but the stencil/template approach was there.
sighansen 3y ago
The commit messages are terrible. In my opinion, conventional commit messages [0] should be used for a clean commit history. [0] https://www.conventionalcommits.org/en/v1.0.0/ https://www.conventionalcommits.org/en/v1.0.0/
- theyinwhy 3y ago
  Something more descriptive than "Grrr" would be nice I guess.
- Kwpolska 3y ago
  CPython seems to use squash merges, which means only one commit will end up on the main branch after merging this PR. The history on branches is irrelevant and can be completely messy, full of merges and other experiments; the main branch has one commit per actual feature/change. And eh, conventional commits seem like pointless bureaucracy to me.
  - hnfong 3y ago
    With only +1,722 lines added, even if the commits were eventually squashed upon landing, I'd consider it good etiquette to tidy up changes to maybe a handful of logical commits instead of pushing 404 raw commits. Or maybe it's another weird pun on 404 Not Found? I can't tell by now...
    - CapsAdmin 3y ago
      The end result of doing this is good, but I find it really difficult to cleanly do this before I have something that's 100% complete. I don't code linearly like "first I need feature A, then I code feature B which is needed for feature C, and so on" It's usually a bit all over the place and it's not clear what depends on what until I start reaching the end. So to do this properly I'd need to spend a day or two rewriting or making a new branch that cleanly adds everything in order. Hopefully in a way that doesn't leave master in a broken state when reverting tail commits. In addition, when doing multiple pull requests for a single high level feature, you might get some comments about pull request "C" that would require changes in pull request "A"
samsquire 3y ago
Wow! Thank you for your hard work. I use python for all experimental work so this would speed up my scripting work, such as processing data from API calls or filesystem. Would be good if it could speed up Flask or Django applications. I wrote a simple toy JIT for a Javascript-like language in jitcompiler.c. It might be useful for others to learn from (I'm a beginner too!) because it's so simply written and not complicated. It's about ~2400 lines of C: frontend and backend. I do lazy patching of callsites, I haven't got anywhere near as advanced as tracing or copy-and-patching. Much of the code I wrote for this JIT was written in Python and ported to C such as register allocation, graph colouring, precolouring and "A Normal Form". The Java Virtual Machine has a template interpreter which is interesting to research. I haven't got around to encoding amd64 x86_64 instructions as bitmasks yet, so I've hardcoded it which is another ~2000 lines of code :-) [1]: https://github.com/samsquire/compiler https://github.com/samsquire/compiler see jitcompiler.c
kragen 3y ago
xu and kjolstad's paper https://dl.acm.org/doi/pdf/10.1145/3485513 https://dl.acm.org/doi/pdf/10.1145/3485513 (cc-by) looks pretty worth reading; the abstract makes exciting claims i'm skeptical of this line > The patching step rewrites pre-determined places in the binary code, which are operands of machine instructions, including jump addresses and values of constants (stack offsets and literal values). Despite patching binary code, however, the system does not need any knowledge of platform-specific machine instruction encoding and is thus portable. like, i think if that were possible then we wouldn't need new linker relocation types for risc-v? how are you going to patch an auipc or st instruction to have the right stack offsets and memory addresses without knowing about the weird platform-specific details like how you have to increment the auipc immediate field to compensate for the sign-extension of the associated addi or jump field in the case where its high bit is set? two of the most influential systems using this stencil technique, as i understand it, include bellard's qemu (02005) https://www.usenix.org/legacy/event/usenix05/tech/freenix/full_papers/bellard/bellard.pdf https://www.usenix.org/legacy/event/usenix05/tech/freenix/fu... (cited in xu and kjolstad's bibliography) and massalin's synthesis (01992) https://dl.acm.org/doi/10.5555/143219 https://dl.acm.org/doi/10.5555/143219 (not cited) synthesis's quaject object system was notable for generating code at object instantiation time, so that dynamic method dispatch was implemented by branching to a subroutine at a given offset from the receiver's address, instance variables could be located in immediate operands of instructions, and the program counter served as the receiver pointer (instance variable accesses could be pc-relative). unfortunately massalin never published synthesis itself, just papers about it
- lifthrasiir 3y ago
  > like, i think if that were possible then we wouldn't need new linker relocation types for risc-v? how are you going to patch an auipc or st instruction to have the right stack offsets and memory addresses without knowing about the weird platform-specific details like how you have to increment the auipc immediate field to compensate for the sign-extension of the associated addi or jump field in the case where its high bit is set? That knowledge is encoded into the relocation type (e.g. R_X86_64_64) for given ABI. So the system does know about relocations, and some relocation types will be specific to a single architecture (R_RISCV_CALL_PLT in this example, I think?). But that's all you need to know about those architectures.
mgaunard 3y ago
PR is unreadable due to being redacted like a story with irrelevant details.
- tecleandor 3y ago
  It's all explained, including a 50 minutes talk, in the linked issue: https://github.com/python/cpython/issues/113464 https://github.com/python/cpython/issues/113464
  - mgaunard 3y ago
    A link to a video is not a good PR writeup. It needs to be concise, precise, and to the point.
erlend_sh 3y ago
For another very recent implementation of copy-and-patch, written in Zig, see Cyber-lang: https://cyberscript.dev/0.3/index.html https://cyberscript.dev/0.3/index.html

270 points by polyrand 3y ago

This is awesome. I don't want to spoil anything, but please read the PR description. You won't regret it (or your money back!).

Ringz 3y ago
I read it first and also wanted to post a corresponding note here. You were faster. It's really worth it. :•) You get downvoted on Hacker News if you don't use English?

chc4 3y ago

Sweet! I tried playing around with implementing a copy-and-patch style JIT in Rust before, but unfortunately between the lack of `ghccc`-style register-heavy calling convention and (still!) having no way to guarantee tailcalls, rustc doesn't make it very easy and I gave up.

yunruse 3y ago

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

nialse 3y ago

I believe this is the talk about the python JIT by Brandt Bucher. https://youtu.be/HxSHIpEQRjs https://youtu.be/HxSHIpEQRjs

vidarh 3y ago

Their "binary stencils" reminds me of Michael Franz' "Code Generation on the Fly: A Key to Portable Software". Franz generated the templates at runtime by caching parameterized code fragments from doing code gen on a version of the AST effective encoded in an lzw like way, so that each partial AST node would just have code generated once, so it didn't go as far as this but the stencil/template approach was there.

sighansen 3y ago

The commit messages are terrible. In my opinion, conventional commit messages [0] should be used for a clean commit history. [0] https://www.conventionalcommits.org/en/v1.0.0/ https://www.conventionalcommits.org/en/v1.0.0/

theyinwhy 3y ago
Something more descriptive than "Grrr" would be nice I guess.
Kwpolska 3y ago
CPython seems to use squash merges, which means only one commit will end up on the main branch after merging this PR. The history on branches is irrelevant and can be completely messy, full of merges and other experiments; the main branch has one commit per actual feature/change. And eh, conventional commits seem like pointless bureaucracy to me.
- hnfong 3y ago
  With only +1,722 lines added, even if the commits were eventually squashed upon landing, I'd consider it good etiquette to tidy up changes to maybe a handful of logical commits instead of pushing 404 raw commits. Or maybe it's another weird pun on 404 Not Found? I can't tell by now...
  - CapsAdmin 3y ago
    The end result of doing this is good, but I find it really difficult to cleanly do this before I have something that's 100% complete. I don't code linearly like "first I need feature A, then I code feature B which is needed for feature C, and so on" It's usually a bit all over the place and it's not clear what depends on what until I start reaching the end. So to do this properly I'd need to spend a day or two rewriting or making a new branch that cleanly adds everything in order. Hopefully in a way that doesn't leave master in a broken state when reverting tail commits. In addition, when doing multiple pull requests for a single high level feature, you might get some comments about pull request "C" that would require changes in pull request "A"

samsquire 3y ago

Wow! Thank you for your hard work. I use python for all experimental work so this would speed up my scripting work, such as processing data from API calls or filesystem. Would be good if it could speed up Flask or Django applications. I wrote a simple toy JIT for a Javascript-like language in jitcompiler.c. It might be useful for others to learn from (I'm a beginner too!) because it's so simply written and not complicated. It's about ~2400 lines of C: frontend and backend. I do lazy patching of callsites, I haven't got anywhere near as advanced as tracing or copy-and-patching. Much of the code I wrote for this JIT was written in Python and ported to C such as register allocation, graph colouring, precolouring and "A Normal Form". The Java Virtual Machine has a template interpreter which is interesting to research. I haven't got around to encoding amd64 x86_64 instructions as bitmasks yet, so I've hardcoded it which is another ~2000 lines of code :-) [1]: https://github.com/samsquire/compiler https://github.com/samsquire/compiler see jitcompiler.c

kragen 3y ago

xu and kjolstad's paper https://dl.acm.org/doi/pdf/10.1145/3485513 https://dl.acm.org/doi/pdf/10.1145/3485513 (cc-by) looks pretty worth reading; the abstract makes exciting claims i'm skeptical of this line > The patching step rewrites pre-determined places in the binary code, which are operands of machine instructions, including jump addresses and values of constants (stack offsets and literal values). Despite patching binary code, however, the system does not need any knowledge of platform-specific machine instruction encoding and is thus portable. like, i think if that were possible then we wouldn't need new linker relocation types for risc-v? how are you going to patch an auipc or st instruction to have the right stack offsets and memory addresses without knowing about the weird platform-specific details like how you have to increment the auipc immediate field to compensate for the sign-extension of the associated addi or jump field in the case where its high bit is set? two of the most influential systems using this stencil technique, as i understand it, include bellard's qemu (02005) https://www.usenix.org/legacy/event/usenix05/tech/freenix/full_papers/bellard/bellard.pdf https://www.usenix.org/legacy/event/usenix05/tech/freenix/fu... (cited in xu and kjolstad's bibliography) and massalin's synthesis (01992) https://dl.acm.org/doi/10.5555/143219 https://dl.acm.org/doi/10.5555/143219 (not cited) synthesis's quaject object system was notable for generating code at object instantiation time, so that dynamic method dispatch was implemented by branching to a subroutine at a given offset from the receiver's address, instance variables could be located in immediate operands of instructions, and the program counter served as the receiver pointer (instance variable accesses could be pc-relative). unfortunately massalin never published synthesis itself, just papers about it

lifthrasiir 3y ago
> like, i think if that were possible then we wouldn't need new linker relocation types for risc-v? how are you going to patch an auipc or st instruction to have the right stack offsets and memory addresses without knowing about the weird platform-specific details like how you have to increment the auipc immediate field to compensate for the sign-extension of the associated addi or jump field in the case where its high bit is set? That knowledge is encoded into the relocation type (e.g. R_X86_64_64) for given ABI. So the system does know about relocations, and some relocation types will be specific to a single architecture (R_RISCV_CALL_PLT in this example, I think?). But that's all you need to know about those architectures.

mgaunard 3y ago

PR is unreadable due to being redacted like a story with irrelevant details.

tecleandor 3y ago
It's all explained, including a 50 minutes talk, in the linked issue: https://github.com/python/cpython/issues/113464 https://github.com/python/cpython/issues/113464
- mgaunard 3y ago
  A link to a video is not a good PR writeup. It needs to be concise, precise, and to the point.

erlend_sh 3y ago

For another very recent implementation of copy-and-patch, written in Zig, see Cyber-lang: https://cyberscript.dev/0.3/index.html https://cyberscript.dev/0.3/index.html