Fascinating! I wonder if there's a way to keep this 100% inside the C ecosystem, without having to reach for an LLVM dependency...
Sure, you’d just pick a language that has a flexible optimizing compiler and generate code using that instead.
Building the fastest Lua interpreter automatically
41–50 of 114 posts
Re: Building the fastest Lua interpreter automatically
#42Nice 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…
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 w…
Interestingly System-V passes the number of floating point registers used for a variadic function in rax.
Re: Building the fastest Lua interpreter automatically
#43[deleted]
Re: Building the fastest Lua interpreter automatically
#44I wonder why the target was 5.1 since 5.4 has been out for a while now?
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…
_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).
Re: Building the fastest Lua interpreter automatically
#45I’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 :)
Re: Building the fastest Lua interpreter automatically
#46PGO 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.
Re: Building the fastest Lua interpreter automatically
#47Nice 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…
Relatedly, it’s worth noting that there are really good bindings between Lua and Haskell [ https://hslua.org/ ], used in e.g. Pandoc for plugins.
Haskell and Pandoc has too much dependency bloat. Just installing Pandoc on Arch requires like 200MB in dependencies, and over hundred haskell specific dependencies.
Re: Building the fastest Lua interpreter automatically
#48> 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…
Re: Building the fastest Lua interpreter automatically
#49Earlier quoted context omitted.
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…
_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…
Interesting. Thanks for answering.
Re: Building the fastest Lua interpreter automatically
#50Awesome 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.