4x Faster Interpreters? The Meta-Tracing Secret EXPOSED Transcript, AI Summary & Key Points

00:10 Good afternoon everyone. 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 the dynamically tight language or the scripting languages, the lures, the rubies, the pythons. But also there are quite a lot of other language implementations out there that they may not run as fast as you would like.

00:28 CPU companies have CPU simulators and so on. And what I'm going to do is show you that we can take in existing language implementations and automatically add a just in time compiler to them. So I'm going to introduce a new technology we developed called YK. Now the good news is that uh it does something fun. The problem is the showing performance is quite challenging.

00:54 So I'm going to start with a simple demo and hope that you are a kind of forgiving audience and will forgive me for taking something that's a little artificial. So let's um take the following lure program as has already been mentioned. So here is a mandle program very standard. I've cranked the quality handle up a bit so that it runs reasonably long so we can actually benchmark something.

01:19 Um, for those of you who don't know Lure, it's a dynamically typed language used in games, Neoim, various other places. So, let's take the standard Lure VM that you would download from lure.org. We're going to run it and just see how long this takes. If I can type properly. Okay, so it's a mandlerot. Excellent. And it's taken 3.2 seconds. Very good.

01:48 Now what I'm going to do is our fork of this same lure VM run through the YK technology. Okay, so it displayed a lot quicker, right? It's gone8 seconds. So that's about 4x faster. Now you can bet your bottom dollar I have cherry picked this example something rotten, right? So I've chosen something where we're particularly effective across a wider set of uh lower benchmarks.

02:14 probably a geomine of 2x is about right. But the point is that we aren't just speeding up say lure here. So we've just started uh a little bit of work. This is very early stage not quite as uh advanced uh looking at uh putting this into microython which is a small python VM. So if we have a look at microython on the well-known fancush benchmark if you're German I'm sorry I can't pronounce it properly.

02:41 So it's doing something. And we've put a little to-do there. So you can see it's kind of roughly linear performance. So this is the normal micro Python implementation chugging away. How long does it take or any second now? Okay, 15 seconds. So you kind of guess the same thing. We have our own fork YK microython. Watch at some point somewhere around about now notice it suddenly really starts warming up and chunking through.

03:10 Yeah. So this one's about 2x as fast. Now that's not as representative of YK MicroPython because I think we've put in less than 10 person days into that so far. So 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. So we're very lucky this work was being funded by Shopify and the Royal Academy of Engineering.

03:35 Uh neither are responsible for anything I say. The work's done in collaboration with Ed Barrett, who's over there, Lucas Deman, and Pavle Djurov. One thing I just want to emphasize before I go any further is that we're aiming not to change too much. So those changes you saw to YK Lure, here's the diff against the normal Lure VM. So we've added 400 lines.

03:57 We probably could have got away with adding fewer and changed about 50. So we're not talking about massive invasive changes. This is one under 5% of the codebase. But before I go any further again, I want to define some terminology because otherwise people will start throwing tomatoes at me. So I've used the term virtual machine. I haven't defined it.

04:18 So we're talking about programming language virtual machines, there's some sort of system that contain one or more language implementations. If you've got say the Java virtual machines, got multiple just in time compilers, an 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.

04:35 So something that you know 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. So please save your tomatoes for your computer screen. And finally, a just in time compiler. So this is some sort of 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.

05:05 Good news, that's more or less the end of the definitions. So why are we doing this? I mean, apart from the fact that it's fun. So 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 know, you may be running on some sort of large data thing where you know more data is coming in.

05:26 So you can predict that in nine months your program will run too slow for your situation. But my experience is that often people go from not caring about performance to thinking it's an existential crisis in under 24 hours. And then they sort of flail around and panic. And if they're hopefully uh sensible and intelligent, they'll profile their code.

05:44 Maybe they'll try implementing a uh better algorithms or better data structures. Maybe they'll try rewriting it in a faster language. Bit easier with LLMs. I've admits 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.

06:10 But in many languages, there are alternative faster JIT compiling virtual machine. So 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 pi, which is a Python VM with the JIT compiler. you might get a sort of three, four, fivex improvement for free. That's all you have to do and you can put the performance problem off for a long time.

