How does LuaJIT's trace compiler work?

Post by JoeAltmaier » Sat, Nov 30, 2013, 2:47 PM UTC

rayiner wrote: post #11

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?

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

Post by pygy_ » Sun, Dec 01, 2013, 12:24 AM UTC

Tobu wrote: post #29

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 by ldc » Tue, Dec 03, 2013, 12:24 PM UTC

mikemike wrote: post #12

rayiner wrote: post #10

Earlier quoted context omitted.

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…

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…

Post by apw » Thu, Dec 05, 2013, 11:57 AM UTC

mikemike wrote: post #23

apw wrote: post #20

Earlier quoted context omitted.

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…