mikemike · HackerTrans

mikemike

no profile record

Submissions

A Walk with LuaJIT

polarsignals.com

20 pointsby mikemike2 ปีที่แล้ว2 comments

comments

เดือนที่แล้วdiscuss

I'm not sure one can infer anything from a single failed Mozilla project.

'Real-world' JavaScript is a challenge for any compiler, no matter the underlying technology.

The technical debt in SpiderMonkey (at that time, anyway) was eye-watering. Grafting anything on top of that was hard. They haven't even gotten to the point of implementing the crucial pieces of a trace compiler before the project folded.

Trace compilers make nice textbook exercises. Getting them into production is a different matter: region selection, side-exit handling, trace graph evolution, deep VM integration, code generation adapted to all of this … far from trivial, but doable.

Neither is it trivial to create a production-quality method-at-a-time JIT compiler and VM for a dynamic language.

Ceterum censeo: The fundamental papers on trace compilation are from Fisher (1981) and the teams around Multiflow (1990) and Dynamo (1999). Franz, Gal, et al can be credited for later re-popularizing the idea, but they haven't added anything of note.

เดือนที่แล้วdiscuss

Trace compilation is NOT a dead end.

LuaJIT works just fine. On big programs. On hundreds of millions of servers and devices.

I find it deeply saddening that even scholars keep repeating this trope. Ignorance is bliss.

3 เดือนที่ผ่านมาdiscuss

To illustrate this, here's the contorted Lua code from https://news.ycombinator.com/item?id=11327201

    local t = setmetatable({}, {
      __index = pcall, __newindex = rawset,
      __call = function(t, i) t[i] = 42 end,
    })
    for i=1,100 do assert(t[i] == true and rawget(t, i) == 42) end

Arguably this exercises only the slow paths of the VM.

A more nuanced take is that Lua has many happy fast paths, whereas Python has some unfortunate semantic baggage that complicates those. Another key issue is the over-reliance on C modules with bindings that expose way too many internals.

4 เดือนที่ผ่านมาdiscuss

As the open source author in question, I'd politely ask everyone to not draw overly-generic conclusions from an ancient discussion in some third-party forum, which links to a (now) resolved bug report.

Open source is not a one-way street. By publicly disparaging open source projects, you're actually harming the ecosystem you rely on.

2 ปีที่แล้วdiscuss

A good read if you want to learn (more than you ever wanted) about stack frame unwinding in conjunction with a JIT compiler.

The only correction I have: LuaJIT _does_ have 64 bit integers, e.g. 0x0123456789abcdefLL.

3 ปีที่แล้วdiscuss

This is conjecture. OTOH I measured while I designed the LuaJIT IR.

1. An array index is just as suitable as a pointer for dereferencing. 2. What matters is how many dereferences are needed and their locality. 3. Data structure density is important to get high cache utilization.

References show a lot of locality: 40% of all IR operands reference the previous node. 70% reference the previous 10 nodes. A linear IR is the best cache-optimized data structure for this.

That said, dereferencing of an operand happens less often than one might think. Most of the time, one really needs the operand index itself, e.g. for hashes or comparisons. Again, indexes have many advantages over pointers here.

What paid off the most was to use a fixed size IR instruction format (only 64 bit!) with 2 operands and 16 bit indexes. The restriction to 2 operands is actually beneficial, since it helps with commoning and makes you think about IR design. The 16 bit index range is not a limitation in practice (split IR chunks, if you need to). The high orthogonality of the IR avoids many iterations and unpredictable branches in the compiler itself.

The 16 bit indexes also enable the use of tagged references in the compiler code (not in the IR). The tag caches node properties: type, flags, constness. This avoids even more dereferences. LuaJIT uses this in the front pipeline for fast type checks and on-the-fly folding.

4 ปีที่แล้วdiscuss

I had already changed the title after your reply. The objection is about the naming, which implies an invention claim without further explanation. It's not about the code.

4 ปีที่แล้วdiscuss

You may want to clarify that in the GitHub repo, too. See my issue there.

If you want to go the didactic route, then consider documenting the improvements over the naive implementation: register hinting, register priorities (PHI), two-headed register picking, fixed register picking, optimized register picking for 2-operand instructions (x86/x64), register pair picking, ABI calling-conventions, weak allocations, cost heuristics, eviction heuristics, lazy/eager spill/restore, rematerialization, register shuffling (PHI) with cycle breaking, register renaming, etc. That's all in ~2000 lines of lj_asm.c.

4 ปีที่แล้วdiscuss

Uh? This *is* the LuaJIT register allocator. Period.

Code published 2009. Description published here: https://lua-users.org/lists/lua-l/2009-11/msg00089.html (ignore the TLS cert error).

Coming up with a silly markting name, writing a naive implementation and then claiming it's their invention is impertinent. Especially since they mention LuaJIT itself in the text ...

4 ปีที่แล้วdiscuss

That's what I'm wondering, too, right now.

It's trivial to DoS-hang redis with the script feature (and SCRIPT KILL won't help).

And I found at least 3 DoS-crash, because it hasn't backported fixes to its copy of Lua 5.1.5 (but Debian's liblua 5.1 might -- I haven't checked).

And that's without even exploring the really problematic builtins it still has available.

Maybe they should instead clarify their security guarantee for redis scripting (e.g. "none").

4 ปีที่แล้วdiscuss

Yes, of course it's vulnerable, verified with Docker debian:sid. That was my first reaction when I read this, but I wanted to verify it first. You beat me with this post.

Since you've already let the cat out of the hat (which is not ideal), please file the bugs at Debian and Ubuntu.

