How does LuaJIT's trace compiler work?

http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-compiler-work,1

by slashdev • 13 years ago

92 35 13 years ago

freelists.org

eloff• 13 years ago

Also of interest, are trace compilers suited for static languages?

http://www.freelists.org/post/luajit/Are-trace-compilers-sui...

rayiner2• 13 years ago

Some of the original work on trace compilation was done in the context of Java, a static language: http://static.usenix.org/event/vee06/full_papers/p144-gal.pd....

What trace compilation buys you is: 1) elimination of method call boundaries in analysis; 2) elimination of data flow merges.

Dynamic languages benefit particularly from these characteristics because their semantics are replete with method calls and data flow merges (e.g. after any generic operation). But static languages can have these qualities too.

mikemike4• 13 years ago

To give credit, where credit is due: the original work on trace compilation is much, much older. The paper you cited is an application.

The fundamental papers to hunt for are Joseph A. Fisher's publications on trace scheduling (sadly, his PhD thesis from the 70ies is nowhere to be found online) and the Multiflow reports from the 90ies. The Dynamo paper built upon that foundation ten years later in '99 (get the full HP report, not the short summary). A related research area is about trace caches for use in CPUs with various papers from the 90ies.

AFAIK there's no up-to-date comprehensive summary of the state of research on trace compilers. Most papers don't even scratch the surface of the challenges you'll face when building a production-quality trace compiler.

mikemike4• 13 years ago

Err, the title of this item is a bit misleading, although it's the subject of the posting on the mailing list.

One cannot explain it all in a single post. I just answered some specific questions, omitting most details.

cloudflare4• 13 years ago

From the post:

    A recent example illustrates the power of this approach:

    Cloudflare's WAF (web application firewall) basically generates
    Lua code for the (highly non-linear) maze of firewall rules. An
    incoming attack triggers certain rules and the corresponding paths
    are turned into linearized traces. These can be heavily optimized
    by LuaJIT, much more so than you could ever hope to do with a
    static compiler.

    When a different attack wave is started, it'll spawn different
    traces -- i.e. the generated code dynamically adapts to the
    specific attacks.

    The result is a much higher firewall throughput than you might be
    able to achieve with a data-driven or a static compilation
    approach. This directly equates into money saved on machines
    needed to handle the load.

Added to that is the fact that the WAF configuration (which is automatically generated Lua code) is different for each customer and so we rely heavily on caching and JITing to get the performance.

The bottom line is that LuaJIT is very fast and very flexible.

JoeAltmaier2• 13 years ago

Wow I'd need some evidence to believe JIT can do a better job than a 'static' compiler. What can JIT do to optimize 'much more so'? How about a little more? If you know some common conditional jump stats you can do slightly better. Is there anything else?

justincormack2• 13 years ago

you have a very large number of options so getting code locality between the ones that are applicable is important, at a guess. performance in large state machines is very much locality dependent but this way you get to do this dynamically not statically.

rayiner2• 13 years ago

A static compiler has to generate code that handles every possible path through the code. This tends to pessimize code downstream of a control flow merge point, because such code has to be compiled assuming it can be reached via multiple paths. A trace compiler can compile only the paths that are actually taken on a given workload, and compile the (dynamically) uncommon cases into exits to the interpreter.

The firewall rule example Mike Pall gives is a pretty good one. You have code that has many different paths through it, but only specific ones are triggered, dynamically, by a particular attack. Those can be compiled into traces that assume the other paths are not taken (except to guard the possible control flow splits with trace exits). This can allow an optimizer to make much more aggressive assumptions on the actually-taken paths.

k4st• 13 years ago

Dynamic binary translation can sometimes get performance improvements. This is because you would still statically compile your program, and then at runtime, the DBT system dynamically decodes and re-encodes the binary instructions. With a DBT system, you can do tracing, by identifying hot paths and such and lining those basic blocks up in your code cache.

apw2• 13 years ago

You might want to read about Dynamo:

http://www.hpl.hp.com/techreports/1999/HPL-1999-78.pdf

"Contrary to intuition, we demonstrate that it is possible to use a piece of software to improve the performance of a native, statically optimized program binary, while it is executing. Dynamo not only speeds up real application programs, its performance improvement is often quite significant."

agumonkey• 13 years ago

Interesting to see JIT compilation used for low level and what I assume high perf workload. NetBSD is supporting in-kernel lua code, I wonder if dynamic compilation can produce expressive and flexible performant execution too in drivers.

ps: I wonder if it's related, maybe cloudflare uses netbsd and pushed for kernel embedding, or they just benefited from netbsd lua love.

justincormack2• 13 years ago

Entirely unrelated I think.

cloudflare4• 13 years ago

We are entirely Linux not NetBSD and are not currently using Lua in the kernel at all. We did, however, sponsor some of Mike Pall's work on LuaJIT based on our particular workload: http://luajit.org/sponsors.html#sponsorship_perf