06:36 But does anyone recognize what these names are? Yes, sir. Do you recognize them? >> Yes, that's a net one. Yes. >> Java. >> Yes, indeed. So, we've got some Python Python implementations. Actually, these are Python JIT compiling VMs. So, these are all JIT compilers of Python. Here's some more. There's some more, more, more, more. So, these are the publicly available just in time compilers I know of for Python.

07:10 There are some that are not publicly known. Um, 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, but an obvious question is you why are there so many? I mean, it can't just be people doing it for fun. And I would say fundamentally it's because just in time compiling VMs are really hard.

07:34 There's lots of moving parts that you've got to get right. And you make the smallest slip, things go splat, and you will be debugging it for a week. And because they're hard, they're expensive. I mean most programming languages are really quite big. You know a language Python, Ruby, they're really big languages in terms of the sort of number of features they have, the complexity of their interactions.

07:56 There's just a lot of stuff to implement. So say that the uh main Java virtual machine hotspot has had low thousands of persons of years of effort put into it. Um V8 the JavaScript VM in Chrome team of 50 people. These are large amounts of resources that are necessary. But there are other issues. If you make a new implementation, you'll I say maybe you will almost certainly be in some maybe small ways incompatible with the existing mainstream implementations.

08:29 People try your thing out. It doesn't quite run that uh 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. And again, if people can't run their stuff on your new implementation, they'll just give up and go on. And 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.

08:56 So 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, extend it, maybe break some feature, and you've now got to cope with that. But you've probably embedded deep assumptions about the existing language in it and then you're stuck and so you tend to fall further and further behind and you can see this in many well-known and sometimes once well-known JIT compilers.

09:26 Lujit for example is stuck on a relatively old version of Lure. So for all these reasons there's long been a desire to see can we somehow automate the creation of just in time compilers and there are two basic approaches which happily uh exemplified in the really the only two existing technologies. So um our Python is effectively the same project name as pi.

09:52 So if you've heard of one you've heard of the other. So that's a metatracing system. Truffle is a partial evaluation system and 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. So a subset of Python or if you're in truffle you write it in Java. So you've got to write a new interpreter for the guest language and that guest language could be a lure, Ruby, Python, CPU, simulator, whatever doesn't really matter.

10:22 And 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 really good, but probably not that many people here have used them or the results of their of these systems. And unfortunately, I think it comes back to some of the reasons from the previous slides.

10:45 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. So 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 all versions? And there's another detail that I'll get going into.

11:07 So 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 a de facto standard implementations. So often you know Ruby and Python it's CP Python MRI Ruby or sometimes called C Ruby for Ruby. Lure is just called the Lure VM.

11:34 Those standard implementations which are nearly always C interpreters are the source of truth. Yeah, those languages have language specifications with lots of semantics written down but 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. And basically people run a program on those standard implementation and if it does what they expect their program is good whether or not there are other um valid executions of their program or not.

12:03 So they come to rely on everything the existing C interpreter uh does. So we realized we had to take this as our source of truth and that's fundamentally what we've done and and the demos you saw earlier hopefully give you some idea of that and if you make that decision and it is quite a big one I think at least in my prain there's only one technique you can then use which is you can generate a metatracing just in time compiler from a C interpreter I don't think other techniques work or at least I don't know how to

12:37 make them So whenever anyone uses the prefix meta, I get very scared because now I have to understand two things. The the word uh and the meta word. Um so if you're making a JIT compiling VM, there's 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 and then they kind of run the equivalent of like a GCC or clang compilation process over those functions and things that they can inline.

13:06 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 time. So exceed some counter and become hot. And then this is the real difference. when they become hot, they then record the actions the the loop took during a concrete execution. So they're very very different to an ahead of time compiler.

13:35 They then take those traces that that record of the execution of one iteration, optimize it, compile it into machine code. Metatracing and this is the wee 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. So 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.

14:03 So let's break our view of um the lifetime of of running a program and 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, but because a JIT compiles at runtime, that that's very confusing. So, I've got an interpreter written in C. I'm going to compile it through, in our case, a fork of LVM called Y LVM.

14:26 You see, we're quite imaginative with our names. Um, and that gives me a fairly standard executable. There's something else in there that I'll get to in a minute. So, but 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.

