from Hacker News

Demystifying Garbage Collectors

by gmcabrita on 10/11/12, 11:38 PM with 28 comments

• by RodgerTheGreat on 10/12/12, 1:22 AM

  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.

• by microtherion on 10/12/12, 12:52 AM

  "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

• by pcwalton on 10/12/12, 12:57 AM

  "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.

• by batgaijin on 10/12/12, 1:46 AM

  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).

• by mseepgood on 10/12/12, 6:17 AM

  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?

• by weirdkid on 10/12/12, 1:44 AM

  Oh, THOSE garbage collectors. I was rather hoping this would be an exposé on the secret tech employed by curbside trash collection companies.

• by keikun17 on 10/12/12, 1:25 AM

  i see alex is this busy. no wonder alex hasn't been online in steam recently