One take away point from this for non-c coders is that higher level languages will always be significantly slower than C because it's far easier to make these kinds of fiddly pipeline optimizations when you don't have another abstraction layer in between mucking things up. There's few java programmers for instance that both intuitevly understand how both the machine architecture, and the JVM compiler will affect the code they write. There's too many quirks. While in theory it's possible to write comparably fast java code(assuming your willing to do sketchy things for memory manipulation related tasks). In practice it's significantly more difficult to get all the juice out with higher level languages.
The counter argument is that if you've compiled into a semantic description (bytecodes for a virtual machine) then the underlying VM implementation can optimize a semantically correct pipeline based on features available to it. Thus programmer time is saved (they wrote their code once) at the expense of a higher burden on the VM to do the right thing.
This argument (that the VM new best) was put forward by Bill Joy early on in the development of Java as the reason Java would eventually be faster than compiled C code. We discovered that in practice 'friction' [1] between hot spot compilation and instruction set architectures nearly always dominated this equation (leaving Java code slower).
Architectures where the friction was reduced (like the Jazelle instruction set on ARM) could swing the balance the other way.
[1] Friction in this case is the cost to performance of the difference of expressibility between a byte coded instruction and the actual processor architecture.
What the JVM compiler does to your code isn't really that much harder to understand than what GCC or LLVM does to your code. Assuming equally skilled programmers, I think it's often easier to write fast code in a higher level language. The primary bottleneck for performance is usually developer time. If you can get the non-performance critical parts written in half the time, you have way more time to optimize. Higher level languages also generally have much better profiling and introspection tools, which make debugging much easier. Debugging tightly optimized code is, of course, one of the big time sucks in optimizing code.
This is not correct: there are things that can be faster than C because of the compilation aspect (the compiler can only optimize with the information it has, some of them can only be known at runtime).
A good example is iteration over non trivial, multi-dimensional structures: if you iterate over a single dimension, then some variables become actual constant, but this can only be known once you know the iterator parameters (i.e. even profile-guided optimization would not work).
You could obviously implement a runtime-based optimizer in C, but then the assertion that you can never beat C is a tautology.
On the other hand, sometime in higher level languages the compiler could prove more constrains and then apply more aggressive optimizations. (I don't remember a specific case now, perhaps we still need a few years for an interesting example.)
Another possibility is that using a higher level language it is possible to write more complicated code, with smarter optimizations, because the programmer doesn't have to take care of all the details. For example, the Pypy project they has a Phyton interpreter written in a combination of RPhyton an C that is faster than the standard Phyton interpreter that is written directly in C.
Fortran defaults to strict aliasing and C defaults to loose aliasing, leading to naive Fortran programs sometimes being optimized better than equivalent naive C programs. Or as some people say, "Fortran is faster than C".
Another lesson from Fortran is to include arrays as a native type in your language. Intel continues to push their Fortran compiler whenever you shop for their numeric C libraries with some convincing benchmarks. https://speakerdeck.com/u/multicoreworld/p/james-reinders-in...
Indeed, a JIT compiler will always be able to take advantage of something that isn't possible for something that is compiled once and set in stone.
However, that's not to say that upfront compilation is doomed never to compete.
Profiling C compilers can mimic this behaviour to an extent, although they can only profile for the situtations they experience during their training phase so they can't adapt to unforeseen scenarios or dramatic shifts in the input stream.
C compilers could be extended to implement several/many variants of each function based on different possible code paths and, using information gained from on the fly timings it could switch between different variants in order to optimise execution. Combinatorics would place a low limit on the number of percentage of possible variants implemented though.
Finally, no-one ever said that C has to be a compiled language. There's nothing stopping someone writing a JIT C interpreter and getting the best of both worlds. (Ugh!)
True, I should have been clearer that I meant only C under the mainstream implementation style. If you get creative there are so many wonderful options. I know there's already TCC and a variety of REPLs.
Both the C compiler and the JVM JIT target machine code. I don't buy that one is automatically & universally superior to the other. You can equally argue that the JIT will always be superior because it's run-time aware.
Yes, it's always possible to write assembly code that is at least as fast as C code, if not faster.
But it's entirely another question whether you, as a mere mortal human, are able to do a better job at producing assembly code in practice, for non-trivial programs, than a compiler.
It's pretty much demonstrated by the update to the piece -- certain compliers & compiler flags did produce the right optimization, whereas the original author did not.
What kind of benchmarks? The benchmarks C folks always want to use are the ones that favor static compilation (matrix multiplication, etc). The best any language can do in that situation is tie--it's basically just an exercise of how much money has gone into the compiler's low-level optimizer.
Consider a benchmark implementing a common situation in real programs--a performance intensive loop calling some code located in a plugin that isn't known until runtime. The JVM will wipe the floor with a C compiler in that situation--since the JVM can do inlining at runtime between module boundaries, while a C compiler cannot do inlining at runtime at all.
Or, when memory management is involved, they always want to test situations where everything can be easily pool-allocated, instead of complex situations involving lots of dynamic allocation. But in situations where code is really allocating lots of short-lived objects (e.g. functional code for optimizing compiler trees), the GC in a JVM is going to wipe the floor with any malloc() implementation.
But, in "real programs", all this doesn't usually matter b/c clever JIT tricks with loops and branches fail to offset 5-10x the memory use and the abysmal corresponding CPU cache hit rate.
5-10x the memory use? Only if coders smoked something. I agree that JITed runtime has some overhead, but in a great majority of cases it is far below what you write here.
I think the best benchmark for this is to look at the industries where performance matters and see what they are using. Take high-frequency trading where lowest latency makes the most money. I don't see many using the JVM. AFAIK it's all assembly, C and C++. If they could use the JVM and have faster code, they would be doing so.
But in situations where code is really allocating lots of short-lived objects (e.g. functional code for optimizing compiler trees), the GC in a JVM is going to wipe the floor with any malloc() implementation.
Arena allocation is feasible only for particular types of allocation patterns. If that weren't true, every malloc() implementation would just be based on an arena allocator.
Specifically, for arena allocation to work, you have to have points at which you know all objects in an arena will become garbage. There are many situations where you know that most objects will quickly become garbage (say 98%), but can only guarantee at a very large scope that all objects will become garbage.
Consider something like a compiler that optimizes a tree by replacing sets of nodes with simpler ones. Where do you put the pool delete operation? You know lots of nodes will become garbage after each optimization pass, but you know some will survive. But you can't statically segregate which ones. So you can put the pool delete at the very end after code generation, when you know you don't need the tree anymore. But then your memory use skyrockets--you don't reclaim any memory until the very end of the process.
GCC, for example, used to use a pool allocation functionality called obstack's. They ended up switching to a home-rolled GC because it became too hard to manage that system.
This gets into a can of worms, because while much of the performance benefit of an arena is the fact that you don't need to do per-object bookkeeping, the other benefit is that it's fast to allocate, track, and free data when you know all the sizes in advance, and that is a benefit you can get from a pool allocator, which isn't much more complicated than an arena.
The general purpose malloc(3) has a very hard problem to solve that most allocations in most programs probably don't really need it to work so hard to solve.
Lower level languages like C can include ASM code with little overhead, they can also swap code around at run time just like the JIT. Granted, the vast majority of CRUD code has no need for such capability's, but as JVM languages have more constraints and absolutely no new capability's when it comes to the ASM they produce they fall behind when performance is most critical.
That said, the vast majority of programmers are never get any where near these limits.
If you need to super-optimize execution you can build C or ASM code and call it via a library or inline it into your high-level language. Java can call functions in shared libraries (or use JNI) and Perl can inline straight C or ASM.
I'm not sure why you'd want to get "all the juice" out of higher level languages, though. I thought the whole point was to abstract away from machine optimization? For example, to learn to write more efficient Perl I picked up "Mastering Algorithms with Perl" and it had loads of helpful tips.
Yes, there are some critical algorithms which will be always be faster in C.
In practice it's significantly more difficult to optimize all your code based on deep knowledge of architectures, compilers, and even compiler versions than it is to just let a JIT compiler optimize at runtime.
On the other hand, using a higher lever language and ready-made code can mean than someone else has already implemented all those optimizations you would never implement yourself.
Comments
One take away point from this for non-c coders is that higher level languages will always be significantly slower than C because it's far easier to make these kinds of fiddly pipeline optimizations when you don't have another abstraction layer in between mucking things up. There's few java programmers for instance that both intuitevly understand how both the machine architecture, and the JVM compiler will affect the code they write. There's too many quirks. While in theory it's possible to write comparably fast java code(assuming your willing to do sketchy things for memory manipulation related tasks). In practice it's significantly more difficult to get all the juice out with higher level languages.
The counter argument is that if you've compiled into a semantic description (bytecodes for a virtual machine) then the underlying VM implementation can optimize a semantically correct pipeline based on features available to it. Thus programmer time is saved (they wrote their code once) at the expense of a higher burden on the VM to do the right thing.
This argument (that the VM new best) was put forward by Bill Joy early on in the development of Java as the reason Java would eventually be faster than compiled C code. We discovered that in practice 'friction' [1] between hot spot compilation and instruction set architectures nearly always dominated this equation (leaving Java code slower).
Architectures where the friction was reduced (like the Jazelle instruction set on ARM) could swing the balance the other way.
[1] Friction in this case is the cost to performance of the difference of expressibility between a byte coded instruction and the actual processor architecture.
What the JVM compiler does to your code isn't really that much harder to understand than what GCC or LLVM does to your code. Assuming equally skilled programmers, I think it's often easier to write fast code in a higher level language. The primary bottleneck for performance is usually developer time. If you can get the non-performance critical parts written in half the time, you have way more time to optimize. Higher level languages also generally have much better profiling and introspection tools, which make debugging much easier. Debugging tightly optimized code is, of course, one of the big time sucks in optimizing code.
This is not correct: there are things that can be faster than C because of the compilation aspect (the compiler can only optimize with the information it has, some of them can only be known at runtime).
A good example is iteration over non trivial, multi-dimensional structures: if you iterate over a single dimension, then some variables become actual constant, but this can only be known once you know the iterator parameters (i.e. even profile-guided optimization would not work).
You could obviously implement a runtime-based optimizer in C, but then the assertion that you can never beat C is a tautology.
On the other hand, sometime in higher level languages the compiler could prove more constrains and then apply more aggressive optimizations. (I don't remember a specific case now, perhaps we still need a few years for an interesting example.)
Another possibility is that using a higher level language it is possible to write more complicated code, with smarter optimizations, because the programmer doesn't have to take care of all the details. For example, the Pypy project they has a Phyton interpreter written in a combination of RPhyton an C that is faster than the standard Phyton interpreter that is written directly in C.
Fortran defaults to strict aliasing and C defaults to loose aliasing, leading to naive Fortran programs sometimes being optimized better than equivalent naive C programs. Or as some people say, "Fortran is faster than C".
Another lesson from Fortran is to include arrays as a native type in your language. Intel continues to push their Fortran compiler whenever you shop for their numeric C libraries with some convincing benchmarks. https://speakerdeck.com/u/multicoreworld/p/james-reinders-in...
You can carefully design an interpreter to mitigate these issues.
You can also have a JIT compiler remove branches altogether based on experimental data, something completely impossible in C.
Don't point at one thing and claim it makes a language class faster or slower.
Indeed, a JIT compiler will always be able to take advantage of something that isn't possible for something that is compiled once and set in stone.
However, that's not to say that upfront compilation is doomed never to compete.
Profiling C compilers can mimic this behaviour to an extent, although they can only profile for the situtations they experience during their training phase so they can't adapt to unforeseen scenarios or dramatic shifts in the input stream.
C compilers could be extended to implement several/many variants of each function based on different possible code paths and, using information gained from on the fly timings it could switch between different variants in order to optimise execution. Combinatorics would place a low limit on the number of percentage of possible variants implemented though.
Finally, no-one ever said that C has to be a compiled language. There's nothing stopping someone writing a JIT C interpreter and getting the best of both worlds. (Ugh!)
True, I should have been clearer that I meant only C under the mainstream implementation style. If you get creative there are so many wonderful options. I know there's already TCC and a variety of REPLs.
C++/CLI probably comes close to "C with JIT"
Isn't it possible to JIT C code with LLVM?
It's not impossible in C. It's impossible statically.
There is nothing that stops you from JIT'ing C/C++. LLVM includes a JIT that functions just fine on C/C++ programs.
And assembly would be faster again?
Both the C compiler and the JVM JIT target machine code. I don't buy that one is automatically & universally superior to the other. You can equally argue that the JIT will always be superior because it's run-time aware.
Yes, it's always possible to write assembly code that is at least as fast as C code, if not faster.
But it's entirely another question whether you, as a mere mortal human, are able to do a better job at producing assembly code in practice, for non-trivial programs, than a compiler.
Think we completely agree.
It's pretty much demonstrated by the update to the piece -- certain compliers & compiler flags did produce the right optimization, whereas the original author did not.
In the counterfactual world where the JVM's JIT commonly won bechmarks against C, that would be a great point.
What kind of benchmarks? The benchmarks C folks always want to use are the ones that favor static compilation (matrix multiplication, etc). The best any language can do in that situation is tie--it's basically just an exercise of how much money has gone into the compiler's low-level optimizer.
Consider a benchmark implementing a common situation in real programs--a performance intensive loop calling some code located in a plugin that isn't known until runtime. The JVM will wipe the floor with a C compiler in that situation--since the JVM can do inlining at runtime between module boundaries, while a C compiler cannot do inlining at runtime at all.
Or, when memory management is involved, they always want to test situations where everything can be easily pool-allocated, instead of complex situations involving lots of dynamic allocation. But in situations where code is really allocating lots of short-lived objects (e.g. functional code for optimizing compiler trees), the GC in a JVM is going to wipe the floor with any malloc() implementation.
But, in "real programs", all this doesn't usually matter b/c clever JIT tricks with loops and branches fail to offset 5-10x the memory use and the abysmal corresponding CPU cache hit rate.
See "branch misprediction" vs. "fetch from main memory" on norvig's rough timings list: http://norvig.com/21-days.html#answers .
5-10x the memory use? Only if coders smoked something. I agree that JITed runtime has some overhead, but in a great majority of cases it is far below what you write here.
I think the best benchmark for this is to look at the industries where performance matters and see what they are using. Take high-frequency trading where lowest latency makes the most money. I don't see many using the JVM. AFAIK it's all assembly, C and C++. If they could use the JVM and have faster code, they would be doing so.
But in situations where code is really allocating lots of short-lived objects (e.g. functional code for optimizing compiler trees), the GC in a JVM is going to wipe the floor with any malloc() implementation.
Even an arena allocator?
Arena allocation is feasible only for particular types of allocation patterns. If that weren't true, every malloc() implementation would just be based on an arena allocator.
Specifically, for arena allocation to work, you have to have points at which you know all objects in an arena will become garbage. There are many situations where you know that most objects will quickly become garbage (say 98%), but can only guarantee at a very large scope that all objects will become garbage.
Consider something like a compiler that optimizes a tree by replacing sets of nodes with simpler ones. Where do you put the pool delete operation? You know lots of nodes will become garbage after each optimization pass, but you know some will survive. But you can't statically segregate which ones. So you can put the pool delete at the very end after code generation, when you know you don't need the tree anymore. But then your memory use skyrockets--you don't reclaim any memory until the very end of the process.
GCC, for example, used to use a pool allocation functionality called obstack's. They ended up switching to a home-rolled GC because it became too hard to manage that system.
This gets into a can of worms, because while much of the performance benefit of an arena is the fact that you don't need to do per-object bookkeeping, the other benefit is that it's fast to allocate, track, and free data when you know all the sizes in advance, and that is a benefit you can get from a pool allocator, which isn't much more complicated than an arena.
The general purpose malloc(3) has a very hard problem to solve that most allocations in most programs probably don't really need it to work so hard to solve.
The benchmarks were JIT running time versus C compile time + runtime.
Not exactly apples to apples.
It's a question of degrees of freedom.
Lower level languages like C can include ASM code with little overhead, they can also swap code around at run time just like the JIT. Granted, the vast majority of CRUD code has no need for such capability's, but as JVM languages have more constraints and absolutely no new capability's when it comes to the ASM they produce they fall behind when performance is most critical.
That said, the vast majority of programmers are never get any where near these limits.
If you need to super-optimize execution you can build C or ASM code and call it via a library or inline it into your high-level language. Java can call functions in shared libraries (or use JNI) and Perl can inline straight C or ASM.
I'm not sure why you'd want to get "all the juice" out of higher level languages, though. I thought the whole point was to abstract away from machine optimization? For example, to learn to write more efficient Perl I picked up "Mastering Algorithms with Perl" and it had loads of helpful tips.
Yes, there are some critical algorithms which will be always be faster in C.
In practice it's significantly more difficult to optimize all your code based on deep knowledge of architectures, compilers, and even compiler versions than it is to just let a JIT compiler optimize at runtime.
On the other hand, using a higher lever language and ready-made code can mean than someone else has already implemented all those optimizations you would never implement yourself.
> higher level languages will always be significantly slower than C
Looking at benchmarks, I can see this is factually incorrect.
Also... show me where C allows you to see the pipeline directly. It's hard to optimize something you can't see.
C is an abstraction layer. So is assembly. Both are relatively thick when you're talking about things like branch prediction and pipelining.