Test command:

    redis-cli eval 'return select(2, loadstring("\027")):match("binary") and "VULNERABLE" or "OK"' 0

While we're at it, redis has ignored the advice at: http://lua-users.org/wiki/SandBoxes Almost all of the critical functions (loadstring, load, getmetatable, getfenv, ...) are present and unprotected in the redis 'SandBox' (which isn't).

Which means, disable scripting or shut down your redis instances NOW, which do not run with the same privileges as any client which has access to this. Scripting can be disabled by renaming the EVAL and EVALSHA commands to unguessable names.

5 ปีที่แล้วdiscuss

One year ago I hardened LuaJIT's VM against these kind of attacks. Since then, there has been a constant influx of complaints and issues filed. All bitterly complaining their code, which mistakenly assumed a fixed hash table iteration order, is now broken.

Even when told that the Lua manual clearly states the undefined order since 20 years, they do not cease to complain. They do not realize this change helped them to discover a serious bug in their code (the order could differ even before that change). Sigh.

You can now have a guess, what one of the lesser enlightened forks of LuaJIT did ...

9 ปีที่แล้วdiscuss

Actually, LuaJIT 1.x is just that: a translator from a register-based bytecode to machine code using templates (small assembler snippets) with fixed register assignment. There's only a little bit more magic to that, like template variants depending on the inferred type etc.

You can compare the performance of LuaJIT 1.x and 2.0 yourself on the benchmark page (for x86). The LuaJIT 1.x JIT-compiled code is only slightly faster than the heavily tuned LuaJIT 2.x VM plus the 2.x interpreter written in assembly language by hand. Sometimes the 2.x interpreter even beats the 1.x compiler.

A lot of this is due to the better design of the 2.x VM (object layout, stack layout, calling conventions, builtins etc.). But from the perspective of the CPU, a heavily optimized interpreter does not look that different from simplistic, template-generated code. The interpreter dispatch overhead can be moved to independent dependency-chains by the CPU, if you're doing this right.

Of course, the LuaJIT 2.x JIT compiler handily beats both the 2.x interpreter and the 1.x compiler.

10 ปีที่แล้วdiscuss

Notable recent use of DynASM: Zend is using it to write a JIT compiler for PHP 8.0. http://externals.io/thread/268#email-12706-body

10 ปีที่แล้วdiscuss

No. You DO need a good understanding of a computer language and of JIT compilers to understand the code base for any just-in-time compiler for that computer language.

LuaJIT is not a toy compiler from a textbook. There's a lot of inherent complexity in a production compiler that employs advanced optimizations and needs to work on various CPU architectures and operating systems. This reflects in the code.

10 ปีที่แล้วdiscuss

This is a wrong perception. There is/was no shortage of sponsorships. I had to turn down most of these offers, due to time constraints.

10 ปีที่แล้วdiscuss

Just in case, anyone has somehow gotten to the conclusion that Lua's semantics are 'simple', they should closely inspect this example and try to figure out through which contortions the VM has to go to make this work:

    local t = setmetatable({}, {
      __index = pcall, __newindex = rawset,
      __call = function(t, i) t[i] = 42 end,
    })
    for i=1,100 do assert(t[i] == true and rawget(t, i) == 42) end

[LuaJIT has no problems with this code and turns it into 8 machine code instructions for the actual loop.]

Anyway ...

This permanent excuse of JavaScript proponents that it has more complex semantics, which somehow prevents it from being made fast, is getting old. There are no insurmountable obstacles to make JavaScript fast -- it just takes more effort!

And they dug this hole themselves, by not cleaning up the language and allowing new complicated features into the language. Well ...

11 ปีที่แล้วdiscuss

By definition, a trace doesn't have internal branches.

The solution is to use Hyperblock Scheduling. This is an extra pass that merges multiple traces, e.g. the described root trace and its side trace. The result is a single trace with a predicated IR. This is amenable to most linear optimizations, with only minor limitations.

A predicated IR is the ideal representation to apply branch-free optimizations, using bit operations or SIMD tricks. If there are any predicates left in the IR, the compiler backend will either turn it into predicated machine code (on CPUs which support that to some extent, e.g. ARM32) or generate machine code with internal branches.

11 ปีที่แล้วdiscuss

Thank you for taking the time to perform these tests!

One thing that people advocating FDO often forget: this is statically tuning the code for a specific use case. Which is not what you want for an interpreter that has many, many code paths and is supposed to run a wide variety of code.

You won't get a 30% FDO speedup in any practical scenario. It does little for most other benchmarks and it'll pessimize quite a few of them, for sure.

Ok, so feed it with a huge mix of benchmarks that simulate typical usage. But then the profile gets flatter and FDO becomes much less effective.

Anyway, my point still stands: a factor of 1.1x - 1.3x is doable. Fine. But we're talking about a 3x speedup for my hand-written machine vs. what the C compiler produces. And that's only a comparatively tiny speedup you get from applying domain-specific knowledge. Just ask the people writing video codecs about their opinion on C vector intrinsics sometime.

I write machine code, so you don't have to. The fact that I have to do it at all is disappointing. Especially from my perspective as a compiler writer.

But DJB is of course right: the key problem is not the compiler. We don't have a source language that's at the right level to express our domain-specific knowledge while leaving the implementation details to the compiler (or the hardware).

And I'd like to add: we probably don't have the CPU architectures that would fit that hypothetical language.

See my ramblings about preserving programmer intent, I made in the past: http://www.freelists.org/post/luajit/Ramblings-on-languages-...

13 ปีที่แล้วdiscuss

Oh, great! Thank you very much!