7 ms·

How does LuaJIT's trace compiler work?

92 points by eloff 13y ago

eloff 13y ago
Also of interest, are trace compilers suited for static languages? http://www.freelists.org/post/luajit/Are-trace-compilers-suited-for-static-languages,1 http://www.freelists.org/post/luajit/Are-trace-compilers-sui...
- rayiner 13y 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.pdf 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.
  - mikemike 13y 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.
    - chrismonsanto 13y ago
      > 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-level knowledge in more traditional compilation methods (aka, not JIT).
      - sitkack 13y ago
        I second this, Mike Pall should write a book. I will buy any book Mike Pall writes.
        swah 13y ago
        I'll read any book Mike Pall recommends.
      - beagle3 13y ago
        Thirded.
    - ldc 13y ago
      Fisher's thesis is actually available on the internet archive: https://archive.org/details/optimizationofho00fish https://archive.org/details/optimizationofho00fish
      - mikemike 13y ago
        Oh, great! Thank you very much!
mikemike 13y 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.
cloudflare 13y 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.
- JoeAltmaier 13y 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?
  - justincormack 13y 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.
  - rayiner 13y 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.
pygy_ 13y 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 13y 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 http://stackoverflow.com/users/1657919/mike-pall [2] http://stackoverflow.com/questions/359494/does-it-matter-which-equals-operator-vs-i-use-in-javascript-comparisons http://stackoverflow.com/questions/359494/does-it-matter-whi...
ajtulloch 13y 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_narrow.c#L155 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 https://github.com/LuaDist/luajit
- malkia 13y ago
  I've borrowed the way Mike writes his enum macros.
rombix 13y 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-is-specific-to-Lua http://www.freelists.org/post/luajit/To-which-extent-LuaJIT-...
losethos 13y ago
C switch makes a decision tree

92 points by eloff 13y ago

eloff 13y ago

Also of interest, are trace compilers suited for static languages? http://www.freelists.org/post/luajit/Are-trace-compilers-suited-for-static-languages,1 http://www.freelists.org/post/luajit/Are-trace-compilers-sui...

rayiner 13y 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.pdf 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.
- mikemike 13y 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.
  - chrismonsanto 13y ago
    > 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-level knowledge in more traditional compilation methods (aka, not JIT).
    - sitkack 13y ago
      I second this, Mike Pall should write a book. I will buy any book Mike Pall writes.
      - swah 13y ago
        I'll read any book Mike Pall recommends.
    - beagle3 13y ago
      Thirded.
  - ldc 13y ago
    Fisher's thesis is actually available on the internet archive: https://archive.org/details/optimizationofho00fish https://archive.org/details/optimizationofho00fish
    - mikemike 13y ago
      Oh, great! Thank you very much!

mikemike 13y 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.

cloudflare 13y 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.

JoeAltmaier 13y 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?
- justincormack 13y 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.
- rayiner 13y 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.

pygy_ 13y 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 13y 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 http://stackoverflow.com/users/1657919/mike-pall [2] http://stackoverflow.com/questions/359494/does-it-matter-which-equals-operator-vs-i-use-in-javascript-comparisons http://stackoverflow.com/questions/359494/does-it-matter-whi...

ajtulloch 13y 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_narrow.c#L155 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 https://github.com/LuaDist/luajit

malkia 13y ago
I've borrowed the way Mike writes his enum macros.

rombix 13y 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-is-specific-to-Lua http://www.freelists.org/post/luajit/To-which-extent-LuaJIT-...

losethos 13y ago

C switch makes a decision tree