News for hackers. Stuff that matters.
Re:Have Tracing JIT Compilers Won? by mikek on Wednesday March 10, 2010 @08:48AM (#1180871)
Can somebody please explain what a tracing JIT is?
Re:Have Tracing JIT Compilers Won? by jrockway on Wednesday March 10, 2010 @09:26AM (#1180929)
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.

Re:Have Tracing JIT Compilers Won? by stcredzero on Wednesday March 10, 2010 @09:32AM (#1180942)
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.

Re:Have Tracing JIT Compilers Won? by jrockway on Wednesday March 10, 2010 @09:39AM (#1180963)
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.

Re:Have Tracing JIT Compilers Won? by scott_s on Wednesday March 10, 2010 @11:00AM (#1181164)
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? by silentbicycle on Wednesday March 10, 2010 @12:13PM (#1181384)
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? by stcredzero on Wednesday March 10, 2010 @12:32PM (#1181437)
Static typing and JIT compiling aren't mutually exclusive, though

Static/Dynamic typing are no longer mutually exclusive either. We need to get past this idea already.

(I mean we as a field, not present company necessarily.)

Re:Have Tracing JIT Compilers Won? by scott_s on Wednesday March 10, 2010 @12:17PM (#1181394)
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? by stcredzero on Wednesday March 10, 2010 @12:29PM (#1181429)
Strongtalk. Google. Read. Been done.
Re:Have Tracing JIT Compilers Won? by amalcon on Wednesday March 10, 2010 @09:45AM (#1180980)
Such as, for example, Java. Java probably had the first tracing JIT-based VM outside academia.
Re:Have Tracing JIT Compilers Won? by silentbicycle on Wednesday March 10, 2010 @10:25AM (#1181079)
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, LuaJIT. There are several papers about Lua (http://www.lua.org/doc/jucs05.pdf, http://www.lua.org/papers.html) and a bunch of good mailing list posts about LuaJIT (e.g. http://article.gmane.org/gmane.comp.lang.lua.general/58908).

Re:Have Tracing JIT Compilers Won? by stcredzero on Wednesday March 10, 2010 @10:50AM (#1181132)
I was thinking Strongtalk + Tracing + Type inference.
Re:Have Tracing JIT Compilers Won? by silentbicycle on Wednesday March 10, 2010 @11:21AM (#1181221)
Sure. (I was replying more directly to, "Java probably had the first tracing JIT-based VM outside academia.".)
Re:Have Tracing JIT Compilers Won? by silentbicycle on Wednesday March 10, 2010 @11:48AM (#1181300)
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? by Xichekolas on Wednesday March 10, 2010 @12:29PM (#1181430)
Many tracing JIT implementations do the compilation in a separate thread from the running VM, only providing the compiled code when it's ready. This reduces the overhead considerably, and should pretty much prevent any pauses in execution (assuming a CPU that can reasonably handle multiple threads).

There is always the risk of unbounded compilation time as you say... or at least compilation time that runs long enough that the compiled code isn't ready in time to be useful, but empirical evidence of tracing has shown it to be a net win (over interpretation) in every implementation I have seen, so this risk must be small or at least manageable.

Re:Have Tracing JIT Compilers Won? by silentbicycle on Wednesday March 10, 2010 @01:21PM (#1181557)
I'm not in any way saying that it rules out JIT compilation* , just that it's a a constraint that may not have occurred to people, and one that gives it a different (often complementary) focus than static analysis.

* I'm delighted that the LuaJIT port to amd64 is almost done, BTW. I've submitted two threads about it that haven't made it to the front page.

Re:Have Tracing JIT Compilers Won? by nominolo on Wednesday March 10, 2010 @01:56PM (#1181637)
JIT simply stands for Just-in-time compilation or optimisation, that is you delay optimising parts of your program until the program executes.

Most systems start of by interpreting the some form of bytecode and observe which parts are executed most frequently and then compile these to machine code.

Now there are two main techniques for choosing what to compile: You can count how often each function/method is executed and then compile a method to machine code when the counter reaches a certain threshold. You can even compile several versions of the function, e.g., one for integers, one for floating point values.

A tracing JIT, on the other hand, does not compile single methods at once, but whole execution paths (traces) throughout the whole program (typically some kind of loop). A trace can span several methods and thus may allow better inter-procedural optimisations. For example if a certain if-branch is taken more frequently the trace will only include the common case and will fall back to the interpreter in the uncommon case.

Tracing JIT is probably more complicated than method-based JIT, because there are issues with code duplication (e.g., several traces may include the same code) and trace exits can be expensive, so you have to efficiently link traces together dynamically. However, trace-based JIT allows more agressive optimisations and, since traces tend to be longer than methods allow more optimisations in general.

For a good paper on how powerful a tracing-JIT can be, see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7...

Re:Have Tracing JIT Compilers Won? by Perceval on Wednesday March 10, 2010 @11:25AM (#1181236)
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.