7 ms·

Can JIT be Faster?

89 points by aespinoza 15y ago

fleitz 15y ago
Yes and No. If you bundle JIT with garbage collection, bounds checking, and all the usual things that come with the JVM/CLR and execute on current hardware, probably not. If you were to JIT a language like C it would probably be faster as you could optimize to specific hardware. OpenCL uses JIT for example and it's many times faster than static compilation (because it can take advantage of extra hardware at runtime). The issue to contend with is the reality that about 30 years of the industry have gone into making C fast, everything from compilers to the way CPUs are designed. There's likely no inherent reason any style of compilation / execution couldn't beat static compilation, it's just we need the same level of resources and hardware support for those execution models. For instance with garbage collection and bounds checking you no longer need an MMU.
- migueldeicaza 15y ago
  Right, that is the point that both Herb and myself agree on: current managed languages have chosen paths where fewer errors, safety and productivity are more important than raw performance. That said, although bounds checking eliminates some of the reasons for MMUs, it does not really solve many other features that we take for granted today that depend on MMUs, like on-demand-loading. Garbage collectors and VMs typically use the MMU to improve the performance of their own operations. You use the MMU to cause execution to stop, you use MMUs to setup redzones on the stack to avoid checking on every function entry point for how much space is left on the stack and VMs use the MMU to map their metadata into their address space without having to load them from file and provide the services on demand.
  - ArtB 15y ago
    > That said, although bounds checking eliminates some of the reasons for MMUs Microsoft had a research OS called Singularity that was written in C# mostly and could be run in real memory mode because they didn't need the barriers.
    - luriel 15y ago
      Inferno (developed pretty much by the same team that recently created Go at google, and before created Plan 9 and Unix) doesn't need a MMU either, this is a great advantage when running on hardware without an MMU (there is a pretty good port to the Nintendo DS), and also makes it easier to port to platforms with an MMU (a single guy ported it to the PS2 in his spare time), MMUs are one of the main sources of platform-specific complexity.
- Someone 15y ago
  Is that "If you were to JIT a language like C it would probably be faster" true? I think a JIT C compiler would run into trouble with alias detection. Let's say that it removes an if statement because the variable a in the "if(a)" that starts it always is false. In C, code like "x->y = 1;" could affect the value of a, as could _any_ pointer dereference. If the JIT cannot prove that that could happen, it would have to insert a check "does this modify a?" for every such statement. I think there will be quite a bit of code out there where even a very smart JIT would not be able to conclusively prove that such aliasing does not happen. Also, I do not accept that OpenCL argument. IMO, OpenCL is more similar to static compilation than to a JIT. It is as if you recompiled your kernels whenever you changed your video card (perhaps also when you change its configuration); it does not do things that a JIT would do, such as "hm, most of the pixels are black; let's optimize for that case".
  - DannyBee 15y ago
    We (compiler optimization folks) have gotten very good at making pointer and alias analysis fast, particular simple pointer analysis like you might find in JIT. For a JIT, you would likely write out conservative but correct static results in whatever the equivalent of "javac" is for your C jit, and then refine it in the JIT. You'd invalidate it if you saw accesses you can't account for come up later on. Even if you didn't want to do that, on demand CFL reachability formulations of pointer analysis can calculate reasonable pointer results for individual pointers fast enough if it became important. Realistically however, no JIT is going to do advanced pointer analysis, unless you have CPU to burn. As for "conclusively prove that aliasing does not happen", you don't actually have to, because if it is truly going to improve performance, you can insert runtime checks. if (&a == &b) <do super fast thing> else <slower fallback code>
  - tedunangst 15y ago
    If your C program has aliased pointers to different types, you are already running in undefined behavior land. The JIT is just as free to optimize away that test as the static compilers that optimize it away today.
- tedunangst 15y ago
  OpenCL is only vaguely JIT like in the common sense. If I recompiled Photoshop so each image transform were completely unrolled and optimized for the image's dimensions, that'd be a closer approximation. It's more like online static compilation. You could kind of get the same effect using libtcc. [Now I'm not sure if I'm agreeing or disagreeing with you. I can't quite articulate the difference between JIT and "online static compilation", but I feel there is one.]
