20 ms·

Building the fastest Lua interpreter automatically

571 points by hr0m 4y ago

JZL003 4y ago
wow this is a great article, so readable
abecedarius 4y ago
There's some prior art on DSLs for efficient interpreters, like Anton Ertl's vmgen. https://www.complang.tuwien.ac.at/anton/vmgen/ https://www.complang.tuwien.ac.at/anton/vmgen/
- touisteur 4y ago
  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.
  - abecedarius 4y ago
    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 https://github.com/darius/idel/blob/master/src/opcodes.awk) but unfortunately didn't develop it further.
- riffraff 4y ago
  ah, I remembered this but could not find it again, thanks. Many, 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 https://savannah.nongnu.org/projects/carbone
- UncleEntity 4y ago
  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.
  - abecedarius 4y ago
    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".
    - UncleEntity 4y ago
      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.
gary_0 4y ago
I think there's a typo where the Add() example code goes `lhs.As<tDouble>() && rhs.As<tDouble>()`. I'm assuming that should be a `+`?
- LoganDark 4y ago
  If there was such a typo, it doesn't exist anymore!
  - gary_0 4y ago
    Aha, they fixed it!
Vt71fcAqt7 4y ago
Can this be done for javascript?
- Ericson2314 4y ago
  Yes
- corysama 4y ago
  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.
  - LoganDark 4y ago
    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.
dingdingdang 4y ago
Very very impressive.
ufo 4y ago
Fascinating! I wonder if there's a way to keep this 100% inside the C ecosystem, without having to reach for an LLVM dependency...
- runevault 4y ago
  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.
  - kryptiskt 4y ago
    GCC is written in C++ these days, so something like QBE(https://c9x.me/compile/ https://c9x.me/compile/) would be needed.
- IshKebab 4y ago
  No need to wonder - the article clearly explains why there isn't. That's why they made this tool in the first place!
- saagarjha 4y ago
  Sure, you’d just pick a language that has a flexible optimizing compiler and generate code using that instead.
- cmrdporcupine 4y ago
  Not C, but could probably do it with Rust & Cranelift's IR instead of LLVM's. Not as heavy weight of a dependency as bringing in LLVM.
  - sillycross 4y ago
    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.
ufo 4y ago
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.
- LoganDark 4y ago
  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.
gatane 4y ago
>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 Wait what the hell
- hinkley 4y ago
  Faster than the LuaJIT's interpreter. 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.
  - cormacrelf 4y ago
    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.
    - hinkley 4y ago
      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.
      - cormacrelf 4y ago
        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.
tromp 4y ago
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. [1] https://llvm.org/docs/LangRef.html#calling-conventions https://llvm.org/docs/LangRef.html#calling-conventions
- bradrn 4y ago
  Relatedly, it’s worth noting that there are really good bindings between Lua and Haskell [https://hslua.org/ https://hslua.org/], used in e.g. Pandoc for plugins.
  - encryptluks2 4y ago
    Haskell and Pandoc has too much dependency bloat. Just installing Pandoc on Arch requires like 200MB in dependencies, and over hundred haskell specific dependencies.
    - bradrn 4y ago
      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 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).
kzrdude 4y ago
Super interesting. 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.
- Diggsey 4y ago
  Yeah... Especially as it's not actually a JIT compiler (yet).
presheaf 4y ago
This is very cool.
flyingsky 4y ago
> 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 Really huge, if true!
tomcam 4y ago
What’s a stack spill?
- toast0 4y ago
  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.
  - tomcam 4y ago
    AHHH thanks. Now that I know it's obvious from the name ;)
luablues 4y ago
> 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? Yessir I do them me those “features”.
- wruza 4y ago
  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?
- canadianfella 4y ago
- LoganDark 4y ago
  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.
- nmz 4y ago
  What's wrong with luarocks?
bobm_kite9 4y ago
This sounds a lot like the approach taken by GraalVM. Can someone better versed in this area comment?
- sanxiyn 4y ago
  No, it's almost entirely unrelated to GraalVM's approach.
  - cztomsik 4y ago
    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.
bessiesboobies 4y ago
Do these changes work on Apple M1s too?
- saagarjha 4y ago
  This is a design improvement; it’s not specific to any one processor.
  - naniwaduni 4y ago
    It does not, in fact, work, though, since the project (currently) only targets x86_64 Linux.
    - saagarjha 4y ago
      I interpreted the question as "could these work" rather than "do these work today".
fsfod 4y ago
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. [1] https://arxiv.org/abs/2011.13127 https://arxiv.org/abs/2011.13127
- Terretta 4y ago
  Here's what author says: https://news.ycombinator.com/item?id=33714700 https://news.ycombinator.com/item?id=33714700
haberman 4y ago
> 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.
- svnpenn 4y ago
  https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
  - tekknolagi 4y ago
    For your (and maybe other people's) information, this post is authored by the person you are replying to.
- chc4 4y ago
  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).
MuffinFlavored 4y ago
> The problem with the “big switch-case” approach is that C/C++ compilers simply cannot handle such code well. Is this the case with Rust?
- johncolanduoni 4y ago
  Most likely, as the pathological behavior the article mentions is mostly around register allocation and Rust uses LLVM.
- saagarjha 4y ago
  Yes, it will run into the same register allocation and unstructured control flow issues.
sigzero 4y ago
I wonder why the target was 5.1 since 5.4 has been out for a while now?
- interpol_p 4y ago
  Probably because that's where PUC Lua and LuaJIT diverged, would be interesting to see it on 5.4
- scythe 4y ago
  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. Edit: see replies
  - wahern 4y ago
    _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).
    - sigzero 4y ago
      Interesting. Thanks for answering.
  - naniwaduni 4y ago
    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.)
deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
saagarjha 4y ago
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 :)
- haberman 4y ago
  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.
1letterunixname 4y ago
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.
- saagarjha 4y ago
  This is not a JIT.
jonathanyc 4y ago
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.
cornstalks 4y ago
Could this be used to build a better web assembly interpreter? wasm3 is the fastest Wasm interpreter I’ve found but this approach sounds very intriguing!
- titzer 4y ago
  Wasm3 is already written in the tail-call style. Its IR consists of direct threaded code: a list of function pointers that each load and tail-call the next one. The only improvement on that I could see would be if there are spills because of the calling convention running out of registers. Running out of registers in tail calls is one of the reasons I avoided that in doing Wizard's Wasm interpreter. One constraint there is that interpretation is done in-place (i.e. the original Wasm bytes). I wrote it in hand-rolled asm and it uses 9 architectural registers.
  - saagarjha 4y ago
    Wasm3 leans into the hardware stack I believe.
krick 4y ago
I wonder what makes it so much worse on those 2 specific tasks. Especially k-nukleotide one.
fwsgonzo 4y ago
I have been working on this too, and while I am not at all interested in embedding LLVM, the lack of calling conventions and lack of ability t make a direct jump is unfortunate. My biggest pet peeve though is the inability to push unlikely stuff completely to the back of the program. I mean just put it away where nobody can see it. I also want to align code blocks to 1 bytes. Not 16 bytes. Not a single compiler lets me realign the instruction handlers in a way that compresses them down. I also want to know what BOLT does that improves my interpreter by around 30%.
- sillycross 4y ago
  Clang/LLVM accepts (little-known but documented) flags to let you align code block using a custom alignment, though it only works at file-level. See [1]. However, I'm not sure if doing so is useful or necessary. Interpreter performance is sensitive to code layout (which affects hardware branch predictor accuracy), but I don't think there is a general way to optimize the code layout to make the branch predictor as happy as possible. So if you changed your code alignment and saw a perf change, it's more likely caused by the random perf gain/loss due to code layout change, not because that 1-byte-alignment is better than 16-byte-alignment or vice versa. [1] https://easyperf.net/blog/2018/01/25/Code_alignment_options_in_llvm https://easyperf.net/blog/2018/01/25/Code_alignment_options_...
