[rayiner]

Studying garbage collection is a wonderful education in algorithm engineering. Despite decades of work, there is no "best" GC algorithm. Instead, there are different points on the space of optimizing for space/throughput/latency/completeness/etc. Moreover, the various algorithms are linked by deep correspondences (e.g. Bacon's result that all collectors lie on a spectrum between pure tracing and pure reference counting, and that things like generational collection are hybrids.)

[snprbob86]

Saving somebody 10 seconds, here is Bacon's paper:

http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

[apu]

Adding the initial http links it automatically:

http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

[snprbob86]

Heh, fixed mine to save somebody yet one more second. Wrote this comment to waste that second that I saved.

That said, I'm reading this paper now. It's absolutely fascinating and very approachable. Well worth checking out.

[profquail]

The link is returning a 403 now (perhaps too much traffic from this article).

For anyone that still wants to read it, here's a citation -- you can easily find a copy by searching for the title of the paper.

  Bacon, David F., Perry Cheng, and V. T. Rajan.
  "A Unified Theory of Garbage Collection."
  Convergence 6, no. 17 (2004): 32.

[Someone]

I agree that studying garbage collectors is a nice pastime, but one can say the same of many other kinds of algorithms. Best memory allocator? Best thread scheduler? Best file system? Best instruction set? Best programming language? Best editor (just kidding)?

All have seen decades of work, and we have some heuristics that we use to gauge quality, but there is no single quality measure. Also, studying each of them is rewarding.

[seanmcdirmid]

> Best editor (just kidding)?

Writing your own editor can be as much fun as writing your own garbage collector.

The "garbage collection" book is the only physical one I still own (everything else given away and in e-form now). It is a fascinating book, and gives you insights into PL run-time systems that you wouldn't get as easily studying other algorithms.

[epsylon]

And which book is that?

edit: I'm guessing "The Garbage Collection handbook", by Richard Jones et al. Looks like an interesting read.

[seanmcdirmid]

I have the earlier blue bound cover book (just called "Garbage Collection"). The book you are referring to is brand new and I haven't looked at it yet, but given that the first authors are the same, it should be good.

[silentbicycle]

I've had and enjoyed both. The latter has less about the fundamentals, but adds chapters on real-time GCs, concurrent GCs, and other advanced material. (Most of whose research probably came out after the first edition.)

If you're interested in GCs, I would suggest getting the newer edition for advanced material, and deferring to freely available papers such as Wilson's "Uniprocessor Garbage Collection Techniques" for fundamentals.

[Someone]

You are right about writing an editor. I only thought about the eternal discussion about what's better: escape-jkl;-i or shift-alt-meta-coke bottle.

And yes, that blue book on garbage collection is worth reading; it's on my bookshelf, too. I'm still looking for something similar on text editors or spreadsheets.