We use Lua for the WAF (as Mike says), but also for all request processing. This is in part because we use Nginx and in part because employ agentzh (http://agentzh.org/) and he works on OpenResty. Fairly recently we moved all processing of requests through CloudFlare to a Lua-based system inside Nginx.

That's >5B pages views per 24 hours going through LuaJIT-ed code.

ivanr• 13 years ago

Just as a side comment, optimisations to the attack paths are unlikely to make a substantial impact on overall performance, given that attack requests are only a fraction of all requests processed at any given time. (Excluding DoS, of course, but that's not an area where you'd expect a WAF to do much.) In a WAF, you want to heavily optimise then non-attack paths.

pygy_2• 13 years ago

Later in the thread:

        From: Mike Pall

    ...

    [I refuse to contribute to stackoverflow anymore, due to some
    recent incidents. I can't even edit *my own* answers to correct
    them, without some anonymous fool rejecting my edits. Ok, so maybe
    they don't know I wrote the damned thing. But then they really
    shouldn't be allowed to moderate Lua-specific questions. This is
    just plain unacceptable.]

    --Mike

This really is a shame (edit: the SO situation, not Mike's decision. He's the one who should have mod powers).

danielbarla• 13 years ago

I suspect it's due to SO's treatment of low-reputation users. For those who don't frequent SO, when you first sign up, you are severely limited in functionality. So called "privileges" are unlocked as you gain reputation. Specifically, until his rep reaches 2000 (roughly 200 upvotes to his answers), his edits need to be approved by someone who has a high enough rep.

I guess the system works fairly well in preventing spam and gaming of the system. In this case, it seems to have backfired, leaving an expert feeling unwanted. BTW, his reputation on SO seems to be around 200 only [1] (around 20 upvotes altogether), which is very low.

In this case, the issue is probably two-fold (and serves to highlight some of the imbalances in the reputation system). Firstly, his area of expertise / activity is less popular than the mainstream ones on SO (lua / luajit only have 5000 questions tagged collectively, which is around 100x less than C#, Java, etc).

Secondly, as an expert, his answers probably cater for highly specific, difficult technical problems. These typically fly under the radar and get a handful of upvotes (unless they show something of interest to the rest of the communities, in which case a perverse upvoting cycle can happen via the popular questions list, with leading answers getting several hundreds of upvotes).

Disregarding confirmation bias w.r.t. reputation (i.e. how anything one of the SO super stars says is immediately upvoted), the most popular answers seem to be ones that involve a popular language, address a common misunderstanding / lack of knowledge (usually at a trivial or fairly elementary level), and have an element of surprise to it, which makes people share the answer. As an example, JavaScript's type coercion is always popular, even though it's been discussed dozens of times: [2]

These two issues, taken together, mean that you could spend an afternoon prototyping some guy's difficult problem, solving it, writing up a good answer, and getting only 3 upvotes for it.

A similar thing can be said for less populated time-zones; if you're living in one, most likely the questions you are answering are not on the "first page" by the time most of the SO world wakes up / has their morning coffee.

As an aside, I suspect most reputation-based systems suffer from these effects. Some of it can be seen right here on HN. Nevertheless, I guess they work slightly better than having no reputation system, as long as people aren't purposely exploiting it.

[1] http://stackoverflow.com/users/1657919/mike-pall

[2] http://stackoverflow.com/questions/359494/does-it-matter-whi...

re• 13 years ago

The edit in question: http://stackoverflow.com/review/suggested-edits/3395606

Ignoring the issue of whether the edit should have been accepted or rejected, it was subject to moderation because he appears to have (inadvertently) created multiple separate accounts, and was using one to attempt to edit a post made by the other; I don't think self-edits require review.

Tobu• 13 years ago

He's being a prima donna. Edits by a third-party get reviewed, there is no way you could accept that edit (which was from a different account) without allowing other random people to edit his posts in the same way. You can't blame stack overflow for erring of the side on respecting the author's intent.

pygy_2• 13 years ago

FYI, he's participating in this thread.

ajtulloch• 13 years ago

Somewhat tangential - the LuaJIT source [1] is an absolute masterpiece of software engineering in C. The detailed comments (especially on the optimizations - "luajit/src/lj_opt...") are incredibly interesting reading.

One of my favourite quotes is at https://github.com/LuaDist/luajit/blob/master/src/lj_opt_nar...

  ** [A recursive backpropagation algorithm with backtracking, employing
  ** skip-list lookup and round-robin caching, emitting stack operations
  ** on-the-fly for a stack-based interpreter -- and all of that in a meager
  ** kilobyte? Yep, compilers are a great treasure chest. Throw away your
  ** textbooks and read the codebase of a compiler today!]

[1]: https://github.com/LuaDist/luajit

malkia• 13 years ago

I've borrowed the way Mike writes his enum macros.

rombix• 13 years ago

Somewhat related discussion about a possibility of building tracing JITs for other languages on top of the LuaJIT code base:

http://www.freelists.org/post/luajit/To-which-extent-LuaJIT-...

How does LuaJIT's trace compiler work?

Related Stories