Haoran Xu

It doesn't make sense to me that an embedded VM/interpreter could ever outperform direct code You're adding a layer of abstraction and indirection, so how is it possible that a more indirect solution can have better performance? This seems counterintuitive, so I googled it. Apparently, it boils down to instruction cache efficiency and branch prediction, largely. The best content I could find was this post, as well as some scattered comments from Mike Pall of LuaJIT fame: https://sillycross.github.io/2022/11/22/2022-11-22/ Interestingly, this is also discussed on a similar blogpost about using Clang's recent-ish [[musttail]] tailcall attribute to improve C++ JSON parsing performance: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreter…

> we might conclude that the speed-up of a manual assembler implementation compared to a generated interpreter is about 30%[, t]herefore it's no longer worth the effort to implement an interpreter in assembler You got that backwards. The paper reports Deegen’s generated interpreter is faster than LuaJIT’s handwritten one by 30%. That’s actually pretty impressive—and pretty impressively straightforwardly achieved[1], TL;DR: instruction dispatch via tail calls avoids the pessimized register allocation that you get for a huge monolithic interpreter loop. [1] https://sillycross.github.io/2022/11/22/2022-11-22/

I think this is unlikely for SQLite (other comments cover why it probably wouldn't happen even if it were likely to benefit), but I happened to have the copy and patch paper open in a tab, so I'll take the opportunity to share it here. https://sillycross.github.io/assets/copy-and-patch.pdf It has great potential for many applications, if not this particular one.

I think it's really cool that Haoran Xu and Fredrik Kjolstad's copy-and-patch technique[0] is catching on, I remember discovering it through Xu's blog posts about his LuaJIT remake project[1][2], where he intends to apply these techniques to Lua (and I probably found those through a post here). I was just blown away by how they "recycled" all these battle-tested techniques and technologies, and used it to synthesize something novel. I'm not a compiler writer but it felt really clever to me. I highly recommend the blog posts if you're into learning how languages are implemented, by the way. They're incredible deep dives, but he uses the details-element to keep the metaphorical descents into Mariana Trench optional so it doesn't get too overwhelming. I even had the privilege of congratulating him the 1000th star of the GH repo[3], where he reassured me and others that he's still working on it despite the long pause after the last blog post, and that this mainly has to do with behind-the-scenes rewrites that make no sense to publish in part. [0] https://arxiv.org/abs/2011.13127 [1] https://sillycross.github.io/2022/11/22/2022-11-22/ [2] https://sillycross.github.io/2023/05/12/2023-05-12/ [3] https://github.com/luajit-remake/luajit-remake/issues/11

It's crazy that this post seems to have stumbled across an equivalent to the Copy-and-Patch technique[0] used to create a Lua interpreter faster than LuaJit[1] [0]: https://sillycross.github.io/2023/05/12/2023-05-12/ [1]: https://sillycross.github.io/2022/11/22/2022-11-22/ The major difference is that LuaJIT Remake's Copy-and-Patch requires "manually" copying blocks of assembly code and patching values, while this post relies on the Go compiler's closures to create copies of the functions with runtime-known values. I think there's fascinating processing being made in this area—I think in the future this technique (in some form) will be the go-to way to create new interpreted languages, and AST interpreters, switch-based bytecode VMs, and JIT compilation will be things of the past.

> We implement LuaJIT Remake (LJR), a standard-compliant Lua 5.1 VM, using Deegen. Across 44 benchmarks, LJR's interpreter is on average 179% faster than the official PUC Lua interpreter, and 31% faster than LuaJIT's interpreter. LJR's baseline JIT has negligible startup delay, and its execution performance is on average 360% faster than PUC Lua and only 33% slower (but faster on 13/44 benchmarks) than LuaJIT's optimizing JIT. presentation by the author Deegen: A LLVM-based Compiler-Compiler for Dynamic Languages https://www.youtube.com/watch?v=5cAUX9QPj4Y Slides https://aha.stanford.edu/sites/g/files/sbiybj20066/files/media/file/ah… Ongoing work documented here https://sillycross.github.io/ and some comments here https://lobste.rs/s/ftsowh/building_baseline_jit_for_lua https://github.com/luajit-remake/luajit-remake

The second part from 2023 (https://sillycross.github.io/2023/05/12/2023-05-12/) is even more interesting, but the last commit of https://github.com/luajit-remake/luajit-remake was eight months ago, so the development seems to unfortunately have stalled. Does anyone have information about the reason?

The remaining issue with tail calls used to switch context, is that you’re using functions that must use a calling convention. And unfortunately they waste registers to restore state on function exit. See the luajit remake blog for an exhaustive analysis and alternative using an intermediate compiler https://sillycross.github.io/2022/11/22/2022-11-22/

Blog post about the approach here: https://sillycross.github.io/2023/05/12/2023-05-12/

> I just meant that even being aware this is a naive copy-and-patch JIT, my first impression was that the code was slightly worse than I expected. > "there’s only so much one can do without touching the data model" You probably want to look at the other link in that PR, which demonstrated how well copy-and-patch can do for another dynamic language (Lua): [1] Of course, whether or not CPython could eventually make it to that point (or even further) is a different story: they are under a way tighter constraint than just developing something for academia. But copy-and-patch can do a lot even for dynamic languages :) [1] https://sillycross.github.io/2023/05/12/2023-05-12/

Someone needs to learn to use copy / paste properly LOL! Take a look at the URL: https://sillycross.github.io/2021/08/23/https://sillycross.github.io/2… Here's the actual link: https://sillycross.github.io/2021/08/23/2021-08-23/