Transcript
Laurence Tratt: Wouldn't it be great if we could make more of our programming languages run faster? Particularly the awkward squad, we might call them the dynamically typed language, or the scripting languages, the Luas, the Rubys, the Pythons, but also there are quite a lot of other language implementations out there that may not run as fast as you would like. CPU companies have CPU simulators and so on. What I'm going to do is show you that we can take existing language implementations and automatically add a just-in-time compiler to them. I'm going to introduce a new technology we developed called yk. The good news is that it does something fun. The problem is that showing performance is quite challenging. I'm going to start with a simple demo. Let's take the following Lua program, as has already been mentioned. Here is a Mandelbrot program, very standard. I've cranked the quality handle up a bit so that it runs reasonably long so we can actually benchmark something.
Lua is a dynamically typed language used in games, Neovim, various other places. Let's take the standard Lua VM that you would download from lua.org. We're going to run it and just see how long this takes. It's a Mandelbrot. It's taken 3.2 seconds. Very good. Now what I'm going to do is our fork of this same Lua VM run through the yk technology. It displayed a lot quicker. It's gone 0.8 seconds. That's about 4x faster. Now, you can bet your bottom dollar I have cherry-picked this example of something rotten. I've chosen something where we're particularly effective. Across a wider set of Lua benchmarks, probably a geomean of 2x is about right. The point is that we aren't just speeding up Lua here. We've just started a little bit of work. This is very early stage, not quite as advanced, looking at putting this into MicroPython, which is a small Python VM.
If we have a look at MicroPython on the well-known Fannkuch benchmark. It's doing something. We've put a little to do there. You can see it's roughly linear performance. This is the normal MicroPython implementation chugging away. How long does it take? Fifteen seconds. You guessed the same thing, we have our own fork, ykmicropython. Watch at some point, somewhere around about now, notice it suddenly really starts warming up and chunking through. This one's about 2x as fast. That's not as representative of ykmicropython because I think we've put in less than 10 person days into that so far. What I'm going to try and do for the rest of this talk is motivate why we've done this, how it works, some of the technical challenges involved, and what will come next. We're very lucky this work was being funded by Shopify and the Royal Academy of Engineering. Neither are responsible for anything I say.
The work's done in collaboration with Ed Barrett, Lukas Diekmann, and Pavel Durov. One thing I just want to emphasize is that we're aiming not to change too much. Those changes you saw to yklua, here's the diff against the normal Lua VM. We've added 400 lines. We probably could have got away with adding fewer, and changed about 50. We're not talking about massive invasive changes. This is one under 5% of the codebase.
Terminology
I want to define some terminology. I've used the term virtual machine. I haven't defined it. We're talking about programming language virtual machines. They're some sort of system that contain one or more language implementations. Say, the Java virtual machine's got multiple just-in-time compilers and interpreter and so on. When I say an interpreter, and this one I know is particularly contentious, I'm talking about a simple language implementation. Something that conceptually an undergrad might be able to write. If you don't like that definition, there is a blog post where I try and define it a bit more carefully. Finally, a just-in-time compiler. This is some language implementation that runs a program, observes it, works out which points are running most often, optimizes those, compiles them into machine code, and then uses those dynamically compiled machine code versions.
Why?
Why are we doing this? Apart from the fact that it's fun. Everyone has experienced situations, I think, where your software runs too slow. Sometimes you can see a long time in advance that's going to happen. You may be running on some large data thing where you know more data is coming in, so you can predict that in nine months your program will run too slow for your situation. My experience is that often people go from not caring about performance to thinking it's an existential crisis in under 24 hours. Then they flail around in panic, and if they're hopefully sensible and intelligent, they'll profile their code. Maybe they'll try implementing better algorithms or better data structures. Maybe they'll try rewriting it in a faster language. A bit easier with LLMs, I admit. They often miss one of my favorite techniques, bearing in mind that I'm lazy, which is you can often just drop in a faster language implementation.
Maybe you upgrade your C compiler and you get a few percentage points of extra performance for free. In many languages, there are alternative, faster JIT compiling virtual machines. If you're running the normal version of Python, you've downloaded from python.org, the interpreter is not very fast. You may be able to drop in PyPy, which is a Python VM with a JIT compiler. You might get a 3, 4, 5x improvement for free. That's all you have to do. You can put the performance problem off for a long time. Does anyone recognize what these names are? That's a .NET one. We've got some Python implementations. Actually, these are Python JIT compiling VMs. These are all JIT compilers for Python. Here's some more. There's some more. More, more, more. These are the publicly available just-in-time compilers I know of for Python. There are some that are not publicly known.
Nearly all of these are dead or abandoned in such a way that they might as well be dead. There are some of them that are still alive and used, admittedly. An obvious question is, why are there so many? It can't just be people doing it for fun. I would say fundamentally, it's because just-in-time compiling VMs are really hard. There's lots of moving parts that you've got to get right. You make the smallest slip, things go splat, and you will be debugging it for a week. Because they're hard, they're expensive. Most programming languages are really quite big. A language Python, Ruby, they're really big languages in terms of the number of features they have, the complexity of their interactions. There's just a lot of stuff to implement. Say that the main Java virtual machine HotSpot has had low thousands of persons of years of effort put into it.
V8, the JavaScript VM in Chrome, a team of 50 people. These are large amounts of resources that are necessary. There are other issues. If you make a new implementation, I say maybe, you will almost certainly be in some, maybe small ways, incompatible with the existing mainstream implementations. People try your thing out. It doesn't quite run your program straight away. You ditch it, move on. You never try it again. You may also be incompatible with the existing ecosystem of modules and extensions. Again, if people can't run their stuff on your new implementation, they'll just give up and go on. Another big problem is, and this is, I think, one of the major reasons why there are so many Python JIT compilers you saw on the previous slide, they can be really difficult to evolve. You implement a new just-in-time compiler for your favorite language, you get it working for the current version of the language, and then the annoying people in charge of the language spec go and change it.
They extend it, maybe break some feature, and you've now got to cope with that. You've probably embedded deep assumptions about the existing language in it. Then you're stuck. You tend to fall further and further behind. You can see this in many well-known and sometimes once well-known JIT compilers. LuaJIT, for example, is stuck on a relatively old version of Lua.
For all these reasons, there's long been a desire to see, can we somehow automate the creation of just-in-time compilers? There are two basic approaches which happily exemplified in really the only two existing technologies. RPython is effectively the same project name as PyPy. If you've heard of one, you've heard of the other. That's a meta-tracing system. Truffle is a partial evaluation system. We do need to briefly define a bit of terminology, because what both of these systems want you to do is write a new interpreter in the host language. A subset of Python or if you're in Truffle, you write it in Java. You've got to write a new interpreter for the guest language. That guest language could be a Lua, Ruby, Python, CPU simulator, whatever. Doesn't really matter. If you do that, you will often get really good performance. I yield to no one in my admiration for these systems.
They are absolutely astonishing. The performance gains can be really good. Probably not that many people here have used them or the results of these systems. Unfortunately, I think it comes back to some of the reasons from the previous slides. They're often not fully compatible. They tend to get stuck on slightly older versions of the languages and it's difficult to keep up. Here's the challenge we've set ourselves. Can we get the benefits that you get in hopefully a faster language implementation, but you don't get stuck on old versions. There's another detail that I'll go into.
How?
Now about the particular thing that I'm introducing today. This is the one thing that perhaps I should have realized that took me years to realize. Most of this awkward squad of languages we're talking about have de facto standard implementations. Often, Ruby and Python, it's CPython, MRI Ruby, or sometimes called CRuby for Ruby. Lua is just called the Lua VM. Those standard implementations which are nearly always C interpreters are the source of truth. Those languages have language specifications with lots of semantics written down. The semantics are not complete. There's lots of stuff in libraries and so on that's not included in the specification that people expect. Basically, people run a program on their standard implementation and if it does what they expect, their program is good, whether or not there are other valid executions of their program or not. They come to rely on everything the existing C interpreter does.
We realized we had to take this as our source of truth. That's fundamentally what we've done. The demos you saw earlier hopefully give you some idea of that. If you make that decision, and it is quite a big one, I think at least in my pea brain, there's only one technique you can then use, which is you can generate a meta-tracing just-in-time compiler from a C interpreter. I don't think other techniques work, or at least I don't know how to make them work. Whenever anyone uses the prefix meta, I get very scared, because now I have to understand two things. The word and the meta word. If you're making a JIT compiling VM, the typical way it's done, if you say the JVM. They're basically method compilers. They look and find functions that are called a lot. Then they run the equivalent of like a GCC or Clang compilation process over those functions and things that they can inline.
They're quite traditional in that sense. A tracing just-in-time compiler is quite different. It's looking for loops, for loops, while loops, that execute lots of times, so exceed some counter and become hot. Then this is the real difference. When they become hot, they then record the actions the loop took during a concrete execution. They're very different to an ahead-of-time compiler. They then take those traces, that record of the execution of one iteration, optimize it, compile it into machine code. Meta-tracing, and this is the weird bit that's very easy for me to say and quite hard to internalize, record what the interpreter is doing when it's executing a particular loop in the guest language. This is so weird that I'm going to try and look at this from a couple of different directions and hope that one of them resonates with you. Let's break our view of the lifetime of running a program and a language implementation into two.
I'm going to call the first part ahead-of-time. That's what we would normally call compile time. Because a JIT compiles at runtime, that's very confusing. I've got an interpreter written in C. I'm going to compile it through, in our case, a fork of LLVM called ykllvm. You see we're quite imaginative with our names. That gives me a fairly standard executable. There's something else in there that I'll get to. Roughly speaking, not too much funny business. When it comes to me wanting to run a particular concrete guest program, I then get my compiled executable and I start running my program in it. More or less, this is just running as per normal. There's nothing really very clever going on here, until a loop exceeds a threshold and becomes hot. At that point, we then record what the interpreter does on the next iteration of that loop. We trace it.
Once we've recorded that iteration of the loop, two things happen. We immediately fall back to the interpreter so we can carry on executing. Because in a thread, we're going to start compiling that trace and optimizing it, and hopefully eventually getting out a compiled version of the trace. In the meantime, every time the interpreter has been probably continuing to execute that loop and said, is there a machine code version yet? Is there a machine code version yet? Is there a machine code version yet? Eventually there is. It can then, instead of interpreting your program, hand over to the machine code version, the JIT compiled code. That JIT compiled code is only valid for a subset of program behaviors. At some point, it will get to a point that it cannot deal with anymore and it will deoptimize back to the interpreter.
Again, this doesn't fully explain how this could work to my mind. Let's look at it a different way. Interpreters are basically just a giant while loop. You've got a program somewhere in memory. You might call it the bytecode sequence or opcodes. Whatever you want to call it. You've got a program counter. You start at the beginning. Every time you go in the while loop, you look at the current instruction at the program counter, see what it is, and do something based on that kind of instruction. If I've got a variable lookup function, I'm going to look up the variable, push the result on the stack, increment the program counter, go to the next instruction. If I've got an add instruction, I'm going to pop two things off the stack, add them, push it back, increment the program counter, move on. Interpreters are just this pattern over and over again.
They're very unimaginative. There's only one other kind of instruction we need to consider today, which is some sort of conditional or if statement. Here I'll use jump less than or equal as an example. You can think of this as just an if statement in disguise. In this case, we're going to pop a value off the stack. If it's less than or equal to zero, we're going to jump to some label. We may jump far away in the instruction sequence, forwards or backwards. If it's greater than zero, we just increment the program counter by one, carry on to the next instruction. I'll explain why I'm pulling this out as a particular thing later. Just bear in mind that it's different than the others. Because of this pattern, you can always find in an interpreter a loop that is this core loop. This is the thing that we're processing.
If I have a guest program, who cares about the syntax at the top Python syntax, Lua syntax, whatever. Let's imagine that little guest fragment is in a loop that's executed often enough that it's become hot. We're now going to trace it. Let's imagine I've written a tracing JIT compiler. Not meta-tracing at first, just tracing. I will have manually written a function that records all of the opcodes that were taken during that iteration of the loop. In this case, I've gone down the true branch of that statement. I've actually executed y as y+3. You can see here I've actually recorded a concrete execution. I haven't included the false branch in my trace. In a meta-tracing system, and I hope this syntax reminds you of the previous slide, I'm going to record the actions the C interpreter took. Hopefully you can see that's the code you saw in the previous slide with one slight difference, the jump equal has turned into a guard.
The way to think of this, and I'll go into this in a bit more detail later, is because we've recorded a concrete execution, you can only keep executing the trace if the thing at the guard is true. In this case, we went down the true branch for the if statement, so the trace below is only valid for the true branch. If you want to go down the false branch, you're going to have to do some clever deoptimization stuff, which we'll get to a little later.
How do we actually get from a C program to this running system that can do all this stuff? I've alluded partly to it that this fork of LLVM, ykllvm is part of the way we do it. It's more or less, from a makefile sense, a very easy thing to drop in. Instead of just calling your compiler directory, we have a little wrapper script. You tell it if you want to release a debug build. We pass some flags to Clang, which will often be the intermediate frontend you're using for various reasons that I will allude to later. It's very easy from that perspective. It does a couple of things. One of the most obvious, and this is not something you can see at a source code level. What I'm going to show you now is something that's in the binary, but you never see at the source level.
Inside your interpreter, it inserts recording functions. When you start recording a trace, these record functions will tell you the path through the interpreter you took. You may end up with a sequence like 0102. That tells you you did a lookup instruction and then an add instruction. Very simple. The other thing it does is that it takes LLVM's IR. That's its intermediate representation. If you think of that as the internal data structure the compiler has built up about your program, like an AST or something, we convert that into another slightly simplified representation, serialize that, and put that into the binary. Here's a little chunk of LLVM IR for yklua. Lots of detail. We convert more or less that chunk into our slightly simplified IR. The only real difference here, and we'll come back to this, is these safepoints, they weren't in the previous IR. We've actually added a little bit of information in some way.
This is the text representation. The binary representation of that is then dumped into the executable. When you load the interpreter at runtime, you've got a normal copy of the C code compiled into machine code, plus as a second part, some representation of the IR. Then at runtime, we take those IDs we recorded for the trace, 0102, get the fragments of IR that we've serialized, and stitch them together to make a trace that we can optimize and compile. That's how we close that particular circle.
How do we go about optimizing a program? Because these traces can be quite long. Hundreds of instructions long, potentially, and still worthy of doing something with. I'm sure some of you will think, I bet you this is all about inlining. That's definitely a thing. The idea of inlining, if I call a function f, the compiler will basically copy the contents of function f into the function that was calling it. That does two things. The obvious thing is, it optimizes away some of the overhead at runtime of calling a function. I don't need to set up a new frame on the stack. I don't have to deal with moving registers for whatever your crazy ABI wants me to do. Tracing naturally inlines. It doesn't even think about that. It does all that. That's very good. The main thing inlining allows you to do is expose optimization opportunities that you can see when you observe a function in a wider context.
Then you can run some standard compiler optimizations, constant folding, strength reduction, we have dead load, store analysis, value sets, and so on. We don't actually have as many as a typical compiler because we haven't got there yet. Fairly standard things. What really matters is that the interpreter can expose information it knows about the language and/or typical programs to yk that can then use that to optimize further. The classic example is, you may know that in your language some things are immutable or change so rarely that the system can assume they're immutable. As long as it can back out and deoptimize to a more general thing, it's probably worth optimizing on that basis. For example, you might know that once someone has compiled a function into an opcode sequence, that can never change, or changes so rarely that it's not worth doing.
Let me show you this concretely. Here is the standard Lua VM. Let me show you a little function that we've added, and this is R4. This is yklua. This little four-line function that I've inexpertly highlighted here, that function allows yklua to inform yk that the opcodes for a function Lua don't change. There's this little attribute, this annotation up here that says yk_idempotent. I'm just going to comment that out, recompile it, and run it and show you what happens. We recompile it. Linking takes a little while. Then we'll run our Mandelbrot program again. Notice this isn't yklua. It was 0.8 seconds before. Now it's 2.93. It's not quite as slow as the normal Lua implementation, but we've slowed it down 3.5x, just by removing that hint. This gives you a sense of how powerful it is when you can express these hints about the program and the way it's run to the system.
However, the problem with the one that I've just showed you, yes, it's very effective. It's so effective that if I actually tried to look at it in detail, we would be overwhelmed by detail. I'm going to show you a simpler one where we can actually as humans get our head around what's happening. We are going to look at the ADDI instruction in Lua. This adds an immediate to a variable. If you see a statement like x + 1, it becomes the ADDI statement, provided the integer is a small value. I think it's a signed 8-bit value from memory. We'll get to that. We've done something that I'm going to try and demonstrate and then explain to you briefly how it works. Here is a very important program. It's a profound program. It's a loop that counts and prints out a value. Bearing in mind that where we see sum + 1, that integer can be a signed 8-bit value.
Would anyone like to choose a value between 50 and 127? 64. Remember 64, because we'll need to see that. I'm going to run this program. I'm going to turn on some debugging output so we can see what's happening. We run it. I have no idea if that's the right answer. It looks plausible. When I look at this, what we're looking at here is both the trace IR, so this is post-optimized, and the x86 code that's led to. The first thing here, there's the constant 64. Trust me, I'm not lying on this one. It really was the value. I don't have 127 programs lurking around. Somehow, we've burnt that into the trace. Even more interestingly, you can see there's a pattern of instructions here. We load the 64-bit value from memory. We add 64 to it. We store that new value back to the same heap address.
We've been able to optimize that, as you would hope, to a single x86 instruction. That 0x40, so, whoever chose a power of 2, very good thinking. It's a nice round number in hex. We really have been able to burn that Lua value into x86 machine code. Again, here, as we know, as the programmer, if we see the ADDI instruction, that's really a constant integer. We want it to become a constant integer in the machine code. It doesn't take much work. The way the OP_ADDI code works, it defers to this macro called op_arithI. Let's have a look at that. What I'll do, I'm just going to delete this very briefly. This little chunk of code you're seeing here is the normal Lua VM. All we did was we added a simple call to a function called yk_promote. What yk_promote says, give me a value anywhere between 8 and 64 bytes, effectively.
I will now say that value is constant in the context of this trace. I'm going to leave a guard behind to make sure that if you've got that wrong, ID optimizing can cope with the situation. That's all I had to do to turn 64 written in the Lua source code into a 64 immediate in x86 machine code. Again, I'm exposing constantness that I know about the language to yk as the system. This is something that JIT compilers love to do, and tracing JIT compilers get to do a lot of it.
I kept mentioning guards. What I've said is the trace is valid as long as the value we see the next time I execute the trace is true. If the guard evaluates to true, I keep going. What happens if it becomes false? We've now got to deoptimize. We seem to have really made a rod for our own back here, because we've got to deoptimize back to, let's say, normal C code, obviously compiled into machine code. The way this works is roughly as follows. I've got a stack of frames when I start a program, so I'm going to start with a frame on the stack for the main function just as normal. It's probably going to call a function called something like interpreter. You might imagine that when I execute the JIT compiled code for a particular loop, I might create a new frame on the stack.
That's the obvious way. Actually, these two frames get mixed together. When you move into just-in-time compiled code, it takes over the C interpreter stack. It reads and writes from some of the same places. It does grow the stack additionally when it needs to because it's obviously doing additional work. Somehow, when we hit a guard that's false, we've got to take the system that looks like that and put it back like that so we can jump back to the normal ahead-of-time compiled code from Clang. How can we do that? Here's that yk IR we saw earlier. This is the thing that gets serialized into the interpreter. I mentioned these safepoint lines. In essence, wherever there's a conditional branch or a function call, you get a safepoint. These are the points in the system where control flow can diverge, and you might have to deoptimize. You can see from the first one, there's a list of variables.
Those are the live variables at that point in the program. We've got to put all of those live variables back in the same state that Clang compiled the ahead-of-time binary for. Associated with each safepoint, there is some LLVM, the concept of a stack map. It will tell us things like the following. The variable %0_0, that's going to live at stack offset 0x40 and RAX. We have to put those values in those places. It might say the variable %0_1 is the constant line. Great. That's perfect. We don't have to do anything. It might say that %0_2 is in two registers and so on. This deoptimization thing puts the system back in all of these places, jumps to the right place, carries on.
Technical Challenges
There's an obvious problem or two. One of them, if I'm executing in the just-in-time compiled code and I have C code that takes the address of a variable on the stack, it might be down here. Then when I go back to the interpreter, that address is not valid. How am I going to deal with that? For better or for worse, we have to have a second shadow stack on every thread. We'll call the normal stack the C stack. When you take the address of a variable, that will end up on the shadow stack. There's a frame for every function in the normal program. Those addresses are stable. Even when you deoptimize, you've got an address from the right-hand side, not from the left-hand side. The system doesn't know that it's gone into JIT compiled mode or gone back to the C interpreter. It's completely transparent.
There are, though, consequences. A shadow stack slows things down a bit. Stack maps, they're not exactly an afterthought in LLVM, but they are a less loved feature. They haven't received as much polish. There are some optimization passes that don't respect them. Some of the code generators unfortunately put instructions in places that they shouldn't. We actually have to turn off some optimizations in order for this stuff to work reliably. In fact, we actually do pay a penalty for this, and also those record functions you saw earlier. Roughly, and this is going to vary, the interpreter without the JIT on is going to be 3x, 4x slower than normal. When you saw a performance advantage earlier, the JIT is winning back that cost and more. That's what we have to overcome.
I want to give you a sense of a different challenge, because some of you will remember, I'm sure, that there was a tracing just-in-time compiler way back in Firefox, its first JavaScript VM called TraceMonkey. TraceMonkey was relatively quickly replaced because it didn't have great performance. It wasn't a great VM. People have then, to my mind, overgeneralized from that that all tracing compilers are bad. I hope I've shown you here that that's probably not true. There's probably a context where they're a good idea. Not for everything, but some places. Let me give you a flavor of why people might have thought that there are some really bad issues. I'm going to show you a bad case for tracing. Here's a Lua loop. Let me ask you a question. Is this a loop? You can guess from the horrendous tone in my voice that I've asked you a very leading question.
Because ahead-of-time, this is obviously a loop. You're scared. You know that there's going to be something fishy going on in a bit. Normally, that's obviously a loop. It doesn't transform into a flying frog or something. From the point of view of tracing and iteration, the answer turns out to be a lot weirder and harder and boils down to maybe? Here are the opcodes that I might get out of the Lua dynamically compiling opcode thingy. I've changed this a bit, but it gives you a flavor. I've got start and end labels. Look up a variable. Jump less than or equal instruction and so on. Let's say the loop has become hot and I start tracing the next iteration. Two things can happen. I'm going to start at the top, and if i is greater than zero, the jump less than or equal just falls into the next instruction.
We go down to the end of the loop, jump back to the start. We have now closed the loop. We've traced an iteration. A trace optimizer as in yk will eat this for breakfast. It is so happy. It will do an excellent job. You're going to get really good performance. You might get unlucky. If i was zero minus one or whatever, that jump less than or equal would immediately jump past the body of the while loop to the end. We're still recording. We aren't going to close the loop. In fact, if you're unlucky, sometimes you go for miles and miles, and via some torturous thing come back to the beginning and you end up with these ludicrously long traces. Fundamentally, there is no way around this. You can ameliorate the problem so we have a branch that's not finished where, in essence, we say, if you got here and you started there, that's probably bad and you should give up.
You can't ever fully fix it because you start recording not knowing what you're about to execute. When you get bad traces of whatever kind, your performance is much worse. I think this is one of the reasons why sometimes people get the heebie-jeebies about tracing. I think we can ameliorate it, as I said, but you can never fully get rid of this. This is a real challenge.
Recap
Let's go back over what I've shown you. It is possible to take in a C interpreter and more or less for free with very few lines of code change, get a just-in-time compiler out. Although I've cherry picked the data a little, you can get some sense that it can speed things up. I'm presenting alpha quality software here. It's not production ready, but it is way beyond your average research prototype. I hope that we're able to keep pushing this further.
What's Next?
What's next? We don't support all of LLVM. There are things, if you say, you use vector instructions or vector types, we just go, to do. Fixing that is not rocket science, but there's a lot of engineering behind it. We would like to do more optimization. Escape analysis is a really nice optimization as an example, where if you've got a loop and you allocate some memory, read and write to the heap, free the memory in the same iteration, you can often just not do the allocation at all if that memory pointer hasn't escaped. Very effective in trace space compilers. We would like to do those sorts of things. They will give us quite a bit more speed-up. I would think our geomean in yklua, probably 3x seems quite plausible. We've got MicroPython as a work-in-progress interpreter. I think we'll probably look at Pico Python next. Hopefully, we can then graduate to the big boys, as it were, the CPython, CRubys. In one sense, there's nothing intellectually different about those, but they're bound to use all sorts of features we just haven't had a chance to implement yet. That's what's coming next. You can download and play with this yourself. It's open source. You get to keep all the pieces.
Questions and Answers
Participant 1: I'm sort of a Java developer background from pre-millennium. This feels very much modern HotSpot with the decompiling, going back into compiled mode, which is very cool. Do you have to do machine instruction setups for each language, like for each interpreter?
Laurence Tratt: HotSpot's the standard JVM these days. You and I are at the vintage, where you probably remember before HotSpot was a thing. HotSpot is probably the best just-in-time compiler ever, best VM that includes actually now three JIT compilers. Probably the best one ever implemented. It's astonishingly effective. You may remember from many slides here, I mentioned Jython. That is Python running on the JVM. It's really slow. It's interesting. HotSpot is not a great vehicle for running some kinds of languages, which is why there's room for a project like this. yk is doing all of the machine-specific stuff for you. You don't need to know if you're on x86. We only run on x86. Imagine we had written an ARM backend. Your interpreter would then JIT compile on ARM or whatever. That's all totally transparent to you as the interpreter author. You will have to adjust your interpreter a bit for yk, because you want to expose this constantness thing, and you have to tell it where loops are a bit. You do have to do some adjustments, but they're not platform-specific in the way that you might fear.
Participant 2: Just so I understand something here. It looked like when you were modifying the Lua code, was that the Lua compiler that you were modifying?
Laurence Tratt: That was the Lua virtual machine, yes, the Lua interpreter I was modifying.
Participant 2: Then does that mean that if they release a new version of Lua, you would have to reapply all of your changes to that new version?
Laurence Tratt: Yes. There's 400 lines of code. I reckon I can rebase that in an afternoon.
Participant 2: That's how you can still argue that you can update and drift. You can really easily create a new version of the JIT.
Laurence Tratt: Exactly. Yes. I think that's what's really quite different here. There are a few lines where we've invasively changed things, but actually, those are generally the stable parts of the system. We don't really change the libraries and so on a great deal. The hope is that over time, keeping this up to date is a relatively easy effort. Relatively.
Participant 3: I'm also new to JIT. I had a question about the underlying C code where you add the guards and the checkpoints. I presume, does the overhead of that just go to zero because of the branch predictor that you're always hitting the safe lane until you don't?
Laurence Tratt: Branch predictors are really good. They aren't perfect. It takes them a while to learn your code. Interpreters themselves, actually, in their traditional implementation, are actually surprisingly branch predictor unfriendly. There is a concept which is called threaded dispatch. What you would normally do, you remember I had that big switch statement, you would go back to the beginning of the switch statement and then dispatch. What you do in threaded dispatch is you look up where you're going to go at the end of each opcode and go to it. That makes it more branch predictor friendly. No, the overhead of all of those things never goes to zero, although they can be very effective. What I haven't fully been able to show you is, when we compile a trace, many of the guards will disappear completely. We're able to optimize them away because you can prove from the constantness. When you saw that three-and-a-half slowdown, probably the three-and-a-half slowdown had five times as many guards in as the faster version. If you take even a little bit of overhead for some of those, if we're able to get rid of that, it's part of the way that the performance adds up.
Participant 3: If you have fewer guards and you do go down the wrong path, you just have a much worse picture to reconstruct for the deoptimized.
Laurence Tratt: Yes, indeed. Yes, that's when we have to deoptimize, put the system back, because the normal interpreter can handle any program behavior. That's when we have to go back to it as the general source of truth.
Participant 3: You could almost push that to the limit of no guards. You can almost have one guard per program, if you're really confident.
Laurence Tratt: I have never thought of it like that. I don't think so, because, again, that would require you to look forward. You'd have to know that in a future state, you're going to violate the trace you've recorded. I think you do need to see them as you're going along.
See more presentations with transcripts
