Have Tracing JIT Compilers Won? • Hacker News Board

Re: Have Tracing JIT Compilers Won?

#21

Post by scott_s » Wed, Mar 10, 2010, 4:00 PM UTC

stcredzero wrote: post #14

jrockway wrote: post #12

Earlier quoted context omitted.

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

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.

I think you're only considering static typing as an efficiency benefit. I'm equally as interested in its program-correctness benefits.

Re: Have Tracing JIT Compilers Won?

#22

Post by cynicalkane » Wed, Mar 10, 2010, 4:11 PM UTC

jrockway wrote: post #13

stcredzero wrote: post #10

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

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.

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?

Re: Have Tracing JIT Compilers Won?

#23

Post by silentbicycle » Wed, Mar 10, 2010, 4:21 PM UTC

stcredzero wrote: post #19

silentbicycle wrote: post #18

Earlier quoted context omitted.

That depends on whether you consider the Smalltalk and Self research at Sun and Xeroc PARC to be "academia". Much of the JVM optimization technology came directly from those. http://selflanguage.org/documentation/published/index.html The paper "An Efficient Implementation of Self" ( http://selflanguage.org/documentation/published/implementati... ) is a good overview. Lua is another language with a great JIT compiler,…

I was thinking Strongtalk + Tracing + Type inference.

Sure. (I was replying more directly to, "Java probably had the first tracing JIT-based VM outside academia.".)

Re: Have Tracing JIT Compilers Won?

#24

Post by silentbicycle » Wed, Mar 10, 2010, 4:23 PM UTC

cynicalkane wrote: post #22

jrockway wrote: post #13

Earlier quoted context omitted.

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.

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?

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.

Re: Have Tracing JIT Compilers Won?

#25

Post by Perceval » Wed, Mar 10, 2010, 4:25 PM UTC

mikek wrote: post #11

Can somebody please explain what a tracing JIT is?

Here are some articles from Mozilla explaining their Javascript tracing:

http://hacks.mozilla.org/2009/07/tracemonkey-overview/

http://ejohn.org/blog/tracemonkey/

http://weblogs.mozillazine.org/roadmap/archives/2008/08/trac...

These are tangentially related to the article topic, but gives you some sense of what tracing does.

Re: Have Tracing JIT Compilers Won?

#26

Post by silentbicycle » Wed, Mar 10, 2010, 4:48 PM UTC

jrockway wrote: post #12

mikek wrote: post #11

Can somebody please explain what a tracing JIT is?

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

One important issue is that compilation often needs to happen in bounded time. A JIT-compiler that does overly elaborate optimizations at runtime may lead to excessive pauses, and sometimes that's a dealbreaker. (Some of the same trade-offs appear with non-incremental garbage collection.)

Re: Have Tracing JIT Compilers Won?

#27

Post by KirinDave » Wed, Mar 10, 2010, 4:58 PM UTC

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.

Re: Have Tracing JIT Compilers Won?

#28

Post by silentbicycle » Wed, Mar 10, 2010, 5:13 PM UTC

scott_s wrote: post #21

stcredzero wrote: post #14

Earlier quoted context omitted.

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.

I think you're only considering static typing as an efficiency benefit. I'm equally as interested in its program-correctness benefits.

Static typing and JIT compiling aren't mutually exclusive. You can do all the static analysis, checking, whole-program optimization, etc. that's feasible at compile time, compile to bytecode, and then do JIT compilation at runtime.

Edit: We appear to be in fierce agreement.

Re: Have Tracing JIT Compilers Won?

#29

Post by scott_s » Wed, Mar 10, 2010, 5:17 PM UTC

silentbicycle wrote: post #28

scott_s wrote: post #21

Earlier quoted context omitted.

I think you're only considering static typing as an efficiency benefit. I'm equally as interested in its program-correctness benefits.

Static typing and JIT compiling aren't mutually exclusive. You can do all the static analysis, checking, whole-program optimization, etc. that's feasible at compile time, compile to bytecode, and then do JIT compilation at runtime. Edit: We appear to be in fierce agreement.

Exactly! I thought that was implicit in what I said. Maybe in the future static-typing's benefit would only be for program correctness.

Re: Have Tracing JIT Compilers Won?

#30

Post by jrockway » Wed, Mar 10, 2010, 5:27 PM UTC

cynicalkane wrote: post #22

jrockway wrote: post #13

Earlier quoted context omitted.

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.

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?

The "reasoning about performance" is more of a trap for the unwary than a fundamental problem.

Example; you have two threads in a producer/consumer setup. The first thread puts "g x" into the queue. The second thread removes this, and applies "f", and puts the result into a result queue. Then a result-processing thread prints those to the file.

You run this, and notice that it doesn't really take advantage of all cores. It seems to run slower on 2 or 3 cores than it does on 1 core, even though "f" and "g" are of roughly equal complexity and the application of each happens in a different thread! WTF?!?

The problem is, of course, that lazy evaluation "helped you". You never needed "g x" in the first thread, so it wasn't evaluated; the thunk was put in the queue. When you applied "f (g x)" in the second thread, you still didn't need the value of either computation, so it was never evaluated. You just put a thunk in the result queue. Finally, in the result-printing thread, you did need the result -- so all the work to evaluate the result was done there; in a single thread.

You realize this, switch to strict queues, and now your app is 2x faster.

(BTW, I simplified the producer/consumer model a bit. Normally you have one thread feeding work into a queue, n threads reading from that queue, doing work, and putting results into a result queue, and then a final result-aggregator thread. The end result would be the same; all the work would be done in that last thread. Slow!)