qikInNdOutReply 4y ago
I work on a game, that mostly uses lua as logic code, saddling on a c/c++ engine. One of the engine developers implemented lua jit years ago and found that for the actual performance, the interpreter/jit was neglibable, the most expensive thing being the actual switch between luacode and c-code, which is with a large API a constant ugly background performance loss. The lua code by itself did not ran long enough to actually profit much from optimizations much. So, back then we did discuss possible solutions, and one idea was to basically notice a upcoming C-Call in bytecode ahead of execution, detect the stability of the arguments ahead of time. A background thread, extracts the values, perform the Call-processing of arguments and return pushes the values onto the stack, finally setting a "valid" bit to unblock the c-call (which by then actually is no longer a call). Both sides never have a complete cache eviction and live happily ever after. Unfortunatly i have a game dev addiction, so nothing ever came of it. But similar minds might have pushed similar ideas.. so asking the hive for this jive. Anyone ever seen something similar in the wild?
- fwsgonzo 4y ago
  I actually measured it. It was around 65-85ns for Lua and 55ns for LuaJIT (on a 7950X). It adds up every time you make a call, despite looking like a small value. Of course, you can multiply it by 2-5x when you put it in production.A decent emulator these days should have < 20ns time to first instruction. The worst emulators are the ones that require you to host them in another thread for the purpose of execution timeout using some kind of timed-wait (eg. futex op), adding a massive 10-20 micros overhead just to communicate tasks. Ultimately the script in a game engine either makes a bunch of API calls, so we want the "system call overhead" to be that of an opaque function call (4ns), and sometimes you share memory in order to read out properties and put abstractions on them (probably not relevant to Lua). So, it's important to get going fast, and to be able to make hundreds of engine API calls without unnecessary costs. Benchmarks: https://gist.github.com/fwsGonzo/2f4518b66b147ee657d64496811f9edb https://gist.github.com/fwsGonzo/2f4518b66b147ee657d64496811...
- nl 4y ago
  In CPUs they call this speculative execution. It's a good idea if you can detect side effect free code (and don't have the sandboxing issues that caused problems on CPUs).
mraleph 4y ago
It would be interesting to see 1-1 comparison with LuaJIT interpreter _without corresponding runtime changes_. That would given a meaningful baseline for how much you potentially loose/gain using this approach. Current measurement presents comparison of two wildly different implementation strategies: LuaJIT Remake uses IC and hidden classes while LuaJIT proper does not. It's a well known fact that ICs+hidden classes can lead to major performance improvements. That insight originated in Smalltalk world and was brought to dynamic language mainstream by V8† - but unfortunately it muddles the comparison here. † V8 was open sourced on September 2, 2008... Coincidentally (though probably not :)) JSC landed their first IC prototype on September 1, 2008.
- sillycross 4y ago
  I agree with your point, but I want to point out that Deegen also provided APIs to hide all the details of inline caching. The bytecode only specifies the body lambda and the effect lambdas, and Deegen lowers it to an efficient implementation automatically, including exotic optimizations that fuses the cached IC effect into the opcode so one indirect branch can be avoided. If LuaJIT interpreter were to employ IC, it would have to undergo a major rewrite (due to its assembly nature) to have the equally efficient code as LJR (that we generate automatically). This is one advantage of our meta-compiler approach. Finally, although no experiment is made, my subjective opinion is already in the article: > LuaJIT’s hand-written assembly interpreter is highly optimized already. Our interpreter generated by Deegen is also highly optimized, and in many cases, slightly better-optimized than LuaJIT. However, the gain from those low-level optimizations are simply not enough to beat LuaJIT by a significant margin, especially on a modern CPU with very good instruction-level parallelism, where having a few more instructions, a few longer instructions, or even a few more L1-hitting loads have negligible impact on performance. The support of inline caching is one of the most important high-level optimizations we employed that contributes to our performance advantage over LuaJIT. That is, if you compare the assembly between LJR and LuaJIT interpreter, I believe LJR's assembly is slightly better (though I would anticipate only marginal performance difference). But that's also because we employed a different boxing scheme (again...). If you force LJR to use LuaJIT's boxing scheme, I guess the assembly code would also be similar since LJR's hand-written assembly is already optimal or at least very close to optimal.
