7 ms·

Tracing JITs and modern CPUs

78 points by jsnell 11y ago

bluetomcat 11y ago
He mentions that the demands of tracing JITs and current Intel CPUs are well aligned. I wonder, how well do they play with the instruction cache? Generating little chunks of code on-demand and then executing them seems to be a recipe for instruction cache misses?
pjc50 11y ago
We have known for a long time that the worst performance comes from iterating a "fetch value from memory -> make decision based on result about what to fetch next" pattern. Unfortunately almost everything that can be described as business logic looks like that. It's also common in object-orientated systems.
- pjmlp 11y ago
  When I did "Algorithms and Data Structures" back in mid-90's, our teacher did consider amount of memory and disk access on her evaluation of our solutions. Being lazy on getting optimal solutions meant worse evaluations. How many do that to their students nowadays?
  - lorenzhs 11y ago
    I'm grading a graduate level course in Algorithm Engineering, and my testing framework measures time, memory requirements (peak/total/number of allocations), cache behaviour (L1/L2/L3 misses, TLB misses) and other performance counters. It's very easy to do this using libPAPI and malloc instrumentation ;)
- agumonkey 11y ago
  For a reason I read this as a clojure transducer exercise.
- geocar 11y ago
  Only if you program with atoms. If you program with arrays then it is my experience that very few problems look that way. Array programming also keeps absolute program size small which means your program isn't running in main memory but in cache memory which produces anywhere from 10-100x speedups for business software just by itself! I don't know if I fully understand what you mean by object-orientated.
  - vvanders 11y ago
    Take a look a Mike Acton's talks, he does a pretty good job of breaking down why OOP just isn't built for high performance(arranging data by logical association rather than data access patterns). Yeah, your metapoint is is worthwhile, all the JIT in the world aint gonna help you if you're cache missing every damn fetch(hello Java).
    - corysama 11y ago
      > all the JIT in the world aint gonna help you if you're cache missing every damn fetch(hello Java). Acton (sort of) has a talk about that too. Except he speaks about traditional, ahead-of-time compilers. Tldr is that because of how the vast majority of programmers arrange their data, CPUs spends the vast majority of their time stalling on memory. Therefore improvements in optimizing compilers can only marginally help the marginally small section of running time spent actually exercising the ALUs. The solution is to devote more effort to changing our habits regarding data layouts.
      - vvanders 11y ago
        Yup, shaving 5-10 cycles from compiler optimizations doesn't help you when you've got a deficit of 200+ cycles per cache miss. Working with FPGAs and DRAM really makes a lot of reasons behind this and lot of other "obscure" performance issues like pipelining crystal clear.
    - wiml 11y ago
      OOP encourages this kind of memory layout, but I don't think it requires it. I don't think there's anything preventing, say, a JVM or a CLOS implementation from storing "hot" members/fields in compact homogeneous arrays and "cold" ones in more traditional heap-allocated structures, perhaps with the help of a few programmer annotations. Or a tracing VM cooperating with a copying GC to perform this kind of optimization on the fly. This seems like it could make an interesting CS research project, in the (unlikely) case that it isn't one already.
