Practical Garbage Collection - Part 1: Introduction
worldmodscode.wordpress.com
Practical Garbage Collection - Part 1: Introduction
1–10 of 39 posts
Re: Practical Garbage Collection - Part 1: Introduction
#2What are the long term implications of the increasing amount of parallel computing resources available to programmers? Are we getting to a point where there is enough excess CPU available, that the extra instruction on every assignment for reference counting is no big deal? (In certain contexts. In some contexts extra instructions are always a big deal, but these don't span all of computing.) Combine that with incremental algorithms for cycle reclamation, and you'd have great low-latency GC.
Re: Practical Garbage Collection - Part 1: Introduction
#3What are the long term implications of the increasing amount of parallel computing resources available to programmers? Are we getting to a point where there is enough excess CPU available, that the extra instruction on every assignment for reference counting is no big deal? (In certain contexts. In some contexts extra instructions are always a big deal, but these don't span all of computing.) Combine that with increm…
The the object can be accessed (not modified, just accessed) from multiple threads, the extra instruction needs to be a thread safe atomic increment, which is hugely expensive, and becomes more expensive the more cores you have, especially in a NUMA architecture.
Also, when an object is freed, you need to decrement the reference count of every single object it points to, even objects that are referenced from many other places and clearly won't be reclaimed for a long time.
Re: Practical Garbage Collection - Part 1: Introduction
#4What are the long term implications of the increasing amount of parallel computing resources available to programmers? Are we getting to a point where there is enough excess CPU available, that the extra instruction on every assignment for reference counting is no big deal? (In certain contexts. In some contexts extra instructions are always a big deal, but these don't span all of computing.) Combine that with increm…
It's still not trivial even with massive parallelism. Performance is easily killed if you:
1) Completely saturate the memory interconnect between the processors and RAM chips
2) If your parallel collector threads are touching the same memory that your worker threads are, you're going to have some cache contention
3) One of the big challenges with cache lines that have writes in them is if they are shared between processors. For example, create two ref cells and have two parallel threads set them -- if the compiler did not happen to pad them out to cache line size, they'll be fighting for the same 64 bytes (8 64-bit words/pointers) of memory
We (Manticore) have done a lot of work to isolate the per-CPU work, heap pages, etc. (http://arxiv.org/abs/1105.2554 , MSPC 2011 proceedings should be out on acm.org soon-ish). But it's not easy and requires rearchitecting your whole compiler and runtime system. GHC is also in the middle of some similar work, and they have a much harder problem both due to the challenges of implementing laziness and they have a full-featured system and real user base, so they can't just change things willy-nilly.
Further, once you get the parallelism right, you end up in a different situation: Amdahl's Law bites. Even if 90% of your program is amenable to parallel work, if you make that portion go infinitely fast, you still have a sequential portion that takes 10% of the time and therefore limits you to a maximum of 10x speedup.
We are hitting that limitation right now in our research and going back to do more sequential performance work. I've got a small army of undergraduates implementing compiler optimizations and analyses :-)
Re: Practical Garbage Collection - Part 1: Introduction
#5The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized.
It probably isn't possible without a ton of modification, but I wish the JVM/CLR had an option to garbage collect through reference counting.
Re: Practical Garbage Collection - Part 1: Introduction
#6The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I w…
Reference counting is slower than proper garbage collection, since it adds an overhead for each access, instead of just during the collection. (There are ways to make reference counting faster, but they are no longer quite so simple.)
Re: Practical Garbage Collection - Part 1: Introduction
#7The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I w…
Unlikely to happen. Reference counting has poor interaction with the CPU memory hierarchy: It makes all objects larger, making the working set correspondingly larger, meaning your data cache is less effective. It makes code larger because of the extra ref counting twiddling code. Larger code means a less effective instruction cache, as well as being slower because of all the extra operations performed. Reference counts must be frequently modified, and they are scattered all over memory (next to each object), so you get poorer locality and more atomic writes which has all sorts of negative implications for cache-coherent SMP architectures.
So while you may not notice the penalty of reference counting since it is spread out over every operation, it's unlikely that it is better than proper GC for most applications. Maybe just for ones which are extremely sensitive to latency, yet don't mind running much slower overall (hard real time? aeronautics and space?).
As usual you'd need to measure it.
Re: Practical Garbage Collection - Part 1: Introduction
#8The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I w…
Reference counting is slower than proper garbage collection, since it adds an overhead for each access, instead of just during the collection. (There are ways to make reference counting faster, but they are no longer quite so simple.)
It's not quite true to say reference counting adds overhead "for each access" -- for example, you can easily have a loop which accesses an object but doesn't modify the reference count. Reference counting adds overhead each time someone "expresses an ownership interest" in an object (wording from http://developer.apple.com/library/ios/#documentation/genera...).
(That's not to say your main point is false. I don't actually know which is faster in general.)
Re: Practical Garbage Collection - Part 1: Introduction
#9A very good writeup, but one thing always confuses me.
What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear.
If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks!
[EDIT: thanks everyone for the answers so far!]
Re: Practical Garbage Collection - Part 1: Introduction
#10A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]
Traditionally, the stack is a FILO (first in, last out) allocation area. Generally they start at the top of memory and work their way down as space is allocated, then back up as it is freed.
The heap might start at the low end of unused memory (above the program and libraries) and is used for allocating space with arbitrary release order. This means it has to keep track of what is used and what is available as well as when to "grow the heap" by allocating more pages of memory.
Garbage collection is one way of managing a heap.