Building the fastest Lua interpreter automatically • Hacker News Board

Re: Building the fastest Lua interpreter automatically

#51

Post by naniwaduni » Wed, Nov 23, 2022, 2:43 AM UTC

scythe wrote: post #37

sigzero wrote: post #33

I 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…

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

Re: Building the fastest Lua interpreter automatically

#52

Post by sanxiyn » Wed, Nov 23, 2022, 2:44 AM UTC

bobm_kite9 wrote: post #27

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

No, it's almost entirely unrelated to GraalVM's approach.

Re: Building the fastest Lua interpreter automatically

#53

Post by cornstalks » Wed, Nov 23, 2022, 2:46 AM UTC

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!

Re: Building the fastest Lua interpreter automatically

#54

Post by haberman » Wed, Nov 23, 2022, 2:48 AM UTC

saagarjha wrote: post #45

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 so…

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.

Re: Building the fastest Lua interpreter automatically

#55

Post by chc4 » Wed, Nov 23, 2022, 3:10 AM UTC

haberman wrote: post #31

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

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

Re: Building the fastest Lua interpreter automatically

#56

Post by sillycross » Wed, Nov 23, 2022, 3:12 AM UTC

haberman wrote: post #31

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

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

Re: Building the fastest Lua interpreter automatically

#57

Post by sillycross » Wed, Nov 23, 2022, 3:13 AM UTC

chc4 wrote: post #55

haberman wrote: post #31

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

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.

Re: Building the fastest Lua interpreter automatically

#58

Post by naniwaduni » Wed, Nov 23, 2022, 3:13 AM UTC

saagarjha wrote: post #40

bessiesboobies wrote: post #28

Do these changes work on Apple M1s too?

This is a design improvement; it’s not specific to any one processor.

It does not, in fact, work, though, since the project (currently) only targets x86_64 Linux.

Re: Building the fastest Lua interpreter automatically

#59

Post by haberman » Wed, Nov 23, 2022, 3:16 AM UTC

sillycross wrote: post #56

haberman wrote: post #31

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

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

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.

Re: Building the fastest Lua interpreter automatically

#60

Post by cmrdporcupine » Wed, Nov 23, 2022, 3:16 AM UTC

ufo wrote: post #7

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

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.