6 ms·

Have Tracing JIT Compilers Won?

76 points by nex3 17y ago

gizmo 17y ago
I'd say that for languages such as Python or Javascript tracing JIT compilers are the only viable approach. Because the languages allow anything you can't make any sensible predictions about types and call graphs at compile time (people tried; didn't work well). The incremental-JIT approach (LuaJIT) has less information to work with, and it's not aware which parts of the program are bottlenecks, so it can't intelligently decide which parts parts need optimization most. The tracing JIT is such an obvious tactic that it should be part of any dynamic language. Measure which parts are slow, then optimize those parts using the parameter type information gathered at runtime. Fall back on original code on type mismatch. The implementation is hairy, but it's a no-brainer conceptually speaking. I suspect that dynamic languages will evolve over the next 10 years to allow for really efficient compilers, but for the current languages such as Javascript I doubt we're ever going to see massive performance improvements.
- schnalle 17y ago
  * the only viable approach? v8 is pretty fast; in my programs, i've seen firefox being faster only once yet (in an optimal case for tracing) * LuaJIT is a tracing JIT * what are massive performance improvements? i'd say the jump from pure interpreter to static/tracing JIT compilation has already been a massive performance improvement
- beagle3 17y ago
  > The incremental-JIT approach (LuaJIT) has less information to work with, and it's not aware which parts of the program are bottlenecks, so it can't intelligently decide which parts parts need optimization most. You are probably thinking of LuaJIT 1.x; The recent LuaJIT 2 is tracing JIT, and it beats to hell out of every other dynamic language compiler, bar none. Mike Pall for president!
illumen 17y ago
Ahead of time compilers do work quite well for a subset of dynamic languages. Just like tracing JIT works well for a subset. This has been proven by projects like shedskin, cython, and tinypyC++. Given typing information, either explicitly or through type inference - massive speed-ups are possible. Also, tracing JIT currently does not do multiple CPU optimizations - which static compilers have been doing. They also don't do SIMD or MIMD optimizations, which compilers like gcc/icc/etc are doing. However, runtime assemblers - like 'Orc' 'corepy' and older ones like 'softwire' are proving to be lots faster in multimedia applications compared to traditional compilers or interpreters. These runtime assemblers give authors of programs access to the compilers/assemblers. Just like allowing people to specify typing, letting people construct programs at runtime can give massive speed-ups. C has even had fast interpreters for a while - see tinycc as an example. It doesn't use a tracing compiler, but a very straight forward direct translation compiler which happens to be faster than many interpreters. It's quite easy to argue 'No' to this question I think.
- beagle3 17y ago
  > C has even had fast interpreters for a while - see tinycc as an example. It doesn't use a tracing compiler, but a very straight forward direct translation compiler which happens to be faster than many interpreters. How is tinycc an interpreter? It's a full-blown compiler, alas a very simple one with very little optimization. If it weren't faster than an interpreter, I'd be shocked. For well written code, it reaches 50%-70% of modern gcc speed from tests I did a couple of years ago. I think that's on par, or even slightly better, than gcc 1.x
  - barrkel 17y ago
    It helps that C is designed to have an almost one to one mapping between its native operators and machine operations and addressing modes. For example, the pre and post increment operators are expressions with side effects, can be confusing and can provoke undefined behaviour with ease. Having two variants also seems redundant. But the two variants may have different optimal translations to underlying CPU addressing modes, while leaving the pre or post modified value in a register is often a side-effect of the CPU translation. If the language only permitted ++ as a statement, the usefulness of side-effect would be lost. It's a cliche that C is little more than portable assembler, but at a design level there's a lot of truth to it. The length of the assembly translation of C code is usually pretty directly proportional to the source code token length. In more expressive languages with more powerful abstractions, that's frequently not the case.
amix 17y ago
"Will a more static style JIT like Google's V8 be able to keep up?" V8 compiles everything to assembler and does not do JIT. V8 seems to beat TraceMonkey on both CPU and memory benchmarks ( http://shootout.alioth.debian.org/u64/benchmark.php?test=all&lang=v8&lang2=tracemonkey http://shootout.alioth.debian.org/u64/benchmark.php?test=all... ), so I doubt their approach has "lost". They probably do this because most JavaScript programs are very small and it's relatively cheap to compile everything to assembler from the start. They do their optimizations on assembler level as well - instead of doing it at bytecode level as it's done in most other VMs. This is at least the information I gathered when I looked at V8 last time - it was a year ago, so things might have changed.
- iskander 17y ago
  Just because V8 doesn't have an IR doesn't mean it's not a JIT. V8 still has to generate assembly throughout the execution of a javascript program (to create new hidden classes, patch the inline cache, etc...). See: http://code.google.com/apis/v8/design.html http://code.google.com/apis/v8/design.html
stcredzero 17y ago
With modern IDEs, tracing JIT, and type inference, I'm surprised that someone hasn't made the same lateral thinking sidestep that Hennessey & Patterson made for RISC. They offloaded much of the decoding work from the chip to the compiler, yielding faster chips in a smaller die size. Perhaps the Go language is the start of such a sidestep. We should be able to offload a lot of the work of type annotation to the IDE and compiler, yielding a compiled language with the dynamic feel of an interpreted one. In fact, for langs with clean runtime models like Lisp, we should be able to allow intermediate states of partial annotation, and allow some interpreted execution for fast prototyping. (But demand full annotation before deployment.) (EDIT: Yes, I was aware of Haskell when I posted this. Haskell. There I said it!) Is there a tool that uses a Bayesian technique for suggesting type annotation that cannot be inferred? This would be tremendously useful. (And very dangerous in the hands of the incompetent.)
- jrockway 17y ago
  You have just described Haskell. Annotate types if you want, let the compiler infer otherwise. Very dynamic feeling, but much safer. And you're right, it can make for some very fast code.
  - stcredzero 17y ago
    I'd like this for a Smalltalk style OO environment. Strongtalk got partway there.
  - cynicalkane 17y ago
    I've always got the impression that Haskell's lazy properties makes it hard to reason about code performance. You can force high-performance code, but that requires circumventing the beauty of the language. Has this problem been solved?
    - silentbicycle 17y ago
      OCaml has type inference too, though it doesn't have Haskell's typeclasses, which are very nice. (You can get much of the same functionality with functors (parametric modules), but it's not as straightforward.) OCaml isn't lazy-by-default, so reasoning about time/space performance is generally easier. It's worth considering as an alternative to Haskell.
mikek 17y ago
Can somebody please explain what a tracing JIT is?
- jrockway 17y ago
  The runtime watches the code run, and if it notices that a specific type is in use in a certain code section, it rewrites the generated code to use that type when possible. For example, if you want to add all the integers from 1 to 2^31, the JIT will eventually realize that the accumulator can be a register (with a machine int in it) instead of a JavaScript big integer. (If that overflows, it will switch back.) Obviously addition is faster when it's one CPU instruction with no memory loads, so this is a big speed win. JIT in general means you generate native code at runtime instead of at compile time.
  - stcredzero 17y ago
    Often, there's more information at runtime than compile time. This may even be true at times for statically typed languages. I think the static/dynamic type debate is just a vestige of the state of interpreter/compiler technology in the 80's. I wish everyone would get over it and introspect and debug their knee-jerk reactions so we can get on with the next stage of language implementation.
    - jrockway 17y ago
      Sure, because static typing doesn't mean you picked the best type, it just means that you picked a type. If you statically type your function as Integer -> Integer because one invocation in a million uses an integer bigger than 2^63, you are taking a speed hit for the other 999,999 calls. But a tracing JIT can just use a machine integer those times, and only fall back to the arbitrary-size Integer when it needs to.
    - amalcon 17y ago
      Such as, for example, Java. Java probably had the first tracing JIT-based VM outside academia.
KirinDave 17y ago
I'm confused. In the javascript space, it seems like V8 and squirrelfish (or is it Nitro? I prefer SF) have soundly trounced tracemonkey. Last time I checked, Squirrelfish isn't a tracing JIT centric implementation (nor is V8). I've yet to see a ttJIT javascript engine that hasn't been soundly trounced by the more conventional approaches. Perhaps it's different in the Lua world, but it seems to me like this post is claiming the exact opposite of what the evidence suggests? Don't get me wrong, here. I think trace trees are a very cool optimization technique and surely have a place in the future of JIT compilers. I just don't think they've “Won” at this point.
- daeken 17y ago
  Not to mention I don't think any pure approach will ever "win". To date, we've used a lot of different compilation techniques for wholly different use cases, as well as together for different parts of compilation where one makes more sense than another. I don't see any reason why that won't happen here. There's no reason this is an all-or-none proposition.
  - stcredzero 17y ago
    Smalltalk images are a clear demonstration that it doesn't have to be "all or none." Given a clean runtime model, one should be able to switch the execution engine on the fly, just as Smalltalk lets a Smalltalk app (debugger) act as a bytecode interpreter for the process being debugged, then switches back to JIT machine code when you hit "run".
iskander 17y ago
1) No. See V8. 2) Tracing JIT's might win for loop-centric languages. They miss some serious opportunities for parallelization in languages with rich collection-oriented operators (functional and array languages).

76 points by nex3 17y ago

gizmo 17y ago

I'd say that for languages such as Python or Javascript tracing JIT compilers are the only viable approach. Because the languages allow anything you can't make any sensible predictions about types and call graphs at compile time (people tried; didn't work well). The incremental-JIT approach (LuaJIT) has less information to work with, and it's not aware which parts of the program are bottlenecks, so it can't intelligently decide which parts parts need optimization most. The tracing JIT is such an obvious tactic that it should be part of any dynamic language. Measure which parts are slow, then optimize those parts using the parameter type information gathered at runtime. Fall back on original code on type mismatch. The implementation is hairy, but it's a no-brainer conceptually speaking. I suspect that dynamic languages will evolve over the next 10 years to allow for really efficient compilers, but for the current languages such as Javascript I doubt we're ever going to see massive performance improvements.

schnalle 17y ago
* the only viable approach? v8 is pretty fast; in my programs, i've seen firefox being faster only once yet (in an optimal case for tracing) * LuaJIT is a tracing JIT * what are massive performance improvements? i'd say the jump from pure interpreter to static/tracing JIT compilation has already been a massive performance improvement
beagle3 17y ago
> The incremental-JIT approach (LuaJIT) has less information to work with, and it's not aware which parts of the program are bottlenecks, so it can't intelligently decide which parts parts need optimization most. You are probably thinking of LuaJIT 1.x; The recent LuaJIT 2 is tracing JIT, and it beats to hell out of every other dynamic language compiler, bar none. Mike Pall for president!

illumen 17y ago

Ahead of time compilers do work quite well for a subset of dynamic languages. Just like tracing JIT works well for a subset. This has been proven by projects like shedskin, cython, and tinypyC++. Given typing information, either explicitly or through type inference - massive speed-ups are possible. Also, tracing JIT currently does not do multiple CPU optimizations - which static compilers have been doing. They also don't do SIMD or MIMD optimizations, which compilers like gcc/icc/etc are doing. However, runtime assemblers - like 'Orc' 'corepy' and older ones like 'softwire' are proving to be lots faster in multimedia applications compared to traditional compilers or interpreters. These runtime assemblers give authors of programs access to the compilers/assemblers. Just like allowing people to specify typing, letting people construct programs at runtime can give massive speed-ups. C has even had fast interpreters for a while - see tinycc as an example. It doesn't use a tracing compiler, but a very straight forward direct translation compiler which happens to be faster than many interpreters. It's quite easy to argue 'No' to this question I think.

beagle3 17y ago
> C has even had fast interpreters for a while - see tinycc as an example. It doesn't use a tracing compiler, but a very straight forward direct translation compiler which happens to be faster than many interpreters. How is tinycc an interpreter? It's a full-blown compiler, alas a very simple one with very little optimization. If it weren't faster than an interpreter, I'd be shocked. For well written code, it reaches 50%-70% of modern gcc speed from tests I did a couple of years ago. I think that's on par, or even slightly better, than gcc 1.x
- barrkel 17y ago
  It helps that C is designed to have an almost one to one mapping between its native operators and machine operations and addressing modes. For example, the pre and post increment operators are expressions with side effects, can be confusing and can provoke undefined behaviour with ease. Having two variants also seems redundant. But the two variants may have different optimal translations to underlying CPU addressing modes, while leaving the pre or post modified value in a register is often a side-effect of the CPU translation. If the language only permitted ++ as a statement, the usefulness of side-effect would be lost. It's a cliche that C is little more than portable assembler, but at a design level there's a lot of truth to it. The length of the assembly translation of C code is usually pretty directly proportional to the source code token length. In more expressive languages with more powerful abstractions, that's frequently not the case.

amix 17y ago

"Will a more static style JIT like Google's V8 be able to keep up?" V8 compiles everything to assembler and does not do JIT. V8 seems to beat TraceMonkey on both CPU and memory benchmarks ( http://shootout.alioth.debian.org/u64/benchmark.php?test=all&lang=v8&lang2=tracemonkey http://shootout.alioth.debian.org/u64/benchmark.php?test=all... ), so I doubt their approach has "lost". They probably do this because most JavaScript programs are very small and it's relatively cheap to compile everything to assembler from the start. They do their optimizations on assembler level as well - instead of doing it at bytecode level as it's done in most other VMs. This is at least the information I gathered when I looked at V8 last time - it was a year ago, so things might have changed.

iskander 17y ago
Just because V8 doesn't have an IR doesn't mean it's not a JIT. V8 still has to generate assembly throughout the execution of a javascript program (to create new hidden classes, patch the inline cache, etc...). See: http://code.google.com/apis/v8/design.html http://code.google.com/apis/v8/design.html

stcredzero 17y ago

With modern IDEs, tracing JIT, and type inference, I'm surprised that someone hasn't made the same lateral thinking sidestep that Hennessey & Patterson made for RISC. They offloaded much of the decoding work from the chip to the compiler, yielding faster chips in a smaller die size. Perhaps the Go language is the start of such a sidestep. We should be able to offload a lot of the work of type annotation to the IDE and compiler, yielding a compiled language with the dynamic feel of an interpreted one. In fact, for langs with clean runtime models like Lisp, we should be able to allow intermediate states of partial annotation, and allow some interpreted execution for fast prototyping. (But demand full annotation before deployment.) (EDIT: Yes, I was aware of Haskell when I posted this. Haskell. There I said it!) Is there a tool that uses a Bayesian technique for suggesting type annotation that cannot be inferred? This would be tremendously useful. (And very dangerous in the hands of the incompetent.)

jrockway 17y ago
You have just described Haskell. Annotate types if you want, let the compiler infer otherwise. Very dynamic feeling, but much safer. And you're right, it can make for some very fast code.
- stcredzero 17y ago
  I'd like this for a Smalltalk style OO environment. Strongtalk got partway there.
- cynicalkane 17y ago
  I've always got the impression that Haskell's lazy properties makes it hard to reason about code performance. You can force high-performance code, but that requires circumventing the beauty of the language. Has this problem been solved?
  - silentbicycle 17y ago
    OCaml has type inference too, though it doesn't have Haskell's typeclasses, which are very nice. (You can get much of the same functionality with functors (parametric modules), but it's not as straightforward.) OCaml isn't lazy-by-default, so reasoning about time/space performance is generally easier. It's worth considering as an alternative to Haskell.

mikek 17y ago

Can somebody please explain what a tracing JIT is?

jrockway 17y ago
The runtime watches the code run, and if it notices that a specific type is in use in a certain code section, it rewrites the generated code to use that type when possible. For example, if you want to add all the integers from 1 to 2^31, the JIT will eventually realize that the accumulator can be a register (with a machine int in it) instead of a JavaScript big integer. (If that overflows, it will switch back.) Obviously addition is faster when it's one CPU instruction with no memory loads, so this is a big speed win. JIT in general means you generate native code at runtime instead of at compile time.
- stcredzero 17y ago
  Often, there's more information at runtime than compile time. This may even be true at times for statically typed languages. I think the static/dynamic type debate is just a vestige of the state of interpreter/compiler technology in the 80's. I wish everyone would get over it and introspect and debug their knee-jerk reactions so we can get on with the next stage of language implementation.
  - jrockway 17y ago
    Sure, because static typing doesn't mean you picked the best type, it just means that you picked a type. If you statically type your function as Integer -> Integer because one invocation in a million uses an integer bigger than 2^63, you are taking a speed hit for the other 999,999 calls. But a tracing JIT can just use a machine integer those times, and only fall back to the arbitrary-size Integer when it needs to.
  - amalcon 17y ago
    Such as, for example, Java. Java probably had the first tracing JIT-based VM outside academia.

KirinDave 17y ago

I'm confused. In the javascript space, it seems like V8 and squirrelfish (or is it Nitro? I prefer SF) have soundly trounced tracemonkey. Last time I checked, Squirrelfish isn't a tracing JIT centric implementation (nor is V8). I've yet to see a ttJIT javascript engine that hasn't been soundly trounced by the more conventional approaches. Perhaps it's different in the Lua world, but it seems to me like this post is claiming the exact opposite of what the evidence suggests? Don't get me wrong, here. I think trace trees are a very cool optimization technique and surely have a place in the future of JIT compilers. I just don't think they've “Won” at this point.

daeken 17y ago
Not to mention I don't think any pure approach will ever "win". To date, we've used a lot of different compilation techniques for wholly different use cases, as well as together for different parts of compilation where one makes more sense than another. I don't see any reason why that won't happen here. There's no reason this is an all-or-none proposition.
- stcredzero 17y ago
  Smalltalk images are a clear demonstration that it doesn't have to be "all or none." Given a clean runtime model, one should be able to switch the execution engine on the fly, just as Smalltalk lets a Smalltalk app (debugger) act as a bytecode interpreter for the process being debugged, then switches back to JIT machine code when you hit "run".

iskander 17y ago

1) No. See V8. 2) Tracing JIT's might win for loop-centric languages. They miss some serious opportunities for parallelization in languages with rich collection-oriented operators (functional and array languages).