"Garbage Collection" by Jones & Lins was, in my opinion, an excellent book back in the day: http://tinyurl.com/8lrveqm
I noticed that Jones has a new book (The Garbage Collection Handbook) out now, which presumably is even better: http://tinyurl.com/8nl6con
"It is very likely that the Rust language will go with a similar model [per-thread instead of global garbage collection]."
Rust is using this model today.
I think a really cool tactic is racket's places, which basically creates individual zones running their own module with their own gc (but objects shared between cores don't take up extra space, there is a global table or something).
Nice article. What I didn't understand: How does a conservative GC without type information know where the references are in an object? E.g. given this object:
struct {
double a; // 64 bit
short b // 16 bit
int c, d; // 32+32 bit
FooPtr e; // 64 bit
int f; // 32 bit
BarPtr g; // 64 bit
}
Does it assume that all fields are aligned to 64 bit boundaries? Does it potentially consider a double to be a pointer? And how does it know where to stop looking for references without knowing the size of the object?
Oh, THOSE garbage collectors. I was rather hoping this would be an exposé on the secret tech employed by curbside trash collection companies.
i see alex is this busy. no wonder alex hasn't been online in steam recently
If you can look at a word of memory and differentiate pointers from values, garbage collection can become extremely simple. It's a shame that tagged architectures have largely died out.
As an experiment, I tried writing a garbage collector which used high-order bits of a word to identify pointers. The result is about a page of code in Forth:
http://hastebin.com/raw/gabunowelo.fs
This example works exclusively with fixed-size "cons pair" allocations, but generalizing to arbitrary-sized allocations only increases the complexity of the system slightly. Obviously this bitflag technique is not "safe" in general, as arbitrary values on the stacks could produce false positives, but it's easy to imagine a 33-bit or 65-bit architecture that provided the necessary hardware support without such caveats.