arc-in-space 4y ago
sillycross, please consider adding a rss feed to your blog. People do still use those.
fasteo 4y ago
It is my understanding that benchmarks are run against LuaJIT interpreter (-j off), so here are some JIT numbers for reference, using the array3d.lua benchmark [1] time luajit -j off array3d.lua real 0m1,968s user 0m1,915s sys 0m0,052s time luajit -j on array3d.lua real 0m0,128s user 0m0,068s sys 0m0,060s [1] https://github.com/luajit-remake/luajit-remake/blob/master/luabench/array3d.lua https://github.com/luajit-remake/luajit-remake/blob/master/l...
scott55 4y ago
farzher 4y ago
Faster than the LuaJIT's interpreter... with the JIT disabled. would've been nice to make that more clear.
chubot 4y ago
This seems like an awesome way of writing faster interpreters – i.e. not in assembly, but in C++ snippets you stitch together with a tool. I did peek at the deegen tool a bit, and it seems quite large? https://github.com/luajit-remake/luajit-remake/tree/master/deegen https://github.com/luajit-remake/luajit-remake/tree/master/d... I would be interested in an overview of all the analysis it has to do, which as I understand is basically “automated Mike Pall” FWIW I think this is the hand-written equivalent with LuaJIT’s dynasm tool: https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x64.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x64.dasc (just under 5000 lines) Also there are several of these files with no apparent sharing, as you would get with deegen: https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x86.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x86.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_ppc.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_ppc.dasc

571 points by hr0m 4y ago

wow this is a great article, so readable

There's some prior art on DSLs for efficient interpreters, like Anton Ertl's vmgen. https://www.complang.tuwien.ac.at/anton/vmgen/ https://www.complang.tuwien.ac.at/anton/vmgen/

touisteur 4y ago
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.
- abecedarius 4y ago
  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 https://github.com/darius/idel/blob/master/src/opcodes.awk) but unfortunately didn't develop it further.
riffraff 4y ago
ah, I remembered this but could not find it again, thanks. Many, 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 https://savannah.nongnu.org/projects/carbone
UncleEntity 4y ago
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.
- abecedarius 4y ago
  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".
  - UncleEntity 4y ago
    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.

gary_0 4y ago

I think there's a typo where the Add() example code goes `lhs.As<tDouble>() && rhs.As<tDouble>()`. I'm assuming that should be a `+`?

LoganDark 4y ago
If there was such a typo, it doesn't exist anymore!
- gary_0 4y ago
  Aha, they fixed it!

Vt71fcAqt7 4y ago

Can this be done for javascript?

Ericson2314 4y ago
Yes
corysama 4y ago
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.
- LoganDark 4y ago
  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.

dingdingdang 4y ago

Very very impressive.

ufo 4y ago

Fascinating! I wonder if there's a way to keep this 100% inside the C ecosystem, without having to reach for an LLVM dependency...

