Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building the fastest Lua interpreter automatically

sillycross.github.io

Post reply on HN
Print view View original

71–80 of 114 posts

Re: Building the fastest Lua interpreter automatically

#71

Post by LoganDark »

corysama wrote: post #19
Vt71fcAqt7 wrote: post #5

Can this be done for javascript?

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.

Re: Building the fastest Lua interpreter automatically

#72

Post by LoganDark »

luablues wrote: post #24

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

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.

Re: Building the fastest Lua interpreter automatically

#73

Post by saagarjha »

naniwaduni wrote: post #58
saagarjha wrote: post #40

Earlier quoted context omitted.

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.

I interpreted the question as "could these work" rather than "do these work today".

Re: Building the fastest Lua interpreter automatically

#74

Post by saagarjha »

1letterunixname wrote: post #46

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…

This is not a JIT.

Re: Building the fastest Lua interpreter automatically

#75

Post by saagarjha »

titzer wrote: post #67
cornstalks wrote: post #53

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!

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

Wasm3 leans into the hardware stack I believe.

Re: Building the fastest Lua interpreter automatically

#76

Post by saagarjha »

haberman wrote: post #54
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…

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

Re: Building the fastest Lua interpreter automatically

#78

Post by fwsgonzo »

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

Re: Building the fastest Lua interpreter automatically

#79

Post by tekknolagi »

svnpenn wrote: post #48
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…

https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

For your (and maybe other people's) information, this post is authored by the person you are replying to.

Re: Building the fastest Lua interpreter automatically

#80

Post by sillycross »

fwsgonzo wrote: post #78

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…

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

Post reply on HN