rogerbinns 15y ago
One thing I would like to see is speculative execution. I have an 8 core machine. When the JIT compiler runs there is no reason why it can't generate 7 alternatives to any particular code sequence, run them all in parallel and keep whichever was the fastest. Or run both sides of an if statement simultaneously. This helps solve the problem that compiler writers often have multiple alternatives they can generate, but have to make hard decisions as to which to pick. I'm not saying that implementing this will be easy, but then again all of the easy things have already been done.
- wmf 15y ago
  Describing this as not easy is a bit of an understatement; there has been a lot of research into speculative threading and communication overhead between cores almost always kills it.
  - rogerbinns 15y ago
    The main hurdle is getting a block of execution large enough to make it worthwhile trying alternatives and absorbing the cost of setup and finish. I suspect some form of STM would help a lot since you could then run multiple threads of code and only "commit" the winner. That allows a larger execution block. I also think software people still have a innate fear of "wasting" CPU/memory/disk which is hard to overcome.
    - maxs 15y ago
      One example of where this is used in practice is the fftw library (fastest Fourier Transform in the west). At runtime you can run a trial of FFT algorithms for your data size and architecture, and it will pick the fastest.
      - rogerbinns 15y ago
        It is a pain with FFTW since they expose all this in the API, let you save/load the details etc. A better example is MongoDB. When you make a query they try multiple query plans concurrently, note which is fastest and use that in the future with continued performance monitoring. Once diverging from expectations they run the contest again. Compare with other databases that put an inordinate amount of effort and tuning into coming up with the one true query plan per query.
CurtHagenlocher 15y ago
One of the performance advantages of C is the sheer amount of detail that's left to the implementation. By contrast, languages like C# and Java are typically much more tightly specified, which prevents optimizations that are not provably correct. This is not a matter of JIT vs non-JIT.
- ubernostrum 15y ago
  The JVM is quite happy to speculatively apply optimizations that are not provably correct, and has done so for years. Have a look at the link in this comment: http://news.ycombinator.com/item?id=3799975 http://news.ycombinator.com/item?id=3799975
  - CurtHagenlocher 15y ago
    Sure, but if not provably correct then they need to be detectably incorrect. That's still a higher bar than a valid C implementation needs to pass.