runevault 4y ago
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.
- kryptiskt 4y ago
  GCC is written in C++ these days, so something like QBE(https://c9x.me/compile/ https://c9x.me/compile/) would be needed.
IshKebab 4y ago
No need to wonder - the article clearly explains why there isn't. That's why they made this tool in the first place!
saagarjha 4y ago
Sure, you’d just pick a language that has a flexible optimizing compiler and generate code using that instead.
cmrdporcupine 4y ago
Not C, but could probably do it with Rust & Cranelift's IR instead of LLVM's. Not as heavy weight of a dependency as bringing in LLVM.
- sillycross 4y ago
  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.

ufo 4y ago

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.

LoganDark 4y ago
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.

gatane 4y ago

>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 Wait what the hell

hinkley 4y ago
Faster than the LuaJIT's interpreter. 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.
- cormacrelf 4y ago
  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.
  - hinkley 4y ago
    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.
    - cormacrelf 4y ago
      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.

tromp 4y ago

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. [1] https://llvm.org/docs/LangRef.html#calling-conventions https://llvm.org/docs/LangRef.html#calling-conventions

bradrn 4y ago
Relatedly, it’s worth noting that there are really good bindings between Lua and Haskell [https://hslua.org/ https://hslua.org/], used in e.g. Pandoc for plugins.
- encryptluks2 4y ago
  Haskell and Pandoc has too much dependency bloat. Just installing Pandoc on Arch requires like 200MB in dependencies, and over hundred haskell specific dependencies.
  - bradrn 4y ago
    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 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).

kzrdude 4y ago

Super interesting. 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.

Diggsey 4y ago
Yeah... Especially as it's not actually a JIT compiler (yet).

presheaf 4y ago

This is very cool.

flyingsky 4y ago

> 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 Really huge, if true!

tomcam 4y ago

What’s a stack spill?

toast0 4y ago
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.
- tomcam 4y ago
  AHHH thanks. Now that I know it's obvious from the name ;)

luablues 4y ago

> 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? Yessir I do them me those “features”.

wruza 4y ago
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?
canadianfella 4y ago
LoganDark 4y ago
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.
nmz 4y ago
What's wrong with luarocks?

bobm_kite9 4y ago

This sounds a lot like the approach taken by GraalVM. Can someone better versed in this area comment?

sanxiyn 4y ago
No, it's almost entirely unrelated to GraalVM's approach.
- cztomsik 4y ago
  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.

bessiesboobies 4y ago

Do these changes work on Apple M1s too?

saagarjha 4y ago
This is a design improvement; it’s not specific to any one processor.
- naniwaduni 4y ago
  It does not, in fact, work, though, since the project (currently) only targets x86_64 Linux.
  - saagarjha 4y ago
    I interpreted the question as "could these work" rather than "do these work today".

fsfod 4y ago

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. [1] https://arxiv.org/abs/2011.13127 https://arxiv.org/abs/2011.13127

Terretta 4y ago
Here's what author says: https://news.ycombinator.com/item?id=33714700 https://news.ycombinator.com/item?id=33714700

haberman 4y ago

> 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.

svnpenn 4y ago
https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
- tekknolagi 4y ago
  For your (and maybe other people's) information, this post is authored by the person you are replying to.
chc4 4y ago
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).

MuffinFlavored 4y ago

> The problem with the “big switch-case” approach is that C/C++ compilers simply cannot handle such code well. Is this the case with Rust?

johncolanduoni 4y ago
Most likely, as the pathological behavior the article mentions is mostly around register allocation and Rust uses LLVM.
saagarjha 4y ago
Yes, it will run into the same register allocation and unstructured control flow issues.

sigzero 4y ago

I wonder why the target was 5.1 since 5.4 has been out for a while now?

interpol_p 4y ago
Probably because that's where PUC Lua and LuaJIT diverged, would be interesting to see it on 5.4
scythe 4y ago
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. Edit: see replies
- wahern 4y ago
  _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).
  - sigzero 4y ago
    Interesting. Thanks for answering.
- naniwaduni 4y ago
  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.)

deleted 4y ago

[deleted]

deleted 4y ago

[deleted]

saagarjha 4y ago

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 :)

haberman 4y ago
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.

1letterunixname 4y ago

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.

saagarjha 4y ago
This is not a JIT.

