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

11–20 of 37 posts

Re: How does LuaJIT's trace compiler work?

#11

Post by rayiner »

JoeAltmaier wrote: post #5
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…

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

Re: How does LuaJIT's trace compiler work?

#12

Post by mikemike »

rayiner wrote: post #10
eloff wrote: post #2

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

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

Re: How does LuaJIT's trace compiler work?

#13

Post by k4st »

JoeAltmaier wrote: post #5
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…

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?

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.

Re: How does LuaJIT's trace compiler work?

#14

Post by recuter »

cloudflare wrote: post #9
agumonkey wrote: post #7

Earlier quoted context omitted.

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.

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

Across how many nginx servers? :)

I'll add a more serious question. This is a nice optimization, but wouldn't clever attackers respond in turn by eventually throwing highly varied traffic patterns to fluster the JIT?

Re: How does LuaJIT's trace compiler work?

#15

Post by chrismonsanto »

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…

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

Re: How does LuaJIT's trace compiler work?

#16

Post by cloudflare »

recuter wrote: post #14
cloudflare wrote: post #9

Earlier quoted context omitted.

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

Across how many nginx servers? :) I'll add a more serious question. This is a nice optimization, but wouldn't clever attackers respond in turn by eventually throwing highly varied traffic patterns to fluster the JIT?

Hundreds of servers in 23 locations worldwide, each server running multiple instances of Nginx: http://blog.cloudflare.com/a-tour-inside-cloudflares-latest-... The key fact is that this type of scale is possible with Nginx + Lua + hundreds (not thousands) of servers.

If that were to happen (and I think it's a big "if" because of the complexity of predicting what will throw it off given that the attacker doesn't know the code we are running) then we'd see the WAF latency increase and alarms would be generated immediately. That, in turn, would cause a bunch of other mechanisms to come into play.

Re: How does LuaJIT's trace compiler work?

#17

Post by recuter »

cloudflare wrote: post #16
recuter wrote: post #14

Earlier quoted context omitted.

Across how many nginx servers? :) I'll add a more serious question. This is a nice optimization, but wouldn't clever attackers respond in turn by eventually throwing highly varied traffic patterns to fluster the JIT?

Hundreds of servers in 23 locations worldwide, each server running multiple instances of Nginx: http://blog.cloudflare.com/a-tour-inside-cloudflares-latest-... The key fact is that this type of scale is possible with Nginx + Lua + hundreds (not thousands) of servers. If that were to happen (and I think it's a big "if" because of the complexity of predicting what will throw it off given that the attacker doesn't know…

Oh I get that this is the key fact, I put a smiley in there because I was fishing for a more exact number that is unlikely to be given :)

Thanks for your answer. Its a very neat setup. (My intuition is that its not a case of if but when, but you've probably won yourself quite a bit of time until that happens)

Re: How does LuaJIT's trace compiler work?

#18

Post by cloudflare »

recuter wrote: post #17
cloudflare wrote: post #16

Earlier quoted context omitted.

Hundreds of servers in 23 locations worldwide, each server running multiple instances of Nginx: http://blog.cloudflare.com/a-tour-inside-cloudflares-latest-... The key fact is that this type of scale is possible with Nginx + Lua + hundreds (not thousands) of servers. If that were to happen (and I think it's a big "if" because of the complexity of predicting what will throw it off given that the attacker doesn't know…

Oh I get that this is the key fact, I put a smiley in there because I was fishing for a more exact number that is unlikely to be given :) Thanks for your answer. Its a very neat setup. (My intuition is that its not a case of if but when, but you've probably won yourself quite a bit of time until that happens)

"Oh I get that this is the key fact, I put a smiley in there because I was fishing for a more exact number that is unlikely to be given"

The honest truth is that I actually don't know how many servers we have because it's not a number that I have to worry about.

I do know that floor(log_10(#servers)) = 2.

Re: How does LuaJIT's trace compiler work?

#19

Post by sitkack »

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…

I second this, Mike Pall should write a book. I will buy any book Mike Pall writes.

Re: How does LuaJIT's trace compiler work?

#20

Post by apw »

JoeAltmaier wrote: post #5
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…

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

Post reply on HN