r/programming • • Jul 05 '15

Fast as C: How to write really terrible Java

https://vimeo.com/131394615
1.1k Upvotes

394 comments sorted by

View all comments

Show parent comments

20

u/headius Jul 05 '15

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.

0

u/[deleted] Jul 06 '15

[deleted]

6

u/serviscope_minor Jul 06 '15

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.

1

u/ants_a Jul 07 '15

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.

2

u/hu6Bi5To Jul 06 '15

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.

1

u/defenastrator Jul 06 '15

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

2

u/snailbot Jul 06 '15

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.

1

u/oracleoftroy Jul 07 '15

You only have to walk all live nodes

... and all the dead nodes with finalizers, and then possibly a second walk through if they resurrect themselves.

Does Java have a GC.SuppressFinalize() equivalent yet?

1

u/mmtrebuchet Jul 05 '15

Thanks for mentioning this. I'd like to learn more about cache-friendly code, do you have any references you could suggest?

3

u/mike_hearn Jul 05 '15

This might help

http://web.cecs.pdx.edu/~jrb/cs201/lectures/cache.friendly.code.pdf

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.