jonathanyc 4y ago

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.

cornstalks 4y ago

Could this be used to build a better web assembly interpreter? wasm3 is the fastest Wasm interpreter I’ve found but this approach sounds very intriguing!

titzer 4y ago
Wasm3 is already written in the tail-call style. Its IR consists of direct threaded code: a list of function pointers that each load and tail-call the next one. The only improvement on that I could see would be if there are spills because of the calling convention running out of registers. Running out of registers in tail calls is one of the reasons I avoided that in doing Wizard's Wasm interpreter. One constraint there is that interpretation is done in-place (i.e. the original Wasm bytes). I wrote it in hand-rolled asm and it uses 9 architectural registers.
- saagarjha 4y ago
  Wasm3 leans into the hardware stack I believe.

krick 4y ago

I wonder what makes it so much worse on those 2 specific tasks. Especially k-nukleotide one.

fwsgonzo 4y ago

I have been working on this too, and while I am not at all interested in embedding LLVM, the lack of calling conventions and lack of ability t make a direct jump is unfortunate. My biggest pet peeve though is the inability to push unlikely stuff completely to the back of the program. I mean just put it away where nobody can see it. I also want to align code blocks to 1 bytes. Not 16 bytes. Not a single compiler lets me realign the instruction handlers in a way that compresses them down. I also want to know what BOLT does that improves my interpreter by around 30%.

sillycross 4y ago
Clang/LLVM accepts (little-known but documented) flags to let you align code block using a custom alignment, though it only works at file-level. See [1]. However, I'm not sure if doing so is useful or necessary. Interpreter performance is sensitive to code layout (which affects hardware branch predictor accuracy), but I don't think there is a general way to optimize the code layout to make the branch predictor as happy as possible. So if you changed your code alignment and saw a perf change, it's more likely caused by the random perf gain/loss due to code layout change, not because that 1-byte-alignment is better than 16-byte-alignment or vice versa. [1] https://easyperf.net/blog/2018/01/25/Code_alignment_options_in_llvm https://easyperf.net/blog/2018/01/25/Code_alignment_options_...

qikInNdOutReply 4y ago

I work on a game, that mostly uses lua as logic code, saddling on a c/c++ engine. One of the engine developers implemented lua jit years ago and found that for the actual performance, the interpreter/jit was neglibable, the most expensive thing being the actual switch between luacode and c-code, which is with a large API a constant ugly background performance loss. The lua code by itself did not ran long enough to actually profit much from optimizations much. So, back then we did discuss possible solutions, and one idea was to basically notice a upcoming C-Call in bytecode ahead of execution, detect the stability of the arguments ahead of time. A background thread, extracts the values, perform the Call-processing of arguments and return pushes the values onto the stack, finally setting a "valid" bit to unblock the c-call (which by then actually is no longer a call). Both sides never have a complete cache eviction and live happily ever after. Unfortunatly i have a game dev addiction, so nothing ever came of it. But similar minds might have pushed similar ideas.. so asking the hive for this jive. Anyone ever seen something similar in the wild?

fwsgonzo 4y ago
I actually measured it. It was around 65-85ns for Lua and 55ns for LuaJIT (on a 7950X). It adds up every time you make a call, despite looking like a small value. Of course, you can multiply it by 2-5x when you put it in production.A decent emulator these days should have < 20ns time to first instruction. The worst emulators are the ones that require you to host them in another thread for the purpose of execution timeout using some kind of timed-wait (eg. futex op), adding a massive 10-20 micros overhead just to communicate tasks. Ultimately the script in a game engine either makes a bunch of API calls, so we want the "system call overhead" to be that of an opaque function call (4ns), and sometimes you share memory in order to read out properties and put abstractions on them (probably not relevant to Lua). So, it's important to get going fast, and to be able to make hundreds of engine API calls without unnecessary costs. Benchmarks: https://gist.github.com/fwsGonzo/2f4518b66b147ee657d64496811f9edb https://gist.github.com/fwsGonzo/2f4518b66b147ee657d64496811...
nl 4y ago
In CPUs they call this speculative execution. It's a good idea if you can detect side effect free code (and don't have the sandboxing issues that caused problems on CPUs).

