5 ms·

How to write a simple JIT compiler

223 points by eatonphil 5y ago

eatonphil 5y ago
Eli Bendersky has another great, even simpler introduction (from 2013) to JIT compiling but with hardcoded instructions [0]. And a more recent post on JIT compiling Brainfuck [1]. [0] https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-intro... [1] https://eli.thegreenplace.net/2017/adventures-in-jit-compilation-part-2-an-x64-jit/ https://eli.thegreenplace.net/2017/adventures-in-jit-compila...
- haberman 5y ago
  I wrote a blog post about a Brainfuck JIT too: https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-... Mine uses the DynASM framework developed for LuaJIT, so that the assembly instructions can be written symbolically: https://luajit.org/dynasm.html https://luajit.org/dynasm.html
- rvbissell 5y ago
  It amazes me how often I find myself following links back to Eli's blog, unexpectedly. Dude's a treasure.
eterps 5y ago
Experiments like these are really fun to do in a small setting. In reality you would only get to this point after having built a complete programming language with all its parts. But in a situation like this you can start at the end, focus on generating the machine code, putting it in a memory buffer and instructing the CPU to start running it at that point. It can hardly be called a JIT compiler of course, but you definitely get an impression of its mechanics. A couple of years ago I did the JIT 'kickstarting' machinery for fun in the Nim language: https://github.com/eterps/loader/blob/master/syscall.nim https://github.com/eterps/loader/blob/master/syscall.nim
- yholio 5y ago
  Wonder if you could create a new language using this approach, designed for efficient JIT compilation: maximum programmer convenience that is still coherent with maximum runtime performance, whiteout any learning curve for the user other than the language itself.
  - naasking 5y ago
    Yes, these are called multistage languages: https://en.wikipedia.org/wiki/Multi-stage_programming https://en.wikipedia.org/wiki/Multi-stage_programming The classic example is MetaOCaml: https://en.wikipedia.org/wiki/OCaml#MetaOCaml https://en.wikipedia.org/wiki/OCaml#MetaOCaml
- naasking 5y ago
  > In reality you would only get to this point after having built a complete programming language with all its parts. Not necessarily. You might want to JIT a domain-specific abstraction, like a regular expression engine.
Shubhi_29 5y ago
With hand
ximeng 5y ago
https://www.youtube.com/watch?v=xIW6qF8CE78&list=PLvdK1vRmp8wMzH4w_8sQ30NKU3Bt4Cc-M https://www.youtube.com/watch?v=xIW6qF8CE78&list=PLvdK1vRmp8... good video series on JIT compiler implementation
teaearlgraycold 5y ago
To be pedantic, this is an in-memory AOT compiler and not a JIT compiler. As an example, here's a JIT compiler I made for BrainFuck that defers the compilation of some loops: https://github.com/danthedaniel/BF-JIT/blob/master/src/runnable/jit_target.rs#L239 https://github.com/danthedaniel/BF-JIT/blob/master/src/runna...
- ufo 5y ago
  To be a bit less pedantic, this is an area that is kind of ambiguous... From one point of view it's still fair to call this "just in time". I wish there was terminology to differentiate between kind of "on demand AOT compilation" and jits that do jitty stuff that can't be done ahead of time.
  - adgjlsfhk1 5y ago
    Julia uses the term just ahead of time for this, which I think fits well.
  - duped 5y ago
    That strikes me as just-in-time optimization less so than ahead-of-time. If the code isn't compiled until it's executed, "ahead of time" seems extremely confusing
    - ufo 5y ago
      Arguably the term "ahead of time" also suffers from the same problem. Among compiler people, "ahead of time" vs "just in time" sometimes has to do with whether the compiler uses run-time information when compiling. But the names don't reflect that, they talk about when the compilation happens.
  - chrisseaton 5y ago
    > I wish there was terminology to differentiate between kind of "on demand AOT compilation" and jits that do jitty stuff that can't be done ahead of time. Some people differentiate between dynamic JIT compilation and static JIT compilation.