ubernostrum 15y ago
Both Herb and Miguel seem to be writing on a flawed assumption, which is that JIT will only ever apply optimizations that can be proven safe. As I understand it, this is true for CLR implementations. And if that were the case generally, there would be no significant-enough difference between the set of optimizations available with AOT and the set of optimizations available with JIT, and JIT would never be "as fast as C". But this disregards one of the major selling points of profiling + optimizing JIT: you can apply optimizations that cannot be proven safe and you can get away with it. This means you can not only be "as fast as C", you can implement a JIT that will mop the floor with C. Good JITs are already taking advantage of this, and the very first comment on Miguel's article points this out. This (four-year-old!) article by Charles Nutter explains it a bit more in the context of the JVM: http://headius.blogspot.com/2008/05/power-of-jvm.html http://headius.blogspot.com/2008/05/power-of-jvm.html
- vilya 15y ago
  I keep on hearing that it's possible to write a JIT-based vm that's "faster than C". I have yet to actually see one where that is true for anything other than one or two very specific micro-benchmarks. Edit: the old C2 wiki actually has something useful to say about this. http://c2.com/cgi/wiki?AsFastAsCee http://c2.com/cgi/wiki?AsFastAsCee http://c2.com/cgi/wiki?SufficientlySmartVirtualMachine http://c2.com/cgi/wiki?SufficientlySmartVirtualMachine
  - DannyBee 15y ago
    It's actually not that difficult to find programs where a JIT is better. Things that benefit significantly from profile directed feedback often run faster in JIT than static compilers, because JIT's tend to do this dynamically, whereas static compilers require training runs. For example performance critical code that has a lot of conditional branches, but only a few are taken at runtime, will often work faster in a JIT. (Of course, the typical solution is not to write performance critical code with a large number of branches, i'm just giving you examples)
    - vilya 15y ago
DannyBee 15y ago
The very first comment misunderstands reality. It talks about how you can make java programs that outrun C++ ones using hotspot. Ignoring, of course, the fact that nothing really stops you from making a good C++ JIT except engineering time, and it would do just as well in those cases. Nobody does it because the cases in which it would help are small, and most of those folks are willing to do profiling/training runs, and get about as good results, even if it requires more pain. As Herb said, the languages were made for different tradeoffs. Speaking as a compiler guy, yes, you can make almost any of them as fast as each other given enough time and effort. But putting time and effort into a JIT may not be as effective as choosing a different language.
- barrkel 15y ago
  If you redefine C++ so that it looks like Java / C# (i.e. runs on a virtual machine, with a JIT and probably some requirements for memory safety), then yes, you can do these things with C++. But the people who advocate C++ wouldn't recognize that language as a C++, because all the overhead of a JIT runtime violates the "only pay for what you need" dictum. (E.g. consider the uptake of Managed C++, C++/CLI, etc.; which effectively are what you describe.)
  - DannyBee 15y ago
    I think you may be confused. You don't have to redefine anything at a language level to make this work. It will just work. The features Java redefined were mainly for security reasons, and pointer safety, not because it made it possible to run with a JIT As a proof, you can JIT C/C++ with LLVM right now if you wanted to. It's not a great JIT because it has no adaptive compilation heuristics, etc, but it works just fine. C/C++ very specifically leave most of the execution environment undefined. They do not require anything that makes JIT'ing require language level changes. Your JIT may be unsafe (IE crash as easily as a regular C/C++ program), or otherwise require basically native access (IE not really viable for sandboxing in a browser), but it would work fine Things like Managed C++/etc required language changes because they wanted it to interoperate with a common intermediate language and runtime. There are things that you can do in C++ that you can't do in CLR (again, because the CLR chose safety/etc over other considerations), and vice versa (IE garbage collection at a language level), so managed C++ required language changes to support this.
SeanLuke 15y ago
> Java HotSpot takes a fascinating approach: they do a quick compilation on the first pass, but if the VM detects that a piece of code is being used a lot, the VM recompiles the code with all the optimization turned on and then they hot-swap the code. Wait, what? Hotspot does a "quick compile" on the first pass? When did this happen?
- lucian1900 15y ago
  Some time ago. It has a "pasting" JIT for as a first optimisation stage, which just pastes together machine code for each opcode, to remove the overhead of interpreting. Note that it does just interpret by default.
  - SeanLuke 15y ago
    > It has a "pasting" JIT for as a first optimisation stage Could you point to somewhere on the interweb which discusses this in detail?
yxhuvud 15y ago
Sigh. Why the hell do people use the Candara font? Do they want people to have a hard time reading what they write?
- ukreator 15y ago
  There's no accounting for taste. This font looks good for me.
  - yxhuvud 15y ago
    It looks nice to me too, if I press ctrl-+ twice. Maybe it is just that the font doesn't scale well enough for high resolutions.

89 points by aespinoza 15y ago

Yes and No. If you bundle JIT with garbage collection, bounds checking, and all the usual things that come with the JVM/CLR and execute on current hardware, probably not. If you were to JIT a language like C it would probably be faster as you could optimize to specific hardware. OpenCL uses JIT for example and it's many times faster than static compilation (because it can take advantage of extra hardware at runtime). The issue to contend with is the reality that about 30 years of the industry have gone into making C fast, everything from compilers to the way CPUs are designed. There's likely no inherent reason any style of compilation / execution couldn't beat static compilation, it's just we need the same level of resources and hardware support for those execution models. For instance with garbage collection and bounds checking you no longer need an MMU.

migueldeicaza 15y ago
Right, that is the point that both Herb and myself agree on: current managed languages have chosen paths where fewer errors, safety and productivity are more important than raw performance. That said, although bounds checking eliminates some of the reasons for MMUs, it does not really solve many other features that we take for granted today that depend on MMUs, like on-demand-loading. Garbage collectors and VMs typically use the MMU to improve the performance of their own operations. You use the MMU to cause execution to stop, you use MMUs to setup redzones on the stack to avoid checking on every function entry point for how much space is left on the stack and VMs use the MMU to map their metadata into their address space without having to load them from file and provide the services on demand.
- ArtB 15y ago
  > That said, although bounds checking eliminates some of the reasons for MMUs Microsoft had a research OS called Singularity that was written in C# mostly and could be run in real memory mode because they didn't need the barriers.
  - luriel 15y ago
    Inferno (developed pretty much by the same team that recently created Go at google, and before created Plan 9 and Unix) doesn't need a MMU either, this is a great advantage when running on hardware without an MMU (there is a pretty good port to the Nintendo DS), and also makes it easier to port to platforms with an MMU (a single guy ported it to the PS2 in his spare time), MMUs are one of the main sources of platform-specific complexity.
Someone 15y ago
Is that "If you were to JIT a language like C it would probably be faster" true? I think a JIT C compiler would run into trouble with alias detection. Let's say that it removes an if statement because the variable a in the "if(a)" that starts it always is false. In C, code like "x->y = 1;" could affect the value of a, as could _any_ pointer dereference. If the JIT cannot prove that that could happen, it would have to insert a check "does this modify a?" for every such statement. I think there will be quite a bit of code out there where even a very smart JIT would not be able to conclusively prove that such aliasing does not happen. Also, I do not accept that OpenCL argument. IMO, OpenCL is more similar to static compilation than to a JIT. It is as if you recompiled your kernels whenever you changed your video card (perhaps also when you change its configuration); it does not do things that a JIT would do, such as "hm, most of the pixels are black; let's optimize for that case".
- DannyBee 15y ago
  We (compiler optimization folks) have gotten very good at making pointer and alias analysis fast, particular simple pointer analysis like you might find in JIT. For a JIT, you would likely write out conservative but correct static results in whatever the equivalent of "javac" is for your C jit, and then refine it in the JIT. You'd invalidate it if you saw accesses you can't account for come up later on. Even if you didn't want to do that, on demand CFL reachability formulations of pointer analysis can calculate reasonable pointer results for individual pointers fast enough if it became important. Realistically however, no JIT is going to do advanced pointer analysis, unless you have CPU to burn. As for "conclusively prove that aliasing does not happen", you don't actually have to, because if it is truly going to improve performance, you can insert runtime checks. if (&a == &b) <do super fast thing> else <slower fallback code>
- tedunangst 15y ago
  If your C program has aliased pointers to different types, you are already running in undefined behavior land. The JIT is just as free to optimize away that test as the static compilers that optimize it away today.
tedunangst 15y ago
OpenCL is only vaguely JIT like in the common sense. If I recompiled Photoshop so each image transform were completely unrolled and optimized for the image's dimensions, that'd be a closer approximation. It's more like online static compilation. You could kind of get the same effect using libtcc. [Now I'm not sure if I'm agreeing or disagreeing with you. I can't quite articulate the difference between JIT and "online static compilation", but I feel there is one.]