14:47 And 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. And at that point, we then record what the interpreter does on the next iteration of that loop. We trace it. And 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 optimize it optimizing it and hopefully eventually

15:15 getting out a compiled version of the trace. In the meantime, every time the interpreter's been probably continuing to execute that loop, it said, "Is there a machine code version yet? Is there a machine code version yet? Is there a machine code version yet?" And eventually there is. And it can then instead of interpreting your program hand over to the machine code version, the JIT compiled code.

15:35 But that JIT compiled code is only valid for a subset of program behaviors. So at some point it will get to a point that it cannot deal with anymore and it will deoptimize back to the interpreter. Now how again this doesn't fully explain how this could work to my mind. So let's look at it a different way. Interpreters are basically just a giant while loop.

16:01 You've got a program somewhere in memory. You might call it the byte code sequence or op codes, whatever you want to call it. You've got a program counter. You start at the beginning and 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.

16:18 So, 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.

16:37 They're very, very unimaginative. There's only one other kind of instruction we need to consider today, which is some sort of conditional or if statement. So here I'll me uh use jump less than or equal as an example, but 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.

17:01 So 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, but just bear in mind that it's different than the others. Now, because of this pattern, you can always find in an interpreter a loop that is this core loop.

17:22 And this is the thing that we're kind of processing. So, if I have a guest program, who cares about the syntax, the top, Python syntax, Lewis syntax, whatever. Let's imagine that little guest fragment is in a loop that's executed often enough that it's become hot. So we're now going to trace it. So let's imagine I've written a tracing JIT compiler. Not metatracing at first, just tracing.

17:47 I will have manually written a function that records all of the op codes that were taken during that iteration of the loop. So in this case, I've gone down the true branch of that statement. I've actually executed y is y + 3. You can see here I've actually recorded a concrete execution. and I haven't included the false branch in my trace in a metatracing system.

18:08 And I hope this syntax reminds you of the previous slide. I'm going to record the actions the C interpreter took. So hopefully you can see that's kind of the the code you saw in the previous slide with one slight difference. The the jump equal has turned into a guard. And what the way to think of this, and I'll go to this 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.

18:37 So in this case, we said, look, 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. So how do we actually get from a C program to this running system that can do all this stuff?

19:00 And I've kind of alluded partly to it that this fork of LVM YKLVM is part of the way we do it. So it's more or less a fairly easy thing from a make file sense. Uh 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 re release or debug build. We pass some flags to clang which will often be the intermediate front end you're using for various reasons that I will allude to later but it's very easy from that perspective and it does a couple

19:29 of things. One of the most obvious and this is not something you can see at the source code level. So 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 uh inserts recording functions. So when you start recording a trace, these record functions will tell you the path through the interpreter you took.

19:49 So you may end up with a sequence like 0 1 02 that tells you you did a lookup instruction and then an add instruction. Very simple. The other thing it does is that it takes LRVM's IR. So that's its intermediate representation. It's not a term I'm very fond of if I'm honest. If you think of that as the internal data structure the compiler's built up about your program like an a or something, we convert that into another slightly simplified representation, serialize that and put that into the binary.

20:21 So here's a little chunk, don't worry, I'm not going to test you on this. A little chunk of LVM IR for YK lure. 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 safe points. they weren't in the previous IR. So we've actually added a little bit of information in some way.

20:44 This is the textual representation. The binary representation of that is then dumped into the executable. So 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. And then at runtime we take those ids we recorded for the trace 0 1 02 get the fragments of IR that we've serialized and stitch them together to make a trace that we can optimize and compile.

21:11 So that's how we kind of close that particular circle. So 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. So, I'm sure some of you will think, okay, I bet you this is all about inlining. And that's definitely a thing. So, for those of you who maybe aren't familiar with that term, the idea of inlining, if I call a function f, the compiler will basically copy the contents of function f into the function

21:43 that was calling it. Now, 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 AI wants me to do. Tracing naturally in lines. It doesn't even think about that. So it does all that.

22:00 That's very good. But 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. And then you can run some standard compiler optimizations. You know, constant folding, strength reduction. We have uh 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.

22:22 Um, but fairly standard things. But 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. So the classic example is you may know that in your language some things are um 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.

