That's changing the topic. The topic is not "Why do Java programmer seldom put in the effort to make Java run fast?" The topic is "How much effort is required to get Java to run as fast as C?"
It's a bit annoying to see "Java can run as fast as C! >:(" spread around the net at an almost meme-like level. The statement is technically correct only because it is incomplete. Java can run as fast as C for certain types of long-running programs where the JIT can eventually hyper-optimize certain code paths --as long as the GC work is low enough to not cancel out that benefit.
GC is a godsend. But, if performance is a requirement, GC becomes an impediment that must be manually worked-around even today. I recently read the great article Roslyn code base – performance lessons that opens with "Generally the performance gains within Roslyn come down to one thing: Ensuring the garbage collector does the least possible amount of work."
GC is rarely the actual problem...the problem is allocation.
Generally GC-based systems allocate memory using pointer-bumping; they allocate a big slab early in execution and then carve pieces off as needed. Unfortunately this means sequential allocations, whether transient or not, will quickly walk out of a cache segment into another segment. So in order to access that memory, you're forcing the CPU to constantly load from main memory.
In an equivalent C program, if you allocate and free memory in a tight loop, chances are you'll stay in the same cache segment and most of that allocation will never need to leave the CPU.
Platforms and languages that complain about GC being the bottleneck are either doing MASSIVE levels of GC, or they're running on a non-JVM platform that has a less-than-stellar GC.
Not in the slightest true. The reality is good best fit allocators in c run an average of 17 instructions per call.
Yes that's true, but I think it misses another point. C and C++ both also do stack allocation which runs in zero cycles. The memory is pre-allocated and simply accessed by indexing via the stack pointer.
The code I write often makes heavy use of local fixed sized objects such as fixed dimensionality vectors. The C++ stdlib now pretty much specifies that strings use this trick for the "short string optimization", too.
C and C++ also do things like arena allocation, can embed structs into each other and tend to reuse more buffers if not for else due to the fact that you need to keep track of them anyway to free them so you might as well reuse them. This is doubly true for C where you don't have the temptation to use higher level abstractions that obscure inefficiencies.
So not only is it possible to do more efficient memory management, it actually gets used due to the languages guiding the programmer in that direction, and also due to cultural reasons.
I may be misunderstanding one or even both of you, but aren't you and /u/headius talking about different things?
I got the impression he wasn't referring to specific allocators, more the happy coincidence that freeing and allocing the same size of memory in a tight-loop would mostly end-up using the exact slice of memory? Where-as a GC memory model would always provide you with "the next slice" of memory? Although having said that I'm still not sure why cache would be a factor in that case if it's freed at the end of the loop anyway.
This would only be a benefit in tight-loops called upon thousands of times, in other circumstances the memory allocations would be less predictable and other forces would be at work.
This is unlikely to yield the expected caching benefits as allocators tend to use first in first out structures to store their free chunks of the same size sans the trie node
You only have to walk all live nodes, and (with generational gc) the long-living ones are only walked when you're close to OOM. If your new generation is properly sized, most of the shortliving stuff is already dead and has no cost. Edit: most GCs are not compacting, and since c allocaters usually aren't either, compaction cost is not really relevant here.
JVMs can try to avoid the problem with GC allocation smearing the cache via something called scalar replacement. It moves the contents of an allocated object into what are effectively local variables on the stack (instead of the gcd heap). However it doesn't always kick in.
As a rule of thumb, the same algorithm written with a GC has comparable performance to the non-GC version when your available memory is ~6x larger than your working set.
if the cost of increasing memory continues to drop faster than the cost of increasing cpu performance, then we should soon expect GC implementations to be faster(*) than non-GC, if you have sufficient available RAM.
(*) Because JIT can perform on-the-fly data-specific optimizations, similar to offline profile-guided-optimization in non-GC languages.
IIRC, the paper you cite is considering allocation strategies for Java programs (and Java is designed with cheap dynamic allocation in mind and makes heavy use of them). It completely neglects the fact that in an actual non-GC language like C++ or Rust, you'd allocate most of your stuff on the stack, which would be incomparably faster.
Not sure what your point is... Any sufficiently advanced JIT GC language / or whole-program-optimization non-GC language can make those exact same transformations.
Care to try again? Perhaps using big-O notation this time? e.g. Lets try sorting an array with 100 million objects. Which is faster, GC or non-GC?
My rule of thumb says that the GC version is (probably) going to be faster if your working-set (100 million times size per object) is less than 1/6 times your available memory.
How did you jump from being able to catch up with 6x the resources to going faster? Your jit-optimization is somehow better than compiled optimization?
while i < len(myArray):
inplace_sort( myArray[ i : i + myStride] )
i += myStride
if myStride is 6, we can use a fixed sorting network
if myStride is moderate, we can inline the comparator function.
if myStride is large, we could run the sort in parrallel on different cores.
if myStride is very very large, we can copy the data to the GPU, sort it, then copy it back to main memory, quicker than we could on the CPU alone.
An AOT compiler has to make assumptions about myStride and choose which of those optimizations to make.
A JIT compiler can measure the input data, and optimize accordingly.
For example, if myStride happens to be 1, then the above code is a no-op.
Obviously that's an extreme example, but consider this: The input data your code will see in production is always going to be different from the training data you profile your AOT compiler against in your build environment. A JIT compiler doesn't have that restriction.
You're right, that's totally non-obvious, and doesn't at all follow from that paper.
Assume for a minute:
An algorithm operates on input data and produces output.
A compiler (necessarily) makes assumptions about that input data to produce machine code to compute that output.
A JIT doesn't need to make assumptions. It can measure the input data. It measures the properties of the input data, and it can then produce machine code based on that measurement. If the statistics of that input changes over time, it can produce new (optimal) code to better match the new input.
In this way, and only in this way, a JIT compiler (in theory) will outperform an AOT (ahead of time) compiler, if it can also beat the performance overhead of the GC.
In this way, and only in this way, a JIT compiler (in theory) will outperform an AOT (ahead of time) compiler, if it can also beat the performance overhead of the GC.
Where does PGO (profile guided optimization) fit into this theory? It seems like the best of both worlds in terms of run time performance, none of the overhead of a runtime JIT combined with real runtime feedback for the optimizer to analyze, plus a compiler can take more time than a JIT to produce optimal code. Obviously compile times suffer, but I don't see how a JIT could beat the runtime performance (unless the profile isn't a very good one).
PGO does help, sometimes by a few percent speedup. But it's still static, so you need to try and predict ahead of time what data you're likely to encounter when the code is deployed.
As an example, suppose you have a math heavy app, and in production you get a lot more NaN input than your profile training data.
Or suppose you trained your PGO on US-ASCII input, and instead end up processing unicode with lots of CJK characters.
Or you expected to perform FFTs on arrays with 8192 elements, and instead end up with FFTs over 8191 (prime) elements - totally different code path.
Or vice-versa.
Or any combination of these where the mix of input changes over time while the app is running.
Most of those concerns fall under my "unless the profile isn't a very good one" clause. Not to diminish that concern, it is a real one. You will need to improve the profile and recompile. JIT has the advantage of doing this extra step on the fly. It would be very interesting to see actual data about how bad or incomplete profiles change the performance of some task compared to good profiles and non-PGO code.
Or any combination of these where the mix of input changes over time while the app is running.
This seems like something just as likely to trip up JIT as well, maybe even more so. I can imagine a pattern of inputs that the JIT starts optimizing for, but then the pattern changes and the optimizations end up slowing down the program and the JIT starts compensating again. And then the inputs change again, etc. If the slowdown is significant, this might be something better handled by two different paths in the code. If minor, I'm curious whether the extra work the JIT ends up doing makes the task overall slower than the PGO version with an incomplete profile. There are probably too many variables to say definitively.
But your question is a little misleading, because if you look around at the JIT languages, almost all of them (Java, Javascript, lua, Python, Haskell, etc) also have a GC.
Actually, I'm having a hard time thinking of a JIT language which doesn't have a GC. Perhaps something like 'C' when it is running on the Microsoft CLR?
So yeah, a JIT doesn't require a GC, it just almost always seems to have one.
(I know it's bad form to reply to yourself, but...)
A corollary to this is, if your available ram is fixed (i.e. has an upper bound, e.g. on the xbox360) than a GC-implementation will always be slower than a non-GC implementation, because of Amdahl's law.
44
u/corysama Jul 05 '15
That's changing the topic. The topic is not "Why do Java programmer seldom put in the effort to make Java run fast?" The topic is "How much effort is required to get Java to run as fast as C?"
It's a bit annoying to see "Java can run as fast as C! >:(" spread around the net at an almost meme-like level. The statement is technically correct only because it is incomplete. Java can run as fast as C for certain types of long-running programs where the JIT can eventually hyper-optimize certain code paths --as long as the GC work is low enough to not cancel out that benefit.
GC is a godsend. But, if performance is a requirement, GC becomes an impediment that must be manually worked-around even today. I recently read the great article Roslyn code base – performance lessons that opens with "Generally the performance gains within Roslyn come down to one thing: Ensuring the garbage collector does the least possible amount of work."