When can garbage collection be faster than manual memory management? [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 11 years ago.

Under what circumstances is garbage collection more efficient than manual memory management? (Here manual could mean using malloc and free as in C, or the cleaner RAII and smart pointer techniques popularized by C++)

I like how garbage collection can remove some accidental complexity from writing software, but I was even more开发者_开发技巧 pleased at how RAII and smart pointers can eliminate that complexity while also working on resources other than memory, being deterministic, and providing performance guarantees and being more efficient overall. So I thought I could safely ignore garbage collection. However, I've noticed that people have been saying that garbage collection is faster than the tight resource management used in C++, such as when there is a lot of extra memory available.

So when exactly can garbage collection outperform manual memory management? I like RAII and smart pointers but would happy to accept garbage collection as another tool if it is faster.

---

GC advantages:

• a GC allocates simply by incrementing a pointer, heap allocators must take counter-measures to avoid heap fragmentation
• a GC improves cpu cache locality, a big deal on modern processors
• a GC requires no extra code to release memory, low odds for leaks
• a generational GG can collect garbage concurrently, making memory management close to free on a multi-core cpu.

GC disadvantages:

• difficult to make efficient in a language that treats pointers as first class types
• uses more virtual memory space due to collection latency
• leaky abstraction for operating system resources other than memory
• can cause pauses in program operation in some cases while garbage is being collected.

It is a slamdunk for perf, a GC beats a heap allocator easily without effort. The Chinese Dictionary programming contest between Rico Mariani and Raymond Chen is often quoted, overview is here. Raymond's C++ program eventually won but only after rewriting it several times and giving up on the standard C++ library.

---

Never, and I can prove it.

First, let's assume we're using the best algorithms in either case. Using a sub-optimal algorithm can prove anything.

Secondly, let's assume the best GC algorithm uses times T0...Tn to decide whether memory allocation i should be freed at a certain moment. The total then is Σ(Ti)

Now, an equivalent manual memory management algorithm exists that uses the same GC algorithm, but only considers memory blocks which have been manually marked to be freed. Therefore, the running time is Σ(δiTi) (with δi=0 when block i wasn't freed, and =1 when it was).

Obviously, Σ(δiTi) ≤ Σ(Ti) : there's a manual algorithm that's strictly not worse than a GC algorithm.

How does that contrast with other answers?

• "With RAII, you have to deallocate every time you allocate." - No, that's a mistaken assumption. We should compare either batched or non-batched operations. GC would be far worse if you'd also do a GC run every time something went out of scope.
• "Improved locality" - well, unless you discount the fact that non-GC languages can use the stack far more often, and that stack has an excellent locality of reference.
• "low odds for leaks" - that's entirely true, but we were discussing runtime performance. (BTW: good to point out that it's low but non-zero odds).

---

There's one particular scenario I know in which GC pointer is much faster than a smart pointer (reference counted pointer) when both are implemented in traditional C++ (i.e. not C++/CLR as we won't have the same luxury as to Compact the memory after Mark-Sweep, and we're trying to compare apples to apples here as much as we can) assuming GC uses the same underlying heap memory manager. It is when your object assignment time significantly overwhelms object creation time.

Examples include sorting, array reversal etc.

See here for more info on my test with a GC framework I implemented using traditional C++ vs reference counted pointers. Outcome of the array reversal test was GcString was 16.5 times faster than ref counted String.

This could be attributed to the painfully slow bus lock semantics in a reference counted pointer (unless you're targeting purely single threaded apps, locks are required for thread safety). From my experience of implementing a high performance precise GC in traditional C++, I can say that there are more opportunities for optimizations with a GC vs 'manual' (as per OP's definition of manual) memory management (i.e. smart pointers).