Paper! Uniprocessor GC Techniques 1

Uniprocessor GC Techniques, 1

Presenters' notes here

Some interesting related topics to tonight's discussion

• Sorted Array Faster than Unsorted Array?
• Haskell's Memory Management
• Cheney's Algorithm
• Cheney on the M.T.A.

Recap

Feb 6, Leo started us out on our month of garbage collecting by covering the first 2 sections of Wilson's survey paper, "Uniprocessor Garbage Collection Techniques". Garbage collection has a long history in computing, and covers quite a broad spectrum of topics, and Leo did a great job of pulling us through in spite of our many attempts to diverge into tangential discussions. From our perspective today, I think it's clear that the author's motivating statements that languages with an effective GC make it easier for programmers to reason abstractly about their programs are quite true. Just imagine trying to teach a high school class on programming, and you ask the students to copy an array. In Python you just tell them to set the new array equal to the old one "A=B", whereas in C you first have to teach them about how memory works, what a pointer to memory means, and then how to free the pointer later. This is not necessarily a problem, but it isn't at all what you wanted to teach them. The C programmer is never free to reason completely at the higher level of abstraction as there is always some additional cognitive load to deal with the memory. Section 2 covers several different approaches to GC and their pros and cons and I think helped give us a clearer picture of how we will proceed with our own implementations later this month. There are a lot of subtleties to the different approaches and a lot of trade-offs that need to be considered and I think we will all be going over this section again before the end of the month.