krig 11y ago
For anyone interested in learning more about Tracing JITs and the problems involved in implementing them should read the paper "Trace-based Just-in-time Compilation for Haskell" by Thomas Schilling [1]. In it, he explains the details of implementing a basic VM and tracing JIT based on LuaJIT, and deals with a lot of the issues involved. For example, the choice of where to begin a trace and for how long to trace is crucial for performance. Traces that are too long will rarely complete, and selecting poorly and tracing something that won't actually be on the hot path has significant cost. With poor trace selection, a tracing JIT can even be slower than an optimized interpreter. Interestingly, the language itself also influences the viability of tracing: A language with explicit loop instructions is easier to trace since any loop instruction is an intuitive starting point, whereas a language which relies on recursion and TCO is less cooperative in this regard. One possibility is rewriting recursive constructions to imperative loops in a pass prior to trace selection. Personally, after reading the paper I think that there is the possibility for amazing performance from tracing JITs, but the unpredictability and reliance on heuristics makes the practical value over method JITs or static compilation questionable. It is similar to the complexities of GC implementation: As performance gains are made, complexity shoots through the roof while predictability suffers. There's no easy answer to that problem. [1]: http://src.acm.org/2013/ThomasSchilling.pdf http://src.acm.org/2013/ThomasSchilling.pdf
- pron 11y ago
  I had a short conversation at ECOOP with Ben Titzer (who works on V8 at Google, and I think used to work on HotSpot at Sun), who said simply: tracing JITs are good for short programs; for large programs you need a partial-evaluation method JIT. Partial evaluation also produces better results for a larger class of programs. Tracing JITs' advantages are that they're simpler to write than partial evaluation JITs, and produce decent code faster, which is why they're used for JavaScript. There is great progress in partial evaluation JITs going on in the Graal/Truffle project[1] (Graal is the compiler; Truffle is a framework to write language frontends for Graal), which will be available as a pluggable compiler for HotSpot in Java 9. Here are a couple of optimizations Graal yields for Ruby: https://twitter.com/ChrisGSeaton/status/619885182104043520 https://twitter.com/ChrisGSeaton/status/619885182104043520 [1]: https://wiki.openjdk.java.net/display/Graal/Publications+and+Presentations https://wiki.openjdk.java.net/display/Graal/Publications+and...
haberman 11y ago
I think the article is making out trace compilers to be far more limited than they actually are. > Consider these optimization tips: Avoid nested loops. I don't think this is true at all. The article is arguing that because a trace only contains one loop, that nested loops can't be trace-compiled. As I understand it, nested loops are totally possible to trace-compile by having multiple traces that link to each other. See what Mike Pall wrote about LuaJIT (http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-compiler-work,1 http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-...): "If the inner loop has a low iteration count, it'll be unrolled and inlined. For most loop nestings there'll be a single trace for the outer loop that goes 'around' the inner loop and joins its exit with its entry. Otherwise traces link to each other in linear pieces." I would take what this article says with a heavy grain of salt. I don't think that tracing JITs are at all like "programming in a straight jacket." Look at the LuaJIT performance optimization guide. There is nothing in there about avoiding nested loops, avoiding tiny loops, or avoiding loops with unpredictable iteration counts. It does however recommend reducing unpredictable branches: http://wiki.luajit.org/Numerical-Computing-Performance-Guide http://wiki.luajit.org/Numerical-Computing-Performance-Guide
- mrottenkolber 11y ago
  > I think the article is making out trace compilers to be far more limited than they actually are. Luke (the posts' author) and others are building a high performance software Ethernet switch[1] using LuaJIT. Let me assure you that these considerations actually come from experience rather than speculation. > As I understand it, nested loops are totally possible to trace-compile by having multiple traces that link to each other. Sometimes it works, sometimes it doesn't. We can't really expect everybody using Snabb Switch to understand the internals of LuaJIT so restrictive guidelines are useful for us. Disclaimer: Consulting for Snabb GmbH [1]: https://github.com/snabbco/snabbswitchhttps://github.com/snabbco/snabbswitch https://github.com/snabbco/snabbswitchhttps://github.com/sna...
  - haberman 11y ago
    > Let me assure you that these considerations actually come from experience rather than speculation. Good to know. The article did not make this clear.
talles 11y ago
First time I see someone blogging with GitHub issues and, surprisingly, looks like it works well. Markdown, tags, comments plus a index (README.md) if you need one.
- qznc 11y ago
  Also "follow" and "kudos", named "watch" and "star". Getting a feed of the blog requires filtering, though.
- deleted 11y ago
  [deleted]
TheLoneWolfling 11y ago
Two semi-tangential ideas: I wish it was possible to do things along the lines of "fetch this data from RAM and at the same time start recomputing it, whichever is faster". And also, I wish there was a "branch upcoming / branch execute" split. In other words, instead of just "here's a branch", it's more along the lines of "you will have to branch on <x>. <other instructions> now branch on <x>." Effectively a variable number of branch-delay slot(s). Wouldn't help for straight pointer-chasing, but in other situations it could.

78 points by jsnell 11y ago

He mentions that the demands of tracing JITs and current Intel CPUs are well aligned. I wonder, how well do they play with the instruction cache? Generating little chunks of code on-demand and then executing them seems to be a recipe for instruction cache misses?

pjc50 11y ago

We have known for a long time that the worst performance comes from iterating a "fetch value from memory -> make decision based on result about what to fetch next" pattern. Unfortunately almost everything that can be described as business logic looks like that. It's also common in object-orientated systems.

pjmlp 11y ago
When I did "Algorithms and Data Structures" back in mid-90's, our teacher did consider amount of memory and disk access on her evaluation of our solutions. Being lazy on getting optimal solutions meant worse evaluations. How many do that to their students nowadays?
- lorenzhs 11y ago
  I'm grading a graduate level course in Algorithm Engineering, and my testing framework measures time, memory requirements (peak/total/number of allocations), cache behaviour (L1/L2/L3 misses, TLB misses) and other performance counters. It's very easy to do this using libPAPI and malloc instrumentation ;)