oso2k 5y ago
Another great set of JIT introductions are A Basic Just-In-Time Compiler https://nullprogram.com/blog/2015/03/19/ https://nullprogram.com/blog/2015/03/19/ A JIT Compiler Skirmish with SELinux https://nullprogram.com/blog/2018/11/15/ https://nullprogram.com/blog/2018/11/15/
JulianWasTaken 5y ago
More good JIT tutorials can also be found in the PyPy ecosystem, which provides tooling to add JITs to any interpreter for a language implementation written with its (R)Python toolchain. E.g. here's a recent video: https://www.youtube.com/watch?v=fZj3uljJl_k https://www.youtube.com/watch?v=fZj3uljJl_k
Rendello 5y ago
Terry Davis, of TempleOS fame, did a video about writing a mini JIT compiler in TempleOS using HolyC: https://www.youtube.com/watch?v=RnVYXplrRkQ https://www.youtube.com/watch?v=RnVYXplrRkQ
- no_time 5y ago
  I wish I had a space alien or God himself teach me low level computer architecture.
  - Rendello 5y ago
    Terry Davis learned in university and on the job before the schizophrenia 'kicked in'. How he was able to focus enough to write so much solid code after the illness started, I'll never know.
    - hutzlibu 5y ago
      It is also possible, that the illness gave him the fanatism required to maintain the focus over the years, to come so far with TempleOS. (That same fanatism and crazieness also prevented people from participating I guess.)
      - Rendello 5y ago
        I bet it was less about fanaticism and more about time. Previously, he had worked full time and made money. He wasn't able to work after the illness (I think I read somewhere that he was rehired by his old company, but only lasted a few weeks). TempleOS wasn't the first thing he worked on after becoming ill, he'd previously been working on a three-axis milling machine. https://en.wikipedia.org/wiki/Terry_A._Davis#Onset_of_illness_and_spiritual_awakening https://en.wikipedia.org/wiki/Terry_A._Davis#Onset_of_illnes...
tekknolagi 5y ago
For those interested, my blog has a simple Lisp JIT (https://bernsteinbear.com/blog/ https://bernsteinbear.com/blog/) and I maintain a bunch of resources about other JITs of varying complexity on https://bernsteinbear.com/pl-resources/ https://bernsteinbear.com/pl-resources/
- throw10920 5y ago
  I can attest that the other posts on that blog about AOT compilers are also extremely solid - concrete, practical, well-written.
  - tekknolagi 5y ago
    That's very kind. Thank you.
moonchild 5y ago
> APL [...] manages to achieve reasonable performance by having interpreter operations that apply over a large number of data elements at a time Actually... http://www.softwarepreservation.org/projects/apl/Papers/DYNAMICINCREMENTAL http://www.softwarepreservation.org/projects/apl/Papers/DYNA...
tacoluv 5y ago
I really like this kind of a tutorial - start simple, show how to optimize and what to optimize for, and when things get rough, plug in scotch :)
userbinator 5y ago
I think this is the simplest JIT compiler I've seen, which also is able to compile a rather large subset of C: https://news.ycombinator.com/item?id=8746054 https://news.ycombinator.com/item?id=8746054

223 points by eatonphil 5y ago

Eli Bendersky has another great, even simpler introduction (from 2013) to JIT compiling but with hardcoded instructions [0]. And a more recent post on JIT compiling Brainfuck [1]. [0] https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-introduction https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-intro... [1] https://eli.thegreenplace.net/2017/adventures-in-jit-compilation-part-2-an-x64-jit/ https://eli.thegreenplace.net/2017/adventures-in-jit-compila...

haberman 5y ago
I wrote a blog post about a Brainfuck JIT too: https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html https://blog.reverberate.org/2012/12/hello-jit-world-joy-of-... Mine uses the DynASM framework developed for LuaJIT, so that the assembly instructions can be written symbolically: https://luajit.org/dynasm.html https://luajit.org/dynasm.html
rvbissell 5y ago
It amazes me how often I find myself following links back to Eli's blog, unexpectedly. Dude's a treasure.

eterps 5y ago

Experiments like these are really fun to do in a small setting. In reality you would only get to this point after having built a complete programming language with all its parts. But in a situation like this you can start at the end, focus on generating the machine code, putting it in a memory buffer and instructing the CPU to start running it at that point. It can hardly be called a JIT compiler of course, but you definitely get an impression of its mechanics. A couple of years ago I did the JIT 'kickstarting' machinery for fun in the Nim language: https://github.com/eterps/loader/blob/master/syscall.nim https://github.com/eterps/loader/blob/master/syscall.nim

yholio 5y ago
Wonder if you could create a new language using this approach, designed for efficient JIT compilation: maximum programmer convenience that is still coherent with maximum runtime performance, whiteout any learning curve for the user other than the language itself.
- naasking 5y ago
  Yes, these are called multistage languages: https://en.wikipedia.org/wiki/Multi-stage_programming https://en.wikipedia.org/wiki/Multi-stage_programming The classic example is MetaOCaml: https://en.wikipedia.org/wiki/OCaml#MetaOCaml https://en.wikipedia.org/wiki/OCaml#MetaOCaml
naasking 5y ago
> In reality you would only get to this point after having built a complete programming language with all its parts. Not necessarily. You might want to JIT a domain-specific abstraction, like a regular expression engine.

Shubhi_29 5y ago

With hand

ximeng 5y ago