rogerbinns 15y ago

One thing I would like to see is speculative execution. I have an 8 core machine. When the JIT compiler runs there is no reason why it can't generate 7 alternatives to any particular code sequence, run them all in parallel and keep whichever was the fastest. Or run both sides of an if statement simultaneously. This helps solve the problem that compiler writers often have multiple alternatives they can generate, but have to make hard decisions as to which to pick. I'm not saying that implementing this will be easy, but then again all of the easy things have already been done.

wmf 15y ago
Describing this as not easy is a bit of an understatement; there has been a lot of research into speculative threading and communication overhead between cores almost always kills it.
- rogerbinns 15y ago
  The main hurdle is getting a block of execution large enough to make it worthwhile trying alternatives and absorbing the cost of setup and finish. I suspect some form of STM would help a lot since you could then run multiple threads of code and only "commit" the winner. That allows a larger execution block. I also think software people still have a innate fear of "wasting" CPU/memory/disk which is hard to overcome.
  - maxs 15y ago
    One example of where this is used in practice is the fftw library (fastest Fourier Transform in the west). At runtime you can run a trial of FFT algorithms for your data size and architecture, and it will pick the fastest.
    - rogerbinns 15y ago
      It is a pain with FFTW since they expose all this in the API, let you save/load the details etc. A better example is MongoDB. When you make a query they try multiple query plans concurrently, note which is fastest and use that in the future with continued performance monitoring. Once diverging from expectations they run the contest again. Compare with other databases that put an inordinate amount of effort and tuning into coming up with the one true query plan per query.

CurtHagenlocher 15y ago

One of the performance advantages of C is the sheer amount of detail that's left to the implementation. By contrast, languages like C# and Java are typically much more tightly specified, which prevents optimizations that are not provably correct. This is not a matter of JIT vs non-JIT.

ubernostrum 15y ago
The JVM is quite happy to speculatively apply optimizations that are not provably correct, and has done so for years. Have a look at the link in this comment: http://news.ycombinator.com/item?id=3799975 http://news.ycombinator.com/item?id=3799975
- CurtHagenlocher 15y ago
  Sure, but if not provably correct then they need to be detectably incorrect. That's still a higher bar than a valid C implementation needs to pass.

ubernostrum 15y ago

