Out of the 3 general garbage collector types - copying, mark & sweep, and reference count - copying is superior in general. The benefits of copying include: automatic compaction when copying from old heap to new heap (no memory fragmentation), improved locality (objects are closely packed), extremely fast reclamation (just throw away the old heap whereas mark & sweep needs to maintain/update the free list for different sizes of objects), great for systems with lots of objects dying young (mark & sweep needs to reclaim each died young object), cycle removal (ref count's pitfall), and generational GC is just an extension of the copying concept (in addition to copy from old heap to new heap, copy from younger generation to older generations).
And this is where the "it takes five times as much RAM to run a GC'd program with the same performance as the equivalent program with explicitly managed memory" bit kicks in.
Value semantics covers 95% of your object-lifetime needs. The other 5% can be covered with some form of reference counting and being smart about strong vs. weak references. Tracing GC is like bubble sort: almost always a suboptimal solution.
Not 5x as much ram. Exactly 2x more ram. You copy between two half spaces, back and forth. That's why it's usually also called semispace collector.
What you are talking in the 2nd paragraph is total nonsense in a lisp world. Lisp solved this problem decades ago, with copying collectors. Stack values are 20%, plus refcounts do not work with rplac* able trees and are super slow.
As it turns out, compared to the analysis and tree traversal inherent in even a fast GC algorithm, the overhead of malloc() and free() is really quite small. So yes, it takes twice as much memory to use a copying GC, right out of the starting gate -- but in order to match the performance of the equivalent explicitly managed program, it takes even more memory on top of that. And real time -- forget about it. It takes highly tuned, specialized algorithms to run a GC language that can meet hard real-time deadlines. You'll know you've found a decent algorithm because it will be proprietary -- part of some expensive, specialized JVM the Navy uses to crunch radar data aboard ship or something. The conventional algorithms (stop-and-copy, generational, etc.) are all fucking terrible.
And I wasn't talking about "in a Lisp world". Lisp is dead for real application development. Hell, the scruffies won, and C++ is now the predominant language in AI -- where Lisp was once said to thrive. Of course refcounts don't work if you try to build a graph with only one kind of reference. But a) you should know what kind of data structure you're building (cyclic or acyclic, graph or tree) and b) you should use weak references where possible to inform the deallocator which references not to chase. It's called being smart. Yes, it's a little more work than using a tracing GC, but it's still far less cognitively taxing or error-prone than using malloc() and free() manually.
I think you misread the 5x, 3x and 2x sentences there. These are the workloads benchmarked there. The more memory used the faster was a slow GC compared to malloc, equally fast with 5x more memory used, and with 2x memory 70% slower.
Any GC uses much less memory than a refcount or malloc application. That's common sense. Just copying uses more vmem during the copying, compaction step, but even this size is usually less than the refcount and malloc overhead.
The copying one even uses no stack-space, due to Cheney.
A GC is always superior to refcounts and manual malloc, because it's much too hard to do that by yourself.
With real-time you use incremental collections. Just store the state where to continue.
Agreed, the conventional m&s, stop the world collectors as eg. used in most major fancy languages are all terrible. You only need that for an FFI. But a good GC is far superior. And most importantly faster and safe. You don't update refcounts with a GC. You don't pollute your cache and concurrent updates with that.
Look at Java or .NET if you don't like lisp. Same tech, a solved problem.
> Any GC uses much less memory than a refcount or malloc application.
That's plain wrong.
> because it's much too hard to do that by yourself.
Too hard to do yourself? There are some of us who have been doing it for decades. In places where performance, predictable runtime and memory usage is of paramount importance (like the linux kernel) it is still done manually. I'll grant you Moore's law has made those places increasing rare nowadays.
Yes it harder to do it manually, but only in the sense that it's harder to do anything manually than have it automated. But being hard and error prone doesn't mean the result is slower, or uses more memory. A moments thought should have told you that. GC delays freeing memory until there is sufficient memory pressure. The mental load imposed by tracking malloc's means a programmer does it immediately so he can forget about it. Thus the memory is available for re-use immediately.
In my experience a long running program manually managing it's heap has a heap about twice the size of actual space in use. In theory some degenerate cases caused by fragmentation can make it far worse - but I've never been bitten by it. Long running GC languages (they tend to be written in Java) it's around 5 times. Again, if you done any sort of server administration, you would know this. All of us who do have watched Java VM's grow over with amazement and dismay. Ironically, the cure is a form of manual memory management - kill them and restart.
That article was presented at OOPSLA '05 which ran from October 16–20, 2005. I don't know when it was written, nor when the data for it was worked out. That said, it seems safe to say that it's more than twelve years out of date.
you don't need to compact the whole working area as in the classical implementation. if you find that a page is sparse enough, just copy it into a less-than-full page of the next generation.
