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

How does LuaJIT's trace compiler work?

freelists.org

Post reply on HN
Print view View original

21–30 of 37 posts

Re: How does LuaJIT's trace compiler work?

#21

Post by beagle3 »

chrismonsanto wrote: post #15
mikemike wrote: post #12

Earlier quoted context omitted.

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

> 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. In general, there are few good + comprehensive resources for advanced compilation techniques. I would gladly fork over $$$ if you wrote a textbook on tracing compilers aimed at people who have expert…

Thirded.

Re: How does LuaJIT's trace compiler work?

#22

Post by pygy_ »

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

Re: How does LuaJIT's trace compiler work?

#23

Post by mikemike »

apw wrote: post #20
JoeAltmaier wrote: post #5

Earlier quoted context omitted.

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?

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

Oh, well ... pasting my standard rant on this:

This is a common misinterpretation of the Dynamo paper: they compiled their C code at the lowest optimization level and then ran the (suboptimal) machine code through Dynamo. So there was actually something left to optimize.

Think about it this way: a 20% difference isn't unrealistic if you compare -O1 vs. -O3.

But it's completely unrealistic to expect a 20% improvement if you'd try this with the machine code generated by a modern C compiler at the highest optimization level.

Claiming that JIT compilers outperform static compilers, solely based on this paper, is an untenable position.

But, yes, JIT compilers can outperform static compilers under specific circumstances. This has more to do with e.g. better profiling feedback or extra specialization opportunities. But this is not what this paper demonstrates.

Many compiler optimizations have strong non-linear costs in terms of the number of control flow edges. A static compiler has to punt at a certain complexity. OTOH a JIT compiler is free to ignore many edges, since it may fall back to an interpreter for cold paths or attach new code anytime later if some edges become hot.

One interesting example is auto-vectorization (SIMDization) where static compilers have to generate code for all possible combinations of vector alignments in case the underlying alignment of the participating vectors is not statically known. This quickly gets very expensive in terms of code space. OTOH a JIT compiler can simply specialize to the observed vector alignment(s) at runtime, which show almost no variation in practice.

Re: How does LuaJIT's trace compiler work?

#24

Post by ivanr »

cloudflare wrote: post #4

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

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.

Re: How does LuaJIT's trace compiler work?

#25

Post by ajtulloch »

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

Re: How does LuaJIT's trace compiler work?

#26

Post by danielbarla »

pygy_ wrote: post #22

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

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: How does LuaJIT's trace compiler work?

#27

Post by malkia »

ajtulloch wrote: post #25

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

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

Re: How does LuaJIT's trace compiler work?

#28

Post by re »

pygy_ wrote: post #22

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

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.

Re: How does LuaJIT's trace compiler work?

#29

Post by Tobu »

pygy_ wrote: post #22

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

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.
Post reply on HN