Both Herb and Miguel seem to be writing on a flawed assumption, which is that JIT will only ever apply optimizations that can be proven safe. As I understand it, this is true for CLR implementations. And if that were the case generally, there would be no significant-enough difference between the set of optimizations available with AOT and the set of optimizations available with JIT, and JIT would never be "as fast as C". But this disregards one of the major selling points of profiling + optimizing JIT: you can apply optimizations that cannot be proven safe and you can get away with it. This means you can not only be "as fast as C", you can implement a JIT that will mop the floor with C. Good JITs are already taking advantage of this, and the very first comment on Miguel's article points this out. This (four-year-old!) article by Charles Nutter explains it a bit more in the context of the JVM: http://headius.blogspot.com/2008/05/power-of-jvm.html http://headius.blogspot.com/2008/05/power-of-jvm.html

vilya 15y ago
I keep on hearing that it's possible to write a JIT-based vm that's "faster than C". I have yet to actually see one where that is true for anything other than one or two very specific micro-benchmarks. Edit: the old C2 wiki actually has something useful to say about this. http://c2.com/cgi/wiki?AsFastAsCee http://c2.com/cgi/wiki?AsFastAsCee http://c2.com/cgi/wiki?SufficientlySmartVirtualMachine http://c2.com/cgi/wiki?SufficientlySmartVirtualMachine
- DannyBee 15y ago
  It's actually not that difficult to find programs where a JIT is better. Things that benefit significantly from profile directed feedback often run faster in JIT than static compilers, because JIT's tend to do this dynamically, whereas static compilers require training runs. For example performance critical code that has a lot of conditional branches, but only a few are taken at runtime, will often work faster in a JIT. (Of course, the typical solution is not to write performance critical code with a large number of branches, i'm just giving you examples)
  - vilya 15y ago

DannyBee 15y ago

The very first comment misunderstands reality. It talks about how you can make java programs that outrun C++ ones using hotspot. Ignoring, of course, the fact that nothing really stops you from making a good C++ JIT except engineering time, and it would do just as well in those cases. Nobody does it because the cases in which it would help are small, and most of those folks are willing to do profiling/training runs, and get about as good results, even if it requires more pain. As Herb said, the languages were made for different tradeoffs. Speaking as a compiler guy, yes, you can make almost any of them as fast as each other given enough time and effort. But putting time and effort into a JIT may not be as effective as choosing a different language.

barrkel 15y ago
If you redefine C++ so that it looks like Java / C# (i.e. runs on a virtual machine, with a JIT and probably some requirements for memory safety), then yes, you can do these things with C++. But the people who advocate C++ wouldn't recognize that language as a C++, because all the overhead of a JIT runtime violates the "only pay for what you need" dictum. (E.g. consider the uptake of Managed C++, C++/CLI, etc.; which effectively are what you describe.)
- DannyBee 15y ago
  I think you may be confused. You don't have to redefine anything at a language level to make this work. It will just work. The features Java redefined were mainly for security reasons, and pointer safety, not because it made it possible to run with a JIT As a proof, you can JIT C/C++ with LLVM right now if you wanted to. It's not a great JIT because it has no adaptive compilation heuristics, etc, but it works just fine. C/C++ very specifically leave most of the execution environment undefined. They do not require anything that makes JIT'ing require language level changes. Your JIT may be unsafe (IE crash as easily as a regular C/C++ program), or otherwise require basically native access (IE not really viable for sandboxing in a browser), but it would work fine Things like Managed C++/etc required language changes because they wanted it to interoperate with a common intermediate language and runtime. There are things that you can do in C++ that you can't do in CLR (again, because the CLR chose safety/etc over other considerations), and vice versa (IE garbage collection at a language level), so managed C++ required language changes to support this.

SeanLuke 15y ago

> Java HotSpot takes a fascinating approach: they do a quick compilation on the first pass, but if the VM detects that a piece of code is being used a lot, the VM recompiles the code with all the optimization turned on and then they hot-swap the code. Wait, what? Hotspot does a "quick compile" on the first pass? When did this happen?

lucian1900 15y ago
Some time ago. It has a "pasting" JIT for as a first optimisation stage, which just pastes together machine code for each opcode, to remove the overhead of interpreting. Note that it does just interpret by default.
- SeanLuke 15y ago
  > It has a "pasting" JIT for as a first optimisation stage Could you point to somewhere on the interweb which discusses this in detail?

yxhuvud 15y ago

Sigh. Why the hell do people use the Candara font? Do they want people to have a hard time reading what they write?

ukreator 15y ago
There's no accounting for taste. This font looks good for me.
- yxhuvud 15y ago
  It looks nice to me too, if I press ctrl-+ twice. Maybe it is just that the font doesn't scale well enough for high resolutions.