22:52 It's probably worth optimizing on that basis. For example, you might know that uh once someone has compiled a function you know into an op code sequence that can never change or changes so rarely that it's not worth doing. So let me show you this concretely. So, here is the standard Lu VM. Actually, maybe it's easier if I do this. No, can't do it. Um, sorry, I was going to change the colors, but it doesn't work today.

23:16 Um, let me show you a little function that we've added in this is R4. This is YK Lure. So, this little four-line function that I'm I've inexpertly highlighted here and the syntax highlighting is not helping. that function allows YK lure to inform YK that um the op codes for a function lure don't change. And can you see this little attributes, this annotation up here that says YK and potent?

23:46 I'm just going to comment that out, recompile it, and run it and show you what happens. So, we recompile it. Linking takes a little while. Longer than I'd like. And then we'll run our mandle program again. So notice this isn't wala. It was8 seconds before. Now it's 2.93. It's not quite as slow as the normal lure implementation, but we've slowed it down what 3 and 1/2x just by removing that hint.

24:21 So this I gives you a sense I hope of how powerful it is when you can express these hints about the program and the way it's run to the uh system. However, the problem with the one that I've just shown you, yes, it's very very effective. Um, but it's so effective that if I actually tried to look at it in detail, we would be overwhelmed by detail. So, I'm going to show you a simple one where we can actually as humans kind of get our head around what's happening.

24:48 We are going to look at the add i instruction in lure. So, this adds an immediate to a variable. So if you see a statement like x + one, it becomes the add i statement provided the integer is a small value. I think it's assigned 8 bit value from memory. We'll get to that in a second. And we've done something that I'm going to try and demonstrate and then explain to you briefly how it works.

25:10 So here is a very important program. Actually, let's see if we can bump that up a little. Can I bump font size? No, not today. There we are. Right. It's a profound program. It's a loop that counts uh and prints out a value. Let me just move the left hand side's got a bit squished. There we are. Okay. Right. So, bearing in mind that the where we see sum plus one uh that integer can be assigned 8 bit value.

25:37 Would anyone like to choose a value between let's say 50 and 127ish? >> So, 64 >> 64. >> Do I want to know why you chose 64? I like the way you think. Okay. So, remember 64 because we'll need to see that in a second. Um, I'm going to run this program and I'm going to turn on some debugging output so we can see what's happening. So, we run it. I have no idea if that's the right answer.

26:09 It looks plausible. But when I look at this, let's bump this up a little. So what we're looking at here is both the trace IR. So this is post optimized and the x86 code that's led to. So the first thing here there's the constant 64. So that really is, trust me, I'm not lying on this one. It really was the value. I don't have like 127 programs lurking around.

26:33 Um so somehow we've burnt that into the trace. But even more interestingly, you can see there's a pattern of instructions here. We load a 64-bit value for memory. We add 64 to it. We store that new value back to the same heap address and we've been able to optimize that as you would hope to a single x6 uh x86 instruction and that 0x40. So whoever chose a power of two very good thinking it's a nice round number in hex.

27:00 We really have been able to burn that lure value into x86 machine code. So again here as we know as the programmer if we see the add I instruction that's really a constant integer. So we want it to become a constant integer in the machine code and it doesn't take much work. So the way the op addi code works it defers to this uh macro called op ariththi.

27:26 So let's have a look at that. And what I'll do I'm just going to delete this very briefly. So this little chunk of code you're seeing here is is the normal LU VM and all we did was we added a simple call to a function called YK promote and 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.

27:54 I'm going to leave a guard behind to make sure that if you got that wrong IDOtimize and can cope with the situation. But that's all I had to do to turn 64 written in below 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. Now, this is something the JIT compilers love to do and tracing JIT compilers get to do a lot of it.

28:28 So I kept mentioning guards and 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. So if the god evaluates to true I keep going. What happens if it becomes false? We've now got to deoptimize but 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.

28:55 So 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. And you might imagine that when I execute the JIT compiled code for a particular loop, I might create a new frame on the stack.

29:14 That's kind of the obvious way. But actually these two frames get mixed together. So when you move into just in time compiled code, it kind of 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. And 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 client.

