5 ms·

Demystifying Garbage Collectors

90 points by gmcabrita 14y ago

mseepgood 14y ago
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?
- alexrp 14y ago
  I'll start with your last question: It does know the size of objects - this size is passed to the GC when you allocate memory from it. Root ranges (such as the stack, global variables, TLS areas, etc) also all have a static size. (Not strictly true - some runtimes have dynamically growing stacks, but the GC knows the size regardless.) Most garbage collectors assume pointers to be aligned on a word boundary; that is on a 4-byte boundary on 32-bit machines and an 8-byte boundary on 64-bit machines. This is a reasonable assumption because accessing pointers that are not word-aligned is extremely slow on most architectures. It does not care how fields that don't contain pointers are aligned because their contents are irrelevant (so this translates to the compiler being able to pack some fields together without worrying about breaking the GC). So, a conservative GC will simply scan over every word in an object and interpret it as a potential pointer, regardless of what it actually is. So yes - even a double will be considered a pointer.
  - mseepgood 14y ago
    Thanks alexrp and digitalinfinity for your replies!
- digitalinfinity 14y ago
  It can't make that assumption- in a conservative GC, any pointer sized field in an object could be a pointer. So assuming you're on a 32 bit machine, in the above example, the double would look like 2 pointers to the GC. One way of dealing with this is, the GC keeps a set of all the address ranges that belong to its objects (these are the only objects that could be garbage collected). Then, when it sees what could be a pointer, it'll first look up whether this "maybe pointer" actually belongs to it's address range, and only if it does will it add it to the mark stack for further scanning. In terms of how does it know when to stop looking for references, actually, the GC will know the object size for any objects that it has allocated, so it knows when to stop scanning it's own object. For objects that it hasn't given out, it doesn't matter since it won't scan those. And for the stack, it'll just scan the entire stack looking for pointers to it's own objects.
- rayiner 14y ago
  A conservative GC requires the application to obey certain "typical" behaviors. One of those behaviors is "natural" alignment of structures. Most C compilers will align pointers in structures to the word size of the architecture, inserting padding if necessary. In your example, padding would be inserted between "b" and "c" to align "c" to 32-bits and between "f" and "g" to align "g" to 64-bits (assuming this is a 64-bit machine). So the GC can scan an object a word at a time and be sure it'll hit all pointers. Note that using compiler directives that pack structures as tightly as possible, ignoring natural alignments, can break this assumption. As for your other questions, remember that a conservative GC manages objects allocated through it, not just random objects in the system. It can use allocator metadata to keep track of where objects start and how long they are.* It aligns objects to some multiple of the word size, and can ignore any bit pattern that doesn't point to some multiple of 4 or 8 bytes. It also knows the extents of its own heap. As its scanning pointers, it does some checks to see if a particular bit-pattern points outside of the heap or does not point to the beginning of an object. If a possible pointer passes all of these tests, it definitely points to an object. It might not actually be a real pointer, but the target is actually an object managed by the GC. On a 64-bit machine, it's actually fairly rare for a random "int" or "double" to be mistaken for a pointer. Most "ints" are small integers, and on a 64-bit machine the heap is almost always allocated above 4GB. Similarly, the odds of a 64-bit double bit pattern pointing inside the heap out of all those exabytes of heap is unlikely. *) This is similar to how a malloc implementation might use allocator metadata to know how big a chunk is for a free() call.
microtherion 14y ago
"Garbage Collection" by Jones & Lins was, in my opinion, an excellent book back in the day: http://tinyurl.com/8lrveqm 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 http://tinyurl.com/8nl6con
- alexrp 14y ago
  It's an amazingly in-depth and concise book. I fully recommend it!
pcwalton 14y ago
"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.
- alexrp 14y ago
  I was under the impression that the collector that's in place right now is just a cycle collector, not a full-blown garbage collector. But please correct me if I'm wrong!
  - pcwalton 14y ago
    Oh yes, you're right -- I was assuming you were grouping cycle collection under garbage collection. In any case, the cycle collector is task-local, not global.