agumonkey 11y ago
For a reason I read this as a clojure transducer exercise.
geocar 11y ago
Only if you program with atoms. If you program with arrays then it is my experience that very few problems look that way. Array programming also keeps absolute program size small which means your program isn't running in main memory but in cache memory which produces anywhere from 10-100x speedups for business software just by itself! I don't know if I fully understand what you mean by object-orientated.
- vvanders 11y ago
  Take a look a Mike Acton's talks, he does a pretty good job of breaking down why OOP just isn't built for high performance(arranging data by logical association rather than data access patterns). Yeah, your metapoint is is worthwhile, all the JIT in the world aint gonna help you if you're cache missing every damn fetch(hello Java).
  - corysama 11y ago
    > all the JIT in the world aint gonna help you if you're cache missing every damn fetch(hello Java). Acton (sort of) has a talk about that too. Except he speaks about traditional, ahead-of-time compilers. Tldr is that because of how the vast majority of programmers arrange their data, CPUs spends the vast majority of their time stalling on memory. Therefore improvements in optimizing compilers can only marginally help the marginally small section of running time spent actually exercising the ALUs. The solution is to devote more effort to changing our habits regarding data layouts.
    - vvanders 11y ago
      Yup, shaving 5-10 cycles from compiler optimizations doesn't help you when you've got a deficit of 200+ cycles per cache miss. Working with FPGAs and DRAM really makes a lot of reasons behind this and lot of other "obscure" performance issues like pipelining crystal clear.
  - wiml 11y ago
    OOP encourages this kind of memory layout, but I don't think it requires it. I don't think there's anything preventing, say, a JVM or a CLOS implementation from storing "hot" members/fields in compact homogeneous arrays and "cold" ones in more traditional heap-allocated structures, perhaps with the help of a few programmer annotations. Or a tracing VM cooperating with a copying GC to perform this kind of optimization on the fly. This seems like it could make an interesting CS research project, in the (unlikely) case that it isn't one already.

krig 11y ago

For anyone interested in learning more about Tracing JITs and the problems involved in implementing them should read the paper "Trace-based Just-in-time Compilation for Haskell" by Thomas Schilling [1]. In it, he explains the details of implementing a basic VM and tracing JIT based on LuaJIT, and deals with a lot of the issues involved. For example, the choice of where to begin a trace and for how long to trace is crucial for performance. Traces that are too long will rarely complete, and selecting poorly and tracing something that won't actually be on the hot path has significant cost. With poor trace selection, a tracing JIT can even be slower than an optimized interpreter. Interestingly, the language itself also influences the viability of tracing: A language with explicit loop instructions is easier to trace since any loop instruction is an intuitive starting point, whereas a language which relies on recursion and TCO is less cooperative in this regard. One possibility is rewriting recursive constructions to imperative loops in a pass prior to trace selection. Personally, after reading the paper I think that there is the possibility for amazing performance from tracing JITs, but the unpredictability and reliance on heuristics makes the practical value over method JITs or static compilation questionable. It is similar to the complexities of GC implementation: As performance gains are made, complexity shoots through the roof while predictability suffers. There's no easy answer to that problem. [1]: http://src.acm.org/2013/ThomasSchilling.pdf http://src.acm.org/2013/ThomasSchilling.pdf