https://www.youtube.com/watch?v=xIW6qF8CE78&list=PLvdK1vRmp8wMzH4w_8sQ30NKU3Bt4Cc-M https://www.youtube.com/watch?v=xIW6qF8CE78&list=PLvdK1vRmp8... good video series on JIT compiler implementation

teaearlgraycold 5y ago

To be pedantic, this is an in-memory AOT compiler and not a JIT compiler. As an example, here's a JIT compiler I made for BrainFuck that defers the compilation of some loops: https://github.com/danthedaniel/BF-JIT/blob/master/src/runnable/jit_target.rs#L239 https://github.com/danthedaniel/BF-JIT/blob/master/src/runna...

ufo 5y ago
To be a bit less pedantic, this is an area that is kind of ambiguous... From one point of view it's still fair to call this "just in time". I wish there was terminology to differentiate between kind of "on demand AOT compilation" and jits that do jitty stuff that can't be done ahead of time.
- adgjlsfhk1 5y ago
  Julia uses the term just ahead of time for this, which I think fits well.
- duped 5y ago
  That strikes me as just-in-time optimization less so than ahead-of-time. If the code isn't compiled until it's executed, "ahead of time" seems extremely confusing
  - ufo 5y ago
    Arguably the term "ahead of time" also suffers from the same problem. Among compiler people, "ahead of time" vs "just in time" sometimes has to do with whether the compiler uses run-time information when compiling. But the names don't reflect that, they talk about when the compilation happens.
- chrisseaton 5y ago
  > I wish there was terminology to differentiate between kind of "on demand AOT compilation" and jits that do jitty stuff that can't be done ahead of time. Some people differentiate between dynamic JIT compilation and static JIT compilation.

oso2k 5y ago

Another great set of JIT introductions are A Basic Just-In-Time Compiler https://nullprogram.com/blog/2015/03/19/ https://nullprogram.com/blog/2015/03/19/ A JIT Compiler Skirmish with SELinux https://nullprogram.com/blog/2018/11/15/ https://nullprogram.com/blog/2018/11/15/

JulianWasTaken 5y ago

More good JIT tutorials can also be found in the PyPy ecosystem, which provides tooling to add JITs to any interpreter for a language implementation written with its (R)Python toolchain. E.g. here's a recent video: https://www.youtube.com/watch?v=fZj3uljJl_k https://www.youtube.com/watch?v=fZj3uljJl_k

Rendello 5y ago

Terry Davis, of TempleOS fame, did a video about writing a mini JIT compiler in TempleOS using HolyC: https://www.youtube.com/watch?v=RnVYXplrRkQ https://www.youtube.com/watch?v=RnVYXplrRkQ

no_time 5y ago
I wish I had a space alien or God himself teach me low level computer architecture.
- Rendello 5y ago
  Terry Davis learned in university and on the job before the schizophrenia 'kicked in'. How he was able to focus enough to write so much solid code after the illness started, I'll never know.
  - hutzlibu 5y ago
    It is also possible, that the illness gave him the fanatism required to maintain the focus over the years, to come so far with TempleOS. (That same fanatism and crazieness also prevented people from participating I guess.)
    - Rendello 5y ago
      I bet it was less about fanaticism and more about time. Previously, he had worked full time and made money. He wasn't able to work after the illness (I think I read somewhere that he was rehired by his old company, but only lasted a few weeks). TempleOS wasn't the first thing he worked on after becoming ill, he'd previously been working on a three-axis milling machine. https://en.wikipedia.org/wiki/Terry_A._Davis#Onset_of_illness_and_spiritual_awakening https://en.wikipedia.org/wiki/Terry_A._Davis#Onset_of_illnes...

tekknolagi 5y ago

For those interested, my blog has a simple Lisp JIT (https://bernsteinbear.com/blog/ https://bernsteinbear.com/blog/) and I maintain a bunch of resources about other JITs of varying complexity on https://bernsteinbear.com/pl-resources/ https://bernsteinbear.com/pl-resources/

throw10920 5y ago
I can attest that the other posts on that blog about AOT compilers are also extremely solid - concrete, practical, well-written.
- tekknolagi 5y ago
  That's very kind. Thank you.

moonchild 5y ago

> APL [...] manages to achieve reasonable performance by having interpreter operations that apply over a large number of data elements at a time Actually... http://www.softwarepreservation.org/projects/apl/Papers/DYNAMICINCREMENTAL http://www.softwarepreservation.org/projects/apl/Papers/DYNA...

tacoluv 5y ago

I really like this kind of a tutorial - start simple, show how to optimize and what to optimize for, and when things get rough, plug in scotch :)

userbinator 5y ago

I think this is the simplest JIT compiler I've seen, which also is able to compile a rather large subset of C: https://news.ycombinator.com/item?id=8746054 https://news.ycombinator.com/item?id=8746054