RodgerTheGreat 14y ago
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 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.
- derleth 14y ago
  This is why, by default on 32-bit architectures, fixnums in GNU Emacs are 30 bits: http://stackoverflow.com/questions/106597/why-are-fixnums-in-emacs-only-29-bits http://stackoverflow.com/questions/106597/why-are-fixnums-in... http://www.gnu.org/software/emacs/manual/html_node/elisp/Integer-Basics.html http://www.gnu.org/software/emacs/manual/html_node/elisp/Int... SBCL has a more elaborate tag bit system: http://sbcl-internals.cliki.net/tag%20bit http://sbcl-internals.cliki.net/tag%20bit
- alexrp 14y ago
  Hey, you may be interested to know that in the upcoming ARM v8's AArch64 mode, the upper 8 bits of all pointers can be used freely for tagged pointers. See page 11 of: http://board.flatassembler.net/download.php?id=5698 http://board.flatassembler.net/download.php?id=5698
  - barrkel 14y ago
    The issue isn't adding extra data to pointers; it's distinguishing a pointer from an integer of the same size. The extra bit needs to be "meta". Some x64 targeted languages already use tagged pointers without specific hardware support; e.g. I recall reading about JVM using several bits of object pointers in 64-bit to encode a class index, so that polymorphic inline caches can be checked without an indirection.
keikun17 14y ago
i see alex is this busy. no wonder alex hasn't been online in steam recently
weirdkid 14y ago
Oh, THOSE garbage collectors. I was rather hoping this would be an exposé on the secret tech employed by curbside trash collection companies.
batgaijin 14y ago
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).
- alexrp 14y ago
  This sounds very much like how Erlang does it - each process gets an isolated garbage collected heap and communication between processes happens through message passing. How lightweight are Racket places? I'm not very familiar with the language, so I don't know if they're really comparable to Erlang processes.
  - batgaijin 14y ago
    Not lightweight at all really; a 1:1 mapping between places and cores.
- jules 14y ago
  How does that work? Either you have shared objects and you need a global garbage collector, or you don't. Using shared objects with a local GC results in memory leaks.

90 points by gmcabrita 14y ago

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?

alexrp 14y ago
I'll start with your last question: It does know the size of objects - this size is passed to the GC when you allocate memory from it. Root ranges (such as the stack, global variables, TLS areas, etc) also all have a static size. (Not strictly true - some runtimes have dynamically growing stacks, but the GC knows the size regardless.) Most garbage collectors assume pointers to be aligned on a word boundary; that is on a 4-byte boundary on 32-bit machines and an 8-byte boundary on 64-bit machines. This is a reasonable assumption because accessing pointers that are not word-aligned is extremely slow on most architectures. It does not care how fields that don't contain pointers are aligned because their contents are irrelevant (so this translates to the compiler being able to pack some fields together without worrying about breaking the GC). So, a conservative GC will simply scan over every word in an object and interpret it as a potential pointer, regardless of what it actually is. So yes - even a double will be considered a pointer.
- mseepgood 14y ago
  Thanks alexrp and digitalinfinity for your replies!
