5 ms·

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.
      • silentbicycle 17y ago
        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 http://selflanguage.org/documentation/published/index.html The paper "An Efficient Implementation of Self" (http://selflanguage.org/documentation/published/implementation.html 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/doc/jucs05.pdf, http://www.lua.org/papers.html 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 http://article.gmane.org/gmane.comp.lang.lua.general/58908).
        • stcredzero 17y ago
          I was thinking Strongtalk + Tracing + Type inference.
          • silentbicycle 17y ago
            Sure. (I was replying more directly to, "Java probably had the first tracing JIT-based VM outside academia.".)
    • scott_s 17y ago
      I think you're only considering static typing as an efficiency benefit. I'm equally as interested in its program-correctness benefits.
      • silentbicycle 17y ago
        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.
        • scott_s 17y ago
          Exactly! I thought that was implicit in what I said. Maybe in the future static-typing's benefit would only be for program correctness.
          • stcredzero 17y ago
            Strongtalk. Google. Read. Been done.
        • stcredzero 17y ago
          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.)
          • deleted 17y ago
            [deleted]
  • silentbicycle 17y ago
    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.)
    • Xichekolas 17y ago
      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.
      • silentbicycle 17y ago
        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.
• Perceval 17y ago
  Here are some articles from Mozilla explaining their Javascript tracing: http://hacks.mozilla.org/2009/07/tracemonkey-overview/ http://hacks.mozilla.org/2009/07/tracemonkey-overview/ http://ejohn.org/blog/tracemonkey/ http://ejohn.org/blog/tracemonkey/ http://weblogs.mozillazine.org/roadmap/archives/2008/08/tracemonkey_javascript_lightsp.html 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.
• nominolo 17y ago
  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.7516 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.7...