I too keep hearing this repeated but without empirical support. Same goes for the idea that garbage collection can be faster than manually managed memory.
In practice, PGO has been the best possible compilation regime that I have ever found.
In practice, PGO has been the best possible compilation regime that I have ever found.
It's really workload dependent and depend a lot of the GC involved (a pretty dumb one like Python's or Go's won't get you anything performance wise), but a copying collector can achieve allocation way faster than a regular heap allocator (the allocation can be almost as cheap as allocating on the stack). If you can't avoid boxing and your objects aren't all long-lived, you can run circles around a program not using such a GC.
I get that it is theoretically possible for GC to be faster, but I literally have never seen it pan out in practice.
And whichever way you look at it, the GC doesn't really have to outperform manual memory management to be extremely useful. It just has to be close enough, the correctness guarantees alone make it worth it as long as the performance difference is not too large, in many domains, not to mention the productivity boost and program readability.
I agree with all of this. But it is a very different argument than the theoretical argument that garbage collection can be faster than manual memory management.
Rust, for example, is manually managed or compiler managed, depending on how you look at it. But its semantics are extremely crude and naive: allocate on creation, free once an object leaves its current scope. There is no optimization of heap fragmentation, there is no optimization of large bulk frees...the compiler literally just inserts the malloc/free statements for you in a static location that you don't get to choose.
And despite the crudeness of its memory allocation behavior, it runs circles around garbage collected languages all day long. Even fast ones...I have done more than a handful of comparisons between Scala, Java, Go, SML (MLTon), OCaml, F#, and Rust...and Rust always comes out on top. That doesn't mean the performance advantages are worth the extra pain of dealing with a borrow checker...for most of my code, I default to Scala for all the reasons you've mentioned. But I don't delude myself into thinking it is faster.
Most likely if you compare a Rust and Java program that both run a loop creating a million node linked list and then starting over, you'll see that the Java program is much faster. I'll actually try to do that and confirm, but I believe it should be the case.
Even if you were to allocate arrays (Vec) you may see the same.
But, of course, that is not a fair comparison. Rust gives you tools to avoid allocation in the first place. It also optimizes so many things that Java doesn't. Summing up all of the values in an ArrayList<Integer> in Java is going to be so much slower than doing the same in Rust it's not even funny. I'm not even sure that Java implements vectorization yet.
It would be very interesting to see what performance a Rust program would get with a good, concurrent parallel generational copying collector. Perhaps in a few years there will be some interest in that.
As a more concrete example splitting strings by copying in Rust and hammering malloc and memcpy is 4-5x slower than using slices in Go and letting the GC deal with keeping things alive.
You might say that's not a fair comparison but few businesses can tolerate the messing around that is writing zero copy Rust.
malloc implementations actually do optimize by delaying the work of free(1). They do a lot of complex stuff hidden behind those function calls to improve performance.
Most generational gc's don't call free (the ones in Java can, but not per object, the reason for doing it is for returning memory to the OS). The GC will scan every _living_ object, but only those it is interested in. So if the decision to be made is which newly allocated objects should be copied over to the old gen, the gc will avoid scanning objects known to already be old.
The sentence you wrote made it seem like it scans the entire heap and decides which object should be kept, which should be copied and which should be free'd, but this is far from the case.
Since allocation with a GC is usually much cheaper than in non-GC systems (bump allocator) and since free is rarely, if ever, called, you can in theory get better performance from a GC than in a system with manual memory management. Of course, it all depends on the system.
The systems I write (mostly CRUD web apps) benefit from it, because requests to my service allocate little and run pretty fast, they're unlikely to survive to the next GC, and so I mostly pay for bump-allocation (which is cheap).
However, while the performance might be better my systems are prone to unexpected pauses while the GC does run. That pause might be less than the time spent in free in a manual memory managed system, but of course saving up all that time and spending it in one place does make it more noticable.
Thankfully, Java's G1 and collectors have managed to reduce these pauses so they're no longer noticable for my use. Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service.
> Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service.
Note that a pause for calling a web service is different than a GC pause, because in the former you can do other useful things while you wait.
CPython has a specialized arena allocator for small allocations called obmalloc.
Go's allocator is descended from tcmalloc but faster because it doesn't need to support the free(1) api and all the book-keeping required.
It's like comparing speed of a bike vs airplane: the brand and the quality of the bike doesn't really matter…
Freelist based allocation is actually very nearly as fast as bump pointer allocation. Like 10% if you compare the allocation function in isolation and 1% if you benchmark the whole object allocation path.
http://users.cecs.anu.edu.au/~steveb/pubs/papers/mmtk-sigmet...
Some older malloc implementations like Hoard have bump pointer allocation into empty pages but the newest allocator impementations found that the branch prediction cost of having both paths outweighed the benefits
https://www.microsoft.com/en-us/research/uploads/prod/2019/0...
- first, as you said, people repeat the opposite a lot, including world class GC experts.
- then, unless I'm missing something, that claim sounds equivalent to claiming than heap allocation is no more than 10% more expensive than stack allocation, which is arguably completely false.