digitalinfinity 14y ago
It can't make that assumption- in a conservative GC, any pointer sized field in an object could be a pointer. So assuming you're on a 32 bit machine, in the above example, the double would look like 2 pointers to the GC. One way of dealing with this is, the GC keeps a set of all the address ranges that belong to its objects (these are the only objects that could be garbage collected). Then, when it sees what could be a pointer, it'll first look up whether this "maybe pointer" actually belongs to it's address range, and only if it does will it add it to the mark stack for further scanning. In terms of how does it know when to stop looking for references, actually, the GC will know the object size for any objects that it has allocated, so it knows when to stop scanning it's own object. For objects that it hasn't given out, it doesn't matter since it won't scan those. And for the stack, it'll just scan the entire stack looking for pointers to it's own objects.
rayiner 14y ago
A conservative GC requires the application to obey certain "typical" behaviors. One of those behaviors is "natural" alignment of structures. Most C compilers will align pointers in structures to the word size of the architecture, inserting padding if necessary. In your example, padding would be inserted between "b" and "c" to align "c" to 32-bits and between "f" and "g" to align "g" to 64-bits (assuming this is a 64-bit machine). So the GC can scan an object a word at a time and be sure it'll hit all pointers. Note that using compiler directives that pack structures as tightly as possible, ignoring natural alignments, can break this assumption. As for your other questions, remember that a conservative GC manages objects allocated through it, not just random objects in the system. It can use allocator metadata to keep track of where objects start and how long they are.* It aligns objects to some multiple of the word size, and can ignore any bit pattern that doesn't point to some multiple of 4 or 8 bytes. It also knows the extents of its own heap. As its scanning pointers, it does some checks to see if a particular bit-pattern points outside of the heap or does not point to the beginning of an object. If a possible pointer passes all of these tests, it definitely points to an object. It might not actually be a real pointer, but the target is actually an object managed by the GC. On a 64-bit machine, it's actually fairly rare for a random "int" or "double" to be mistaken for a pointer. Most "ints" are small integers, and on a 64-bit machine the heap is almost always allocated above 4GB. Similarly, the odds of a 64-bit double bit pattern pointing inside the heap out of all those exabytes of heap is unlikely. *) This is similar to how a malloc implementation might use allocator metadata to know how big a chunk is for a free() call.

microtherion 14y ago

"Garbage Collection" by Jones & Lins was, in my opinion, an excellent book back in the day: http://tinyurl.com/8lrveqm 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 http://tinyurl.com/8nl6con

alexrp 14y ago
It's an amazingly in-depth and concise book. I fully recommend it!

pcwalton 14y ago

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

alexrp 14y ago
I was under the impression that the collector that's in place right now is just a cycle collector, not a full-blown garbage collector. But please correct me if I'm wrong!
- pcwalton 14y ago
  Oh yes, you're right -- I was assuming you were grouping cycle collection under garbage collection. In any case, the cycle collector is task-local, not global.

RodgerTheGreat 14y ago

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

derleth 14y ago
This is why, by default on 32-bit architectures, fixnums in GNU Emacs are 30 bits: http://stackoverflow.com/questions/106597/why-are-fixnums-in-emacs-only-29-bits http://stackoverflow.com/questions/106597/why-are-fixnums-in... http://www.gnu.org/software/emacs/manual/html_node/elisp/Integer-Basics.html http://www.gnu.org/software/emacs/manual/html_node/elisp/Int... SBCL has a more elaborate tag bit system: http://sbcl-internals.cliki.net/tag%20bit http://sbcl-internals.cliki.net/tag%20bit
alexrp 14y ago
Hey, you may be interested to know that in the upcoming ARM v8's AArch64 mode, the upper 8 bits of all pointers can be used freely for tagged pointers. See page 11 of: http://board.flatassembler.net/download.php?id=5698 http://board.flatassembler.net/download.php?id=5698
- barrkel 14y ago
  The issue isn't adding extra data to pointers; it's distinguishing a pointer from an integer of the same size. The extra bit needs to be "meta". Some x64 targeted languages already use tagged pointers without specific hardware support; e.g. I recall reading about JVM using several bits of object pointers in 64-bit to encode a class index, so that polymorphic inline caches can be checked without an indirection.

keikun17 14y ago

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

weirdkid 14y ago

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

batgaijin 14y ago

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

alexrp 14y ago
This sounds very much like how Erlang does it - each process gets an isolated garbage collected heap and communication between processes happens through message passing. How lightweight are Racket places? I'm not very familiar with the language, so I don't know if they're really comparable to Erlang processes.
- batgaijin 14y ago
  Not lightweight at all really; a 1:1 mapping between places and cores.
jules 14y ago
How does that work? Either you have shared objects and you need a global garbage collector, or you don't. Using shared objects with a local GC results in memory leaks.