en en en pt es en en en en cv en en en en en en en en en en ca es en es ne en en en en en en fr en en en en en en fr en en en en en fr en en en en en en en en en en en en en en en en en en en en en en en en fr en zh nl en en en en en en en en en en en en en en it en en en en en en en pt en en en en en en en en en en en en en en en en
In the last few days I’ve been prototyping a basic Just-In-Time (JIT) compiler for Higgs. I decided to start with a very simple design which is sometimes referred to as a tracelet JIT. This is simply a compiler which compiles one basic block at a time, basic blocks being defined as single-entry, single-exit sequences of instructions. This compiler is lazy, meaning it doesn’t compile unexecuted blocks. It also only compiles “hot” blocks that have been executed a few hundred times, the idea being to avoid wasting time compiling code that only runs once or very few times (e.g.: initialization code). Another advantage of delaying compilation somewhat is to allow time for profiling statistics to be gathered.
I have to admit that I was very excited to actually begin generating machine code (if you can believe that). It took me a few days to port over the x86 assembler I wrote in JavaScript for Tachyon to D, along with all associated unit tests. Once this was done, I was able to get a very basic tracelet JIT working in less than a day. This first version simply compiled sequences of calls to functions implementing interpreter instructions. This provided small speedups on the order of 5%. I improved on this by adding JIT code generation support for some basic arithmetic, bitwise and branching operations which provided speedups of up to 30%. The next step, in my mind, was to support all branching operations so that tracelets could jump directly into each other without ever needing to fall back to the interpreter. However, I ran into a problem.
The Higgs interpreter was designed with simplicity and maintainability in mind, a choice which has paid off thus far. Unfortunately, this means that some operations aren’t built with pure speed in mind, and one problematic case is the call instruction. The call instruction builds the stack frame for callees. This means it needs to make several conditional checks and push the right number of arguments and local variable slots, which isn’t the same for every callee. I started trying to implement the full dynamic extent of calls in the JIT compiler. I stopped once I realized how big and messy the generated code would be. Since every runtime primitive is self-hosted in Higgs, there are calls everywhere, which would assuredly mean the generated machine code would be huge (bad for the instruction cache).
I decided to try an idea just for the fun of it. Most of the calls in the small benchmarks I was testing were global function calls. For such calls, it’s quite easy to guess correctly who the callee would be. I chose to implement a mechanism which tries to guess the callee and has an optimized call path specifically for the said function. If the callee isn’t correctly guessed, the interpreter’s call instruction logic is used instead. Amazingly, such a simple optimization (two hours of work) yielded a total performance improvement of about 500% over the interpreter on most of the benchmarks I tried.
JIT speedup relative to the interpreter
The numbers above show the speedups I measured on some of the SunSpider benchmarks, going from very simple to medium-sized programs. If you’re familiar with these benchmarks, you might feel that these times are ridiculously slow either way. You should keep in mind that this is still very preliminary work (I did say the JIT was a prototype) and that these values were measured using the linux time utility, and so include initialization time. Higgs is also self-hosted, meaning that it lazily compiles parts of its own standard library when you run a program. As such, Higgs will probably always be at a disadvantage when it comes to very short running programs.
At this point, the tracelet JIT compiler is about 800 lines of D code (excluding the x86-64 assembler). It’s very much a prototype and a platform for me to experiment with, meaning I will probably refactor the design in many ways. I’m already thinking of several improvements I can make over the course of the next week which should bring more significant speedups. The main thing I will be doing is trying to extend tracelets in a trace-like manner, which should tremendously help with loops.
As I said earlier, I designed the Higgs interpreter to be simple and easy to maintain. This decision was partly motivated by my belief that interpreter speed should be largely irrelevant in a system where a JIT compiler is also available. I could have tried hard to make the Higgs interpreter faster, at the cost of tasteless kludges and largely increased code complexity, but I don’t think it would have been worth it, especially now that I’ve shown that 4 days of work can yield a simple JIT compiler producing 500% speedups. Next week, I’d like to have at least 1000% speedups over the interpreter, which I believe is easily achievable.
From → Assembly, Compilers, Higgs, JavaScript, Programming, x86
Cryptic Sea (@crypticsea) permalink
Very cool! I haven’t used SunSpider benchmarks, how many iterations does that do? Do most browsers use JIT compilers now?
The times posted are for one iteration of each benchmark.
All modern web browsers have a JIT compiler. It doesn’t seem possible to have adequate performance with just an interpreter.
Cryptic Sea (@crypticsea) permalink
How many bitwise-ands does the first benchmark do? Is there a way to tell how many cycles they take on average? I’m curious about the performance compared to C.
600000 iterations. It’s way too early to compare the performance to C.
Cryptic Sea (@crypticsea) permalink
Thanks! I haven’t written a compiler before so it’s interesting to read about.them, I’ve been thinking about writing a simple compiler for one of my games.
You should. At the very least it will be a good learning experience.
Cryptic Sea (@crypticsea) permalink
Yeah, the game takes place in the 80’s, I want to have 8-bit computers simulated down to machine language, so I’ll need a compiler for that. As I’m typing this I’m realizing it’s pretty ambitious but I never let that stop me :)
Could you provide equivalent benchmark numbers for IonMonkry and V8 on your hardware for comparison to Higgs? I recognize you are a prototype so this is just for understanding of where you are, not where you can get.
Progress on the Higgs JIT | Pointers Gone Wild
Leave a Reply Cancel reply
Enter your comment here...
Fill in your details below or click an icon to log in:
Email (required) (Address never made public)
You are commenting using your WordPress.com account. ( Log Out /  Change )
You are commenting using your Twitter account. ( Log Out /  Change )
You are commenting using your Facebook account. ( Log Out /  Change )
Notify me of new comments via email.
Notify me of new posts via email.
« Progress on the Higgs JIT
Back from Silicon Valley »
Typed vs Untyped Virtual Machines
Minimalism in Programming Language Design
Democracy, Dictatorships and Access to Information
Code that Doesn’t Rot
The Internet Changed My Life
What’s Could You Use Tesla Bot For?
NoiseCraft: a Browser-Based Visual Programming Language for Sound & Music
Art Artificial Intelligence Artificial Life Assembly Biology Compilers Creativity D Language Electronics Future Game Development Genetic Algorithms Grad studies Graphics Higgs JavaScript Microcontrollers Microprocessors Music Programming Programming Languages Psychology Rant Robotics Tachyon Technology Uncategorized work x86 Zeta
Archives Select Month June 2022  (1) May 2022  (1) March 2022  (1) February 2022  (2) January 2022  (2) December 2021  (1) June 2021  (1) February 2021  (2) December 2020  (1) September 2020  (1) January 2020  (1) November 2019  (2) October 2019  (2) June 2019  (1) January 2019  (1) December 2018  (1) May 2018  (2) February 2018  (1) January 2018  (1) December 2017  (1) October 2017  (1) June 2017  (1) April 2017  (1) January 2017  (1) December 2016  (1) November 2016  (2) September 2016  (2) May 2016  (1) March 2016  (1) February 2016  (2) January 2016  (1) November 2015  (4) October 2015  (1) September 2015  (3) August 2015  (2) July 2015  (3) June 2015  (1) May 2015  (3) April 2015  (2) March 2015  (1) February 2015  (1) December 2014  (1) November 2014  (2) October 2014  (2) September 2014  (3) July 2014  (3) May 2014  (1) April 2014  (1) March 2014  (1) February 2014  (1) January 2014  (3) December 2013  (3) October 2013  (2) September 2013  (1) August 2013  (2) July 2013  (3) June 2013  (2) May 2013  (3) March 2013  (2) February 2013  (1) January 2013  (3) December 2012  (4) November 2012  (1) October 2012  (1) September 2012  (3) July 2012  (4) June 2012  (2) May 2012  (2) April 2012  (4) March 2012  (2) February 2012  (3) January 2012  (6) December 2011  (2) November 2011  (3) October 2011  (8) September 2011  (4) August 2011  (3)