29:43 How the hell can we do that? So here's that ykir we saw earlier. This is the thing that gets serialized into the interpreter. And I mentioned these safe point lines. So in essence, wherever there's a conditional branch or a function call, you get a safe point. These are the points in the system where control flow can diverge formally speaking and you might have to deoptimize.

30:04 And 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. So associated with each safe point there is some LLVM the concept of a stack map. So it will tell us things like the following.

30:25 The variable percent 0_0 that's going to live at stack offset 0x40 and rax. So 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 02 is in two registers and so on. So this deoptimization thing puts the system back in all of these places, jumps to the right place, carries on.

30:52 But there's an obvious problem or two. One of them, if I'm executing in the just in time compile code and I have C code that takes the address of a variable on the stack, it might be down here and then when I go back to the interpreter, that address is not valid. So how am I going to deal with that? Well, for better or for worse, we have to have a second shadow stack on every thread.

31:14 So, we'll call the normal stack the C stack. Um, and when you take the address of a variable, that will end up on the shadow stack. So, there's a frame for every function in the normal program, those addresses are stable. So, even when you uh deoptimize, you've got an address from the right hand side, not from the left hand side. So that's how we're able to ensure that we can make the system be it doesn't know that it's gone into JIT compiled mode or gone back to the C interpreter.

31:40 It's completely transparent. There are though consequences. Shadow stack slows things down a bit. Stack maps. They're not exactly an afterthought in LVM, but they are a less loved feature. So they haven't received as much polish. There are some optimization passes that kind of don't respect them. Some of the code generators unfortunately put instructions in places that they shouldn't.

32:06 So we actually have to turn off some optimizations in order for this stuff to work reliably. And 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, but roughly the interpreter without the JIT on is going to be three 4x slower than normal. So when you saw a performance advantage earlier, the JIT is winning back that cost and more.

32:32 So that's what we have to overcome. And 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 Trace Monkey. And uh Trace Monkey was relatively quickly replaced because it didn't have great performance. It wasn't a great VM.

32:55 People have then to my mind overgeneralized from that that all tracing compilers are bad. And 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. But let me give you a flavor of why people might have thought that there are some really bad issues. And I'm going to show you a bad case for tracing.

33:12 So here's a lure loop. And let me ask you a question. Is this a loop? Now, you can guess from the horrendous tone in my voice, thank you, that I've asked you a very leading question because ahead of time, this is obviously a loop, right? You're scared. You know that there's going to be something fishy going on it, but normally there's there's no that's obviously a loop.

33:37 Like, it doesn't transform into a sort of flying frog or something. But from the point of view of tracing an iteration, the answer turns out to be a lot weirder and harder and boils down to maybe. So here are the op codes that I might get out of the lure dynamically uh compiling op code thingy. So I've changed this a bit but it gives you a flavor. So I've got start and end labels look up a variable jump less than or equal instruction and so on.

34:02 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 I get to 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. Uh a trace optimizer like as in YK will eat this for breakfast.

34:27 It is so happy. It will do an excellent job. You're going to get really good performance. But you might get unlucky. If I was 0 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, so we aren't going to close the loop. In fact, if you're unlucky, sometimes you kind of go for miles and miles and miles and via some torturous thing come back to the beginning and you end up with these ludicrously long traces.

34:59 Fundamentally, there is no way around this. You can ameliate the problem. So, we have a branch that's not finished where in essence, we sort of say if you got here and you started there, that's probably bad and you should give up. Um, but you can't ever fully fix it because you start recording not knowing what you're about to execute. And when you get bad traces of whatever kind, your performance is much worse.

35:26 And I think this is one of the uh reasons why sometimes people get the heebie-jebies about tracing. And I think we can ameliate it as I said, but you can never fully uh get rid of this. So this is a real challenge. Okay, let's go back briefly over what I've shown you. I hoped it is possible to take in a C interpreter and more or less for free with very few uh lines of code change get a just in time compiler out and although I've cherrypicked the data a little you can get some sense that it can speed things up.

35:57 Now I'm presenting alpha quality software here. It's not production ready but it is way beyond your average research prototype. So I hope that we're able to keep pushing this further. So what's next? Well, we don't support all of LVM. There are things if you say use vector instructions or vector types, we just kind of go, oh well to-do, yeah, fixing that is not rocket science, but there's a lot of engineering behind it.

36:26 We would like to do more optimizations. So 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 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.

36:45 So we would like to do those sorts of things and they will give us quite a bit more speed up. I would think our geomine and yk lure probably 3x seems quite plausible. And so we've got MicroPython as a work in progress uh interpreter. I think we'll probably look at Pico Python next. And hopefully we can then graduate to the the big boys as it were, the CPython, C Rubies.

37:04 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. So 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. And with that, thank you very much for listening. >> Java developer.

37:30 >> I'm sort of a Java developer background from premillennium. >> Um, this feels very much modern hotspot with the decompiling going back into compiled mode which is very cool. I was just curious do you have to do sort of what machine instruction setups for each language like for each interpreter? >> Uh so let for those because yes right let me let me unpack one bit there because I think it's a really good question.

38:04 So hotspots's the standard JVM these days. So you and I are yeah you and I are at the vintage so where you probably remember before hotspot was the thing. Um, so Hotspot is probably the best just in time compiler ever. Well, best VM that includes actually now three JIT compilers. Um, probably the best one ever implemented. It's astonishingly effective.

38:25 So, um, you may remember from many slides I mentioned Jython. So, that is Python running on the JVM. It's really slow. So, it's interesting the hotspot is not a great vehicle for running some kinds of languages, which is why there's room for a project like this. So YK is doing all of the machine specific stuff for you. You don't need to know if you're an x86 or we only run on x86, but imagine we had written on our back end.

38:50 Your interpreter would then jit compile an arm or whatever. So that's all totally transparent to you as the interpreter author. But 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. So you do have to do some adjustments, but they're not platform specific in the way that you might fear.

39:11 Thank you. >> Um, so sorry, 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? >> That was the Lua virtual machine, which Yeah, the C the Lua interpreter I was modifying. Yeah. >> Okay. So 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?

39:32 >> Yes. >> Doesn't that Yeah. Go on. >> There there's 400 lines of code, so I reckon I can rebase that in an afternoon. Okay. So that's that's how you can still argue that you can um they update and drift you can really easily create a new version of the um JIT. >> Exactly. >> Yes. So I think that's what's really quite different here. You know you've got there's a few lines where we've invasively change things but actually those are generally the stable parts of the system.

39:57 We don't really change the libraries and so on a great deal. Um, so the hope is that over time keeping this up to date is a relatively easy effort >> relatively. >> Yeah. So I'm also new to Jet, so thanks for the talk. Um, >> my pleasure. >> I had a question about the underlying C code where you add the guards and the checkpoints. So 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.

40:28 >> Um, so branch predictors are really good. they aren't they aren't perfect. So it takes them a while to learn your code. Um and interpreters themselves actually in their their traditional implementation are actually surprisingly branch unfriend uh branch predictor unfriendly. So there is a concept it has the worst name ever. So I'm going to say it and then please forgive me for even using the term which is called threaded dispatch.

40:53 And the long story short is what you would normally do you remember I had that big switch statement. So you would >> uh 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 op code and go to it. That makes it more branch predictor friendly. Um so no the overhead of all of those things never goes to zero although they can be very effective.

41:17 Um but what I haven't fully been able to show you is we're often when we compile a trace mo many of the guards will disappear completely. we were able to optimize them away because you can prove from the constantness. So when you saw that three and a half slowdown probably the three and a half slowdown probably had five times as many guards in as the faster version.

41:37 So 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. >> So as a followup if you have fewer guards and you do go down the wrong path you just have a much worse picture to reconstruct for the deop. >> Yes indeed. Yes. That's when we have to deoptimize, put the system back because the normal interpreter can handle any program behavior.

42:00 So that's when we have to go back to it as the general source of truth. >> So you could almost push that to the limit of no guards and >> sorry. Say again. >> You can almost have one guard per program if you're really confident. >> Uh I have never thought of it like that. I don't think so because uh again that would require you to look forward. you'd have to know that in a future state you're going to violate uh the trace you've recorded.

42:24 So I think you do need to see them as you're going along. >> I guess that was just degenerate example but thank you. >> Yeah, I never thought of that before.