mraleph 4y ago

It would be interesting to see 1-1 comparison with LuaJIT interpreter _without corresponding runtime changes_. That would given a meaningful baseline for how much you potentially loose/gain using this approach. Current measurement presents comparison of two wildly different implementation strategies: LuaJIT Remake uses IC and hidden classes while LuaJIT proper does not. It's a well known fact that ICs+hidden classes can lead to major performance improvements. That insight originated in Smalltalk world and was brought to dynamic language mainstream by V8† - but unfortunately it muddles the comparison here. † V8 was open sourced on September 2, 2008... Coincidentally (though probably not :)) JSC landed their first IC prototype on September 1, 2008.

sillycross 4y ago
I agree with your point, but I want to point out that Deegen also provided APIs to hide all the details of inline caching. The bytecode only specifies the body lambda and the effect lambdas, and Deegen lowers it to an efficient implementation automatically, including exotic optimizations that fuses the cached IC effect into the opcode so one indirect branch can be avoided. If LuaJIT interpreter were to employ IC, it would have to undergo a major rewrite (due to its assembly nature) to have the equally efficient code as LJR (that we generate automatically). This is one advantage of our meta-compiler approach. Finally, although no experiment is made, my subjective opinion is already in the article: > LuaJIT’s hand-written assembly interpreter is highly optimized already. Our interpreter generated by Deegen is also highly optimized, and in many cases, slightly better-optimized than LuaJIT. However, the gain from those low-level optimizations are simply not enough to beat LuaJIT by a significant margin, especially on a modern CPU with very good instruction-level parallelism, where having a few more instructions, a few longer instructions, or even a few more L1-hitting loads have negligible impact on performance. The support of inline caching is one of the most important high-level optimizations we employed that contributes to our performance advantage over LuaJIT. That is, if you compare the assembly between LJR and LuaJIT interpreter, I believe LJR's assembly is slightly better (though I would anticipate only marginal performance difference). But that's also because we employed a different boxing scheme (again...). If you force LJR to use LuaJIT's boxing scheme, I guess the assembly code would also be similar since LJR's hand-written assembly is already optimal or at least very close to optimal.

arc-in-space 4y ago

sillycross, please consider adding a rss feed to your blog. People do still use those.

fasteo 4y ago

It is my understanding that benchmarks are run against LuaJIT interpreter (-j off), so here are some JIT numbers for reference, using the array3d.lua benchmark [1] time luajit -j off array3d.lua real 0m1,968s user 0m1,915s sys 0m0,052s time luajit -j on array3d.lua real 0m0,128s user 0m0,068s sys 0m0,060s [1] https://github.com/luajit-remake/luajit-remake/blob/master/luabench/array3d.lua https://github.com/luajit-remake/luajit-remake/blob/master/l...

scott55 4y ago

farzher 4y ago

Faster than the LuaJIT's interpreter... with the JIT disabled. would've been nice to make that more clear.

chubot 4y ago

This seems like an awesome way of writing faster interpreters – i.e. not in assembly, but in C++ snippets you stitch together with a tool. I did peek at the deegen tool a bit, and it seems quite large? https://github.com/luajit-remake/luajit-remake/tree/master/deegen https://github.com/luajit-remake/luajit-remake/tree/master/d... I would be interested in an overview of all the analysis it has to do, which as I understand is basically “automated Mike Pall” FWIW I think this is the hand-written equivalent with LuaJIT’s dynasm tool: https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x64.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x64.dasc (just under 5000 lines) Also there are several of these files with no apparent sharing, as you would get with deegen: https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x86.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_x86.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_ppc.dasc https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/vm_ppc.dasc