pron 11y ago
I had a short conversation at ECOOP with Ben Titzer (who works on V8 at Google, and I think used to work on HotSpot at Sun), who said simply: tracing JITs are good for short programs; for large programs you need a partial-evaluation method JIT. Partial evaluation also produces better results for a larger class of programs. Tracing JITs' advantages are that they're simpler to write than partial evaluation JITs, and produce decent code faster, which is why they're used for JavaScript. There is great progress in partial evaluation JITs going on in the Graal/Truffle project[1] (Graal is the compiler; Truffle is a framework to write language frontends for Graal), which will be available as a pluggable compiler for HotSpot in Java 9. Here are a couple of optimizations Graal yields for Ruby: https://twitter.com/ChrisGSeaton/status/619885182104043520 https://twitter.com/ChrisGSeaton/status/619885182104043520 [1]: https://wiki.openjdk.java.net/display/Graal/Publications+and+Presentations https://wiki.openjdk.java.net/display/Graal/Publications+and...

haberman 11y ago

I think the article is making out trace compilers to be far more limited than they actually are. > Consider these optimization tips: Avoid nested loops. I don't think this is true at all. The article is arguing that because a trace only contains one loop, that nested loops can't be trace-compiled. As I understand it, nested loops are totally possible to trace-compile by having multiple traces that link to each other. See what Mike Pall wrote about LuaJIT (http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-compiler-work,1 http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-...): "If the inner loop has a low iteration count, it'll be unrolled and inlined. For most loop nestings there'll be a single trace for the outer loop that goes 'around' the inner loop and joins its exit with its entry. Otherwise traces link to each other in linear pieces." I would take what this article says with a heavy grain of salt. I don't think that tracing JITs are at all like "programming in a straight jacket." Look at the LuaJIT performance optimization guide. There is nothing in there about avoiding nested loops, avoiding tiny loops, or avoiding loops with unpredictable iteration counts. It does however recommend reducing unpredictable branches: http://wiki.luajit.org/Numerical-Computing-Performance-Guide http://wiki.luajit.org/Numerical-Computing-Performance-Guide

mrottenkolber 11y ago
> I think the article is making out trace compilers to be far more limited than they actually are. Luke (the posts' author) and others are building a high performance software Ethernet switch[1] using LuaJIT. Let me assure you that these considerations actually come from experience rather than speculation. > As I understand it, nested loops are totally possible to trace-compile by having multiple traces that link to each other. Sometimes it works, sometimes it doesn't. We can't really expect everybody using Snabb Switch to understand the internals of LuaJIT so restrictive guidelines are useful for us. Disclaimer: Consulting for Snabb GmbH [1]: https://github.com/snabbco/snabbswitchhttps://github.com/snabbco/snabbswitch https://github.com/snabbco/snabbswitchhttps://github.com/sna...
- haberman 11y ago
  > Let me assure you that these considerations actually come from experience rather than speculation. Good to know. The article did not make this clear.

talles 11y ago

First time I see someone blogging with GitHub issues and, surprisingly, looks like it works well. Markdown, tags, comments plus a index (README.md) if you need one.

qznc 11y ago
Also "follow" and "kudos", named "watch" and "star". Getting a feed of the blog requires filtering, though.
deleted 11y ago
[deleted]

TheLoneWolfling 11y ago

Two semi-tangential ideas: I wish it was possible to do things along the lines of "fetch this data from RAM and at the same time start recomputing it, whichever is faster". And also, I wish there was a "branch upcoming / branch execute" split. In other words, instead of just "here's a branch", it's more along the lines of "you will have to branch on <x>. <other instructions> now branch on <x>." Effectively a variable number of branch-delay slot(s). Wouldn't help for straight pointer-chasing, but in other situations it could.