Nice, do you know whether this DSL was ever used successfully fir other endeavours (abstract interpretation, lowering to Why3, any kind of symbolic execution? or a language server?). I've been looking for a 'flex/bison with complete semantics' and it might be a piece of the puzzle.
I don't know -- there were at least a couple papers about it, but I haven't been following. At the time it was first announced I used some of the ideas in one of my projects (https://github.com/darius/idel/blob/master/src/opcodes.awk) but unfortunately didn't develop it further.
The main difference I see is this project seems to be using C++ (plus C macros?) directly instead of a DSL. And some llvm magic thrown in for good measure.
Fair. I think of DSLs as a way of thinking about the program you want to write; if a scheme is realizable with few compromises in an existing language, it can still be considered "DSL style". SICP calls this style "stratified design".
You can do all sorts of “stratified design” with C++ templates which I assume is underneath the covers of this system. boost::spirit is probably the most excessive use of this that I’ve seen so far.
JavaScript doesn't have a standardized bytecode. But, I suppose you could design one, describe it in C++ and run it through this tool. Then you would "just" need a JS source -> bytecode runtime compiler.
Lua doesn't have a standardized bytecode either, just so you know. The fact that PUC-Rio Lua uses bytecode at all is almost an implementation detail, besides the fact that you can dump it and reload it later. But the actual bytecode format and instructions are definitely implementation details and not standardized.
In general, probably, you'd have to replace the part where he writes the LLVM IR directly to say GCC's IR. If you mean no IR at all it doesn't sound like it based on the part about replacing the assembly from LuaJIT.
I just want to point out that LLVM is not a runtime dependency. It is only a build-time dependency if you want to build LJR from source. Once LJR is built, it is stand-alone and does not need LLVM at runtime.
It should be a build time dependency. There's no JIT here, so there's no calling into LLVM's JIT, so I'd hope it's equivalent to using clang to create a native binary that implements the lua language.
Could probably retarget it to emit assembly and commit that for a loose interpretation of building from source.
>More importantly, it is the world’s fastest Lua interpreter to date, outperforming LuaJIT’s interpreter by 28% and the official Lua interpreter by 171% on average on a variety of benchmarks
People who focus on JIT often focus on the JIT and not the interpreter. Which is a shame because if you make the uncommon paths cheaper then you can tune your code for the hot paths a bit more aggressively. You get fewer situations where you are sacrificing Best Case for Average Case performance.
As in, LuaJIT with the JIT disabled, ie with the `-j off` flag? That would be really good to clarify in the article. They start off talking about how they can generate an interpreter and even a JIT, LuaJIT with its JIT turned on is not benchmarked to provide the necessary perspective, the results summary says “28% faster than the LuaJIT interpreter” before the scope of the research has been clarified, and only if you read through do you discover they did not make it generate JITs (yet). It seems everyone in this thread thinks there is now a faster Lua than LuaJIT. The author didn’t claim anything incorrect, but they did lead people to believe it.
That's my read at least. There are several points where they are careful to say LuaJIT interpreter, and I don't think that's an accident. Occams Razor says that's what they meant. The gist of the article is an incremental improvement on interpreter loops, not some counterintuitive amazing breakthrough that nobody has heard before. That's consistent with apples to apples comparisons.
I know it's what they meant, because they were very precise about it, just not very accommodating to people unfamiliar with the terrain. This is the kind of intro I had in mind:
> "The standard architecture of a JIT compiler (like V8, Java HotSpot or LuaJIT) includes both a bytecode interpreter, and a system to recompile a function to native code at runtime. The interpreter is the slow path in a JIT compiler, and is also a general bottleneck in a purely-interpreted VM like CPython. Since we are writing a Lua interpreter and LuaJIT's is the state of the art, the baseline for performance here will be LuaJIT with its JIT turned off."
This means the same thing as the whole "28% faster than LuaJIT's interpreter" business, but nobody comes away from reading that thinking this is faster than LuaJIT as a whole.
LuaJIT actually has a really fast and well-optimized interpreter though, and the article acknowledges this. The reason this interpreter has such great performance isn't directly because they automatically generate the assembly. The majority of the performance gain is because they implemented inline caching, an optimization that LuaJIT doesn't have:
> A lot of LJR’s speedup over LuaJIT interpreter comes from our support of inline caching. We have rewritten the Lua runtime from scratch. In LJR, table objects are not stored as a plain hash table with an array part. Instead, our table implementation employed hidden classes, using a design mostly mirroring the hidden class design in JavaScriptCore.
>
> Hidden class allows efficient inline caching, a technique that drastically speeds up table operations.
One caveat to pay attention to... Ever since LuaJIT and PUC-Lua diverged, PUC lua has made some significant changes to the garbage collector. I wonder if that might affect the comparison vs LuaJIT for memory intensive benchmarks such as binarytrees and tablesort.
As detailed in the article, the garbage collectors for all interpreters tested were disabled for all benchmarks because this interpreter does not yet have garbage collection.
Nice to see Haskell make an appearance in an article about Lua and C/C++:
> For example, at LLVM IR level, it is trivial to make a function use GHC calling convention (a convention with no callee-saved registers)
This refers to the following section of [1]
“cc 10” - GHC convention
This calling convention has been implemented specifically for use by the Glasgow Haskell Compiler (GHC). It passes everything in registers, going to extremes to achieve this by disabling callee save registers. This calling convention should not be used lightly but only for specific situations such as an alternative to the register pinning performance technique often used when implementing functional programming languages. At the moment only X86 supports this convention and it has the following limitations:
On X86-32 only supports up to 4 bit type parameters. No floating-point types are supported.
On X86-64 only supports up to 10 bit type parameters and 6 floating-point parameters.
This calling convention supports tail call optimization but requires both the caller and callee are using it.
Haskell and Pandoc has too much dependency bloat. Just installing Pandoc on Arch requires like 200MB in dependencies, and over hundred haskell specific dependencies.
Well, firstly, I’d note that Haskell on Arch (including Pandoc) is broken, mostly due to the fact that Arch likes to dynamically link everything and Haskell doesn’t (see also https://www.reddit.com/r/haskell/comments/yuwcei). But yes, Haskell packages do often tend to have quite a lot of dependencies. To some extent this is because the base library is very much ‘batteries-excluded’, so dependencies are necessary for things like file management and byte strings and so on, but I do see quite a few dependencies which could be split up (e.g. ‘servant-server’, a big dependency used to create a webserver in exactly one module of pandoc).
I didn't realise LLVM supported such a wide variety of calling conventions.
It would be cool if they supported OpenVMS/x86-64 calling convention–even not on OpenVMS. Why? Well, OpenVMS calling convention has this cool little feature which nobody else seems to have – the parameter count to a function is passed in a register. What this means–people always ask "how can a C variadic function know how many parameters it was passed?" And the usual answer is – you need to add an argument to explicitly pass an argument count (the computation of which can be automated using preprocessor voodoo), or you need to pass some kind of printf-style format argument, or a sentinel value (terminal NULL), or whatever. "Why can't we just have a va_count() which tells us how many arguments we were passed?" "Not possible, per the calling convention, the caller doesn't tell us."
However, for OpenVMS, there actually is such a thing as va_count() – it pulls it from that extra register (the "Argument Information Register"–which also encodes some info on their types, so you can know whether each parameter is passed in an integer register or a floating point one.) Anyway, if LLVM/Clang/etc supported OpenVMS calling convention on other platforms, they could enjoy va_count() too, you'd just have to declare that as the calling convention for your function.
It only uses %al and leaves the upper 56 bits of %rax undefined. OpenVMS adds an arg count in %ah and then uses the rest of the register to hold bitmasks showing whether each register-passed argument was integer or float, and also (optionally) a pointer (stored as offset from call address) to a data structure containing type info for the stack arguments.
Optimising variadic functions seems fairly low value but given they're usually a different calling convention anyway passing an extra integer is probably harmless.
From what I understand, VSI's C compiler for OpenVMS/x86-64 actually gives you a choice of two different variadic calling conventions - something very close to standard SysV ABI x86-64 (which doesn't pass parameter count and type info), and the OpenVMS extension which adds that. So, while I doubt one extra "mov rax, CONSTANT" is going to be noticed (variadic function calls are rarely found on performance-critical code paths), if a function doesn't need va_count(), it can turn that off.
From what I understand, their x86 C and C++ compilers are a patched version of clang/LLVM – they've said they planned to upstream their changes, I don't think it has happened yet, but I hope it does. (Their other compilers – COBOL, Fortran, Pascal, BASIC, BLISS, MACRO – are also using LLVM as backend on x86-64, but with their legacy frontends.)
> More importantly, it is the world’s fastest Lua interpreter to date, outperforming LuaJIT’s interpreter by 28% and the official Lua interpreter by 171% on average on a variety of benchmarks
A stack spill is passing parameters on the stack instead of in registers. It's unavoidable when the number of parameters exceeds the number of registers available for passing parameters (the parameters spill over onto the stack) or if the parameters don't fit into the registers.
> Lua is concise yet supports almost every language feature one can find in dynamic languages
Having yet another terrible package manager? A non-existent ecosystem outside of checks notes game scripting and nginx? Reinvent-Everything where every developer everywhere has to reinvent everything poorly because the language is “concise” and “embeddable” and stuck in the 90s? Breaking changes between versions and interprets worse than the Python2/3 fiasco?
These points are well-known and many would agree if not for the tone of your comment and the missing context, which is:
I have been working on a research project to make writing VMs easier. <snip>. I chose Lua as the experiment target for my idea, mainly because <quote>
This is the most reasonable choice, because experimenting with a big one would drag all the complexity into the project but not the interesting parts. Which language would you suggest instead and why?
None of those are a factor when implementing an interpreter for Lua 5.1. One example given is stackful coroutines, which has nothing to do with package managers, release dates, or the differences between versions.
IOW, Deegen is a proof-of-concept that is being developed on Lua 5.1. Once it is more mature, it will be able to produce other bytecode VMs, too. Lua 5.1 just has enough language features to exercise a lot of capabilities, or in other words, result in Deegen being quite versatile.
Not in the original scope, but truffle has a way to generate interpreter from a java annotated switch case. And it also generates the bytecode format/length, and if you do changes in the interpreter it can change the bytecode format again.
So I think it is related, if not even the same thing. Plus, GraalVM also does JIT out of box. And it has GC.
That said, it's not all rainbows and unicorns, GraalVM has higher memory usage and is only 10-15% faster in production usage. AFAIK, Twitter is using it in production.
The author also worked on the Copy-and-Patch Compilation paper[1], I wonder if they are going to use the same idea for ones of tiers of the JIT idk if it would beat LuaJIT's JIT for code compilation speed but the machine code could be faster.
> With the tail-call approach, each bytecode now gets its own function, and the pathological case for the C/C++ compiler is gone. And as shown by the experience of the Google protobuf developers, the tail-call approach can indeed be used to build very good interpreters. But can it push to the limit of hand-written assembly interpreters? Unfortunately, the answer is still no, at least at its current state.
> The main blockade to the tail-call approach is the callee-saved registers. Since each bytecode function is still a function, it is required to abide to the calling convention, specifically, every callee-saved register must retain its old value at function exit.
This is correct, wasting of callee-saved registers is a shortcoming of the approach I published about protobuf parsing (linked from the first paragraph above). More recently I have been experimenting with a new calling convention that uses no callee-saved registers to work around this, but the results so far are inconclusive. The new calling convention would use all registers for arguments, but allocate registers in the opposite order of normal functions, to reduce the chance of overlap. I have been calling this calling convention "reverse_cc".
I need to spend some time reading this article in more detail, to more fully understand this new work. I would like to know if a new calling convention in Clang would have the same performance benefits, or if Deegen is able to perform optimizations that go beyond this. Inline caching seems like a higher-level technique that operates above the level of individual opcode dispatch, and therefore somewhat orthogonal.
Have you read the Copy-and-patch compilation paper? It seems broadly similar to what you're describing, and Deegen. They use GHC's calling convention for it's snippets which has only caller-saved registers and all arguments passed in registers in order to optimize stitching the snippets together (via JIT templating in it, but with tailcalls in your case would probably also be the same design space).
The copy-and-patch paper is also written by me. Deegen a follow-up work of copy-and-patch, and it will use copy-and-patch as a tool to build its JIT tiers in the future.
> More recently I have been experimenting with a new calling convention that uses no callee-saved registers to work around this, but the results so far are inconclusive. The new calling convention would use all registers for arguments, but allocate registers in the opposite order of normal functions, to reduce the chance of overlap. I have been calling this calling convention "reverse_cc".
As explained in the article, LLVM already has the calling convention you are exactly looking for: the GHC convention (cc 10). You can use it to "pin" registers by passing arguments at the right spot. If you pin your argument in a callee-saved register of the C calling conv, it won't get clobbered after you do a C call.
I tried exposing the "cc 10" and "cc 11" calling conventions to Clang, but was unsuccessful. With "cc 10" I got crashes at runtime I could not explain. With "cc 11" I got a compile-time error:
> fatal error: error in backend: Can't generate HiPE prologue without runtime parameters
If "cc 10" would work from Clang I'd be happy to use that. Though I think reverse_cc could potentially still offer benefits by ordering arguments such that callee-save registers are assigned first. That is helpful when calling fallback functions that take arguments in the normal registers.
Adding calling conventions to clang is fairly straightforward (e.g. https://reviews.llvm.org/D125970) but there's a limited size structure in clang somewhere that makes doing so slightly contentious. Partly because they're shared across all architectures. At some point we'll run out of bits and have to do something invasive and/or slow to free up space.
If you didn't already, I'd recommend compiling llvm/clang in debug or release+assert mode when working on it.
The codebase is quite heavy in debug-only assertions even for relatively trivial things (like missing implementation of some case, some combination of arguments being invalid, ...) which means that it's pretty easy to get into weird crashes down the line with assertions disabled.
I think I remember one called preserve_none. That might have been in a downstream fork though.
The calling convention you want for a coroutine switch is caller saves everything live, callee saves nothing. As that means spilling is done on the live set, to the stack in use before switching. Return after stack switch then restores them.
So if a new convention is proposed that solves both fast stackful coroutines and bytecode interpreter overhead, that seems reasonable to me.
Lua 5.2 introduced a new scoping rule (_ENV) that impacts the ability to implement efficient interpreters, which is why LuaJIT diverged from the main implementation. Insofar as Lua is notoriously the "fastest scripting language", Lua 5.1 is the "fastest Lua". I personally hope that the author eventually targets "LuaJIT flavored Lua", which incorporates some additional features from newer Lua without compromising the performance.
_ENV is the same thing as setfenv/getfenv in Lua 5.1, except its lexical. Unless the use of function environments also make LuaJIT slower (I doubt it as that would implicate _G and a host of other behaviors, all of which LuaJIT is renowned for making work performantly), I think the best way to interpret the original sentiment regarding _ENV is that it would be a PITA to support in a backward compatible manner. There have also been several patches over the years to add _ENV support to LuaJIT, and AFAICT they've all been relatively simple (but not necessarily simple for someone who is firmly of the opinion that Lua should have been frozen at 5.1).
The functional impact of _ENV in Lua 5.2 below the parser level is simply that globals/function environments no longer exist, becoming syntactical sugar for access to a closed-over table. There's a fairly direct (as in, you could write a compiler for it) source-to-source transformation on a 5.2 program (that doesn't use debug or string.dump) where you replace every "global" access with explicit access to _ENV, resulting in a 5.1 with the same semantics as the 5.2 source. This came along with ABI breakage (since PUC then removed all the interfaces that interact with function environments), but at the design level the change only relaxes constraints on interpreter implementation.
5.3 does change up the data model in ways that are incompatible with certain desirable interpreter features (you generally have to choose between 64-bit integers and NaN-boxing), but the incompatibility of 5.2 specifically with efficient interpreter design is at best based on a misunderstanding based on pre-release discussion on the mailing list.
(Real talk though, Lua 5.2 was being floated around the same time period that Mike Pall had committed to LuaJIT 2 as a full rewrite. You can read a bit in between the lines of just the RC dates.)
I’ve been working on an early design of a high-performance dynamic binary translator that cannot JIT, and have reached a very similar conclusion as the author. We have an existing threaded interpreter but it’s a mess of hard-to-maintain assembly for two architectures, and we run into funny issues all the time where the two diverge. Plus, being handwritten by people who are not scheduling experts, there is probably some performance left on the table because of our poor choices and the design making it difficult to write complex-but-more-performant code. Nobody wants to write an efficient hash for TLB lookups in a software MMU using GAS macros.
The core point I’ve identified is that existing compilers are pretty good at converting high level descriptions of operations into architecture-specific code (at least, better than we are given the amount of instructions we have to implement) but absolutely awful at doing register selection or dealing with open control flow that is important for an interpreter. Writing everything in assembly lets you do these two but you miss out on all the nice processor stuff that LLVM has encoded into Tablegen.
Anyways, the current plan is that we’re going to generate LLVM IR for each case and run it through a custom calling convention to take that load off the compiler, similar to what the author did here. There’s a lot more than I’m handwaving over that’s still going to be work, like whether we can automate the process of translating the semantics for each instruction into code, how we plan to pin registers, and how we plan to perform further optimizations on top of what the compiler spits out, but I think this is going to be the new way that people write interpreters. Nobody needs another bespoke macro assembler for every interpreter :)
Great summary, this matches my experience. For straight-line code, modern C compilers can't be beat. But when it comes to register allocation, they constantly make decisions that are real head-scratchers.
One of the biggest problems is when cold paths compromise the efficiency of hot paths. You would hope that __builtin_expect() would help, but from what I can tell __builtin_expect() has no direct impact on register allocation. I wish the compiler would use this information to make sure that cold paths can never compromise the register allocation of the hot paths, but I constantly see register shuffles or spills on hot paths that are only for the benefit of cold paths.
Is there anywhere I can follow your work? I am very interested in keeping track of the state of the art.
Yeah, I did a quick check in LLVM at some point to see what it does (query I relied on: https://github.com/llvm/llvm-project/search?q=getPredictable...) and all the results seemed to be exclusively code motion or deciding how to lower a branch. Similarly cold path outlining seemed to just want to split the function in a fairly simple manner rather than doing anything beyond that. Perhaps I missed something, but I think the current hints are just to help the branch predictor or instruction cache rather than significantly alter codegen.
Unfortunately, I don't have much to share at the moment besides my thoughts; I've done a few small tests but haven't been able to really do a full implementation yet. The primary consumer of this work would be iSH (https://github.com/ish-app/ish), which has a need for a fast interpreter, so you can at least take a look at the current implementation to see what we'd like to replace. The nature of the project means that most of my time has been tied up in things like making sure that keyboard avoidance is set up correctly and that users can customize the background color of their terminal :/
With that said, I'd be happy to chat more if you'd like–feel free to send me an email or whatever. Not sure I can say I'm at the state of the art yet, but perhaps we can get there :)
PGO on a conventional executable with accumulated profiling data is likely to be more performant. JITs also have a problem because they must transmute RW data pages into RO code pages to satisfy NX. PGO enables longer-term analysis that effectively supersedes JIT. JITs are nice in theory, but don't tend to save profiling data to drive optimizations in performance-critical sections that matter.
Might try LuaToCee and then apply PGO iteratively.
Awesome that the result is backed by benchmarks. The writing style is very clear and having actual code snippets is great. Favorited!
My tldr understanding that:
- writing a byte code interpreter in C++ is slow, and a big reason is callee-saved registers / the compiler doesn't optimize well when multiple operations are implemented in the same "giant switch table" function
- but it's annoying to write everything in assembly
- so the author made a compiler that glues together C++ implementations of byte code instructions (compiled to LLVM IR) into an interpreter, avoiding callee-saved registers (and performs other optimizations)
It'd be interesting to see ablation testing for the other optimizations, like fuzing indices into op codes. My bet would be that avoiding having to restore registers dominated of the performance impact--that was the case for the compiler I implemented with friends in college.
113 comments
[ 3.2 ms ] story [ 29.4 ms ] threadMany, many years ago there was even someone trying to write a ruby VM with it[1]. Wow, I'm old.
[1] https://savannah.nongnu.org/projects/carbone
Could probably retarget it to emit assembly and commit that for a loose interpretation of building from source.
Wait what the hell
People who focus on JIT often focus on the JIT and not the interpreter. Which is a shame because if you make the uncommon paths cheaper then you can tune your code for the hot paths a bit more aggressively. You get fewer situations where you are sacrificing Best Case for Average Case performance.
> "The standard architecture of a JIT compiler (like V8, Java HotSpot or LuaJIT) includes both a bytecode interpreter, and a system to recompile a function to native code at runtime. The interpreter is the slow path in a JIT compiler, and is also a general bottleneck in a purely-interpreted VM like CPython. Since we are writing a Lua interpreter and LuaJIT's is the state of the art, the baseline for performance here will be LuaJIT with its JIT turned off."
This means the same thing as the whole "28% faster than LuaJIT's interpreter" business, but nobody comes away from reading that thinking this is faster than LuaJIT as a whole.
> A lot of LJR’s speedup over LuaJIT interpreter comes from our support of inline caching. We have rewritten the Lua runtime from scratch. In LJR, table objects are not stored as a plain hash table with an array part. Instead, our table implementation employed hidden classes, using a design mostly mirroring the hidden class design in JavaScriptCore. > > Hidden class allows efficient inline caching, a technique that drastically speeds up table operations.
> For example, at LLVM IR level, it is trivial to make a function use GHC calling convention (a convention with no callee-saved registers)
This refers to the following section of [1]
“cc 10” - GHC convention This calling convention has been implemented specifically for use by the Glasgow Haskell Compiler (GHC). It passes everything in registers, going to extremes to achieve this by disabling callee save registers. This calling convention should not be used lightly but only for specific situations such as an alternative to the register pinning performance technique often used when implementing functional programming languages. At the moment only X86 supports this convention and it has the following limitations:
On X86-32 only supports up to 4 bit type parameters. No floating-point types are supported. On X86-64 only supports up to 10 bit type parameters and 6 floating-point parameters. This calling convention supports tail call optimization but requires both the caller and callee are using it.
[1] https://llvm.org/docs/LangRef.html#calling-conventions
It would be cool if they supported OpenVMS/x86-64 calling convention–even not on OpenVMS. Why? Well, OpenVMS calling convention has this cool little feature which nobody else seems to have – the parameter count to a function is passed in a register. What this means–people always ask "how can a C variadic function know how many parameters it was passed?" And the usual answer is – you need to add an argument to explicitly pass an argument count (the computation of which can be automated using preprocessor voodoo), or you need to pass some kind of printf-style format argument, or a sentinel value (terminal NULL), or whatever. "Why can't we just have a va_count() which tells us how many arguments we were passed?" "Not possible, per the calling convention, the caller doesn't tell us."
However, for OpenVMS, there actually is such a thing as va_count() – it pulls it from that extra register (the "Argument Information Register"–which also encodes some info on their types, so you can know whether each parameter is passed in an integer register or a floating point one.) Anyway, if LLVM/Clang/etc supported OpenVMS calling convention on other platforms, they could enjoy va_count() too, you'd just have to declare that as the calling convention for your function.
From what I understand, their x86 C and C++ compilers are a patched version of clang/LLVM – they've said they planned to upstream their changes, I don't think it has happened yet, but I hope it does. (Their other compilers – COBOL, Fortran, Pascal, BASIC, BLISS, MACRO – are also using LLVM as backend on x86-64, but with their legacy frontends.)
I think using the name LuaJIT Remake steps on the toes of the existing LuaJIT and I would advise using a more original name.
Anything distinctive would be better. Lua DeeJIT comes to mind, since the generator is called Deegen.
Really huge, if true!
Having yet another terrible package manager? A non-existent ecosystem outside of checks notes game scripting and nginx? Reinvent-Everything where every developer everywhere has to reinvent everything poorly because the language is “concise” and “embeddable” and stuck in the 90s? Breaking changes between versions and interprets worse than the Python2/3 fiasco?
Yessir I do them me those “features”.
I have been working on a research project to make writing VMs easier. <snip>. I chose Lua as the experiment target for my idea, mainly because <quote>
This is the most reasonable choice, because experimenting with a big one would drag all the complexity into the project but not the interesting parts. Which language would you suggest instead and why?
IOW, Deegen is a proof-of-concept that is being developed on Lua 5.1. Once it is more mature, it will be able to produce other bytecode VMs, too. Lua 5.1 just has enough language features to exercise a lot of capabilities, or in other words, result in Deegen being quite versatile.
So I think it is related, if not even the same thing. Plus, GraalVM also does JIT out of box. And it has GC.
That said, it's not all rainbows and unicorns, GraalVM has higher memory usage and is only 10-15% faster in production usage. AFAIK, Twitter is using it in production.
[1] https://arxiv.org/abs/2011.13127
> The main blockade to the tail-call approach is the callee-saved registers. Since each bytecode function is still a function, it is required to abide to the calling convention, specifically, every callee-saved register must retain its old value at function exit.
This is correct, wasting of callee-saved registers is a shortcoming of the approach I published about protobuf parsing (linked from the first paragraph above). More recently I have been experimenting with a new calling convention that uses no callee-saved registers to work around this, but the results so far are inconclusive. The new calling convention would use all registers for arguments, but allocate registers in the opposite order of normal functions, to reduce the chance of overlap. I have been calling this calling convention "reverse_cc".
I need to spend some time reading this article in more detail, to more fully understand this new work. I would like to know if a new calling convention in Clang would have the same performance benefits, or if Deegen is able to perform optimizations that go beyond this. Inline caching seems like a higher-level technique that operates above the level of individual opcode dispatch, and therefore somewhat orthogonal.
As explained in the article, LLVM already has the calling convention you are exactly looking for: the GHC convention (cc 10). You can use it to "pin" registers by passing arguments at the right spot. If you pin your argument in a callee-saved register of the C calling conv, it won't get clobbered after you do a C call.
> fatal error: error in backend: Can't generate HiPE prologue without runtime parameters
If "cc 10" would work from Clang I'd be happy to use that. Though I think reverse_cc could potentially still offer benefits by ordering arguments such that callee-save registers are assigned first. That is helpful when calling fallback functions that take arguments in the normal registers.
But when I tried it on my actual code, the results weren't quite as good as I hoped, due to sub-optimal register allocation.
The calling convention you want for a coroutine switch is caller saves everything live, callee saves nothing. As that means spilling is done on the live set, to the stack in use before switching. Return after stack switch then restores them.
So if a new convention is proposed that solves both fast stackful coroutines and bytecode interpreter overhead, that seems reasonable to me.
Is this the case with Rust?
Edit: see replies
5.3 does change up the data model in ways that are incompatible with certain desirable interpreter features (you generally have to choose between 64-bit integers and NaN-boxing), but the incompatibility of 5.2 specifically with efficient interpreter design is at best based on a misunderstanding based on pre-release discussion on the mailing list.
(Real talk though, Lua 5.2 was being floated around the same time period that Mike Pall had committed to LuaJIT 2 as a full rewrite. You can read a bit in between the lines of just the RC dates.)
The core point I’ve identified is that existing compilers are pretty good at converting high level descriptions of operations into architecture-specific code (at least, better than we are given the amount of instructions we have to implement) but absolutely awful at doing register selection or dealing with open control flow that is important for an interpreter. Writing everything in assembly lets you do these two but you miss out on all the nice processor stuff that LLVM has encoded into Tablegen.
Anyways, the current plan is that we’re going to generate LLVM IR for each case and run it through a custom calling convention to take that load off the compiler, similar to what the author did here. There’s a lot more than I’m handwaving over that’s still going to be work, like whether we can automate the process of translating the semantics for each instruction into code, how we plan to pin registers, and how we plan to perform further optimizations on top of what the compiler spits out, but I think this is going to be the new way that people write interpreters. Nobody needs another bespoke macro assembler for every interpreter :)
One of the biggest problems is when cold paths compromise the efficiency of hot paths. You would hope that __builtin_expect() would help, but from what I can tell __builtin_expect() has no direct impact on register allocation. I wish the compiler would use this information to make sure that cold paths can never compromise the register allocation of the hot paths, but I constantly see register shuffles or spills on hot paths that are only for the benefit of cold paths.
Is there anywhere I can follow your work? I am very interested in keeping track of the state of the art.
Unfortunately, I don't have much to share at the moment besides my thoughts; I've done a few small tests but haven't been able to really do a full implementation yet. The primary consumer of this work would be iSH (https://github.com/ish-app/ish), which has a need for a fast interpreter, so you can at least take a look at the current implementation to see what we'd like to replace. The nature of the project means that most of my time has been tied up in things like making sure that keyboard avoidance is set up correctly and that users can customize the background color of their terminal :/
With that said, I'd be happy to chat more if you'd like–feel free to send me an email or whatever. Not sure I can say I'm at the state of the art yet, but perhaps we can get there :)
Might try LuaToCee and then apply PGO iteratively.
My tldr understanding that:
- writing a byte code interpreter in C++ is slow, and a big reason is callee-saved registers / the compiler doesn't optimize well when multiple operations are implemented in the same "giant switch table" function
- but it's annoying to write everything in assembly
- so the author made a compiler that glues together C++ implementations of byte code instructions (compiled to LLVM IR) into an interpreter, avoiding callee-saved registers (and performs other optimizations)
It'd be interesting to see ablation testing for the other optimizations, like fuzing indices into op codes. My bet would be that avoiding having to restore registers dominated of the performance impact--that was the case for the compiler I implemented with friends in college.