How to implement a garbage collector?

Question

Could anyone point me to a good source on how to implement garbage collection? I am making a lisp-like interpreted language. It currently uses reference counting, but of course that fails at freeing circularly dependent objects.

I've been reading of mark and sweep, tricolor marking, moving and nonmoving, incremental and stop-the-world, but... I don't know what the best way to keep the objects neatly separated into sets while keeping per-object memory overhead at a minimum, or how to do things incrementally.

I've read some languages with reference counting use circular reference detection, which I could use. I am aware I could use freely available collectors like Boehm, but I would like to learn how to do it myself.

I would appreciate any online material with some sort of tutorial or help for people with no experience on the topic like myself.

https://secure.wikimedia.org/wikipedia/en/wiki/Garbage_collection_%28computer_science%29 — Praetorian, Jul 28 '11 at 22:31
You shouldn't start with anything more complex than a nigh-braindead stop-the-world mark and sweep collector. Forget about sets, incremental collections and all that stuff for now. Getting the roots, getting a list of all live objects, etc. will be enough of a challenge for your first try. — , Jul 28 '11 at 22:33
And specifically, the "implementation strategies" section: https://secure.wikimedia.org/wikipedia/en/wiki/Garbage_collection_%28computer_science%29#Implementation_strategies — Ben Zotto, Jul 28 '11 at 22:34
possible duplicate of [Learning garbage collection theory](http://stackoverflow.com/questions/1318631/learning-garbage-collection-theory) — Dour High Arch, Jul 28 '11 at 23:45
I don't agree that this is a duplicate. That one is about theory, this one is about implementation and tutorials. — Zan Lynx, Jul 29 '11 at 00:47
You do want to learn how to do garbage collection, right? Because otherwise you can just use [Boehm-Demers-Weiser excellent conservative garbage collector](http://www.hpl.hp.com/personal/Hans_Boehm/gc/) at least until the language is well established and has some real applications to show it's worth, because until then there are more pressing matters than the tiny bit of performance you can squeeze out with a good gc. — Jan Hudec, Jul 29 '11 at 07:33

score 35 · Answer 1 · answered Jun 20 '12 at 10:58

Could anyone point me to a good source on how to implement garbage collection?

There's a lot of advanced material about garbage collection out there. The Garbage Collection Handbook is great. But I found there was precious little basic introductory information so I wrote some articles about it. Prototyping a mark-sweep garbage collector describes a minimal mark-sweep GC written in F#. The Very Concurrent Garbage Collector describes a more advanced concurrent collector. HLVM is a virtual machine I wrote that includes a stop-the-world collector that handles threading.

The simplest way to implement a garbage collector is:

Make sure you can collate the global roots. These are the local and global variables that contain references into the heap. For local variables, push them on to a shadow stack for the duration of their scope.
Make sure you can traverse the heap, e.g. every value in the heap is an object that implements a Visit method that returns all of the references from that object.
Keep the set of all allocated values.
Allocate by calling malloc and inserting the pointer into the set of all allocated values.
When the total size of all allocated values exceeds a quota, kick off the mark and then sweep phases. This recursively traverses the heap accumulating the set of all reachable values.
The set difference of the allocated values minus the reachable values is the set of unreachable values. Iterate over them calling free and removing them from the set of allocated values.
Set the quota to twice the total size of all allocated values.

Hi Jon, i would like to read through your Prototyping a mark-sweep garbage collector article but it asks for subscription. Is that the only way to read it — Hari, Feb 01 '15 at 14:53

score 10 · Answer 2 · answered Jul 28 '11 at 23:15

10

Check out the following page. It has many links. http://lua-users.org/wiki/GarbageCollection

answered Jul 28 '11 at 23:15

Mike

1,760
2
18
33

score 9 · Accepted Answer · answered Aug 01 '11 at 15:04

As suggested by delnan, I started with a very naïve stop-the-world tri-color mark and sweep algorithm. I managed to keep the objects in the sets by making them linked-list nodes, but it does add a lot of data to each object (the virtual pointer, two pointers to nodes, one enum to hold the color). It works perfectly, no memory lost on valgrind :) From here I might try to add a free list for recycling, or some sort of thing that detects when it is convenient to stop the world, or an incremental approach, or a special allocator to avoid fragmentation, or something else. If you can point me where to find info or advice (I don't know whether you can comment on an answered question) on how to do these things or what to do, I'd be very thankful. I'll be checking Lua's GC in the meantime.

score 4 · Answer 4 · answered May 13 '12 at 21:14

One thing I haven't yet seen mentioned is the use of memory handles. One may avoid the need to double-up on memory (as would be needed with the Cheney-style copying algorithm) if each object reference is a pointer to a structure which contains the real address of the object in question. Using handles for memory objects will make certain routines a little slower (one must reread the memory address of an object any time something might have happened that would move it) but for single-threaded systems where garbage collection will only happen at predictable times, this isn't too much of a problem and doesn't require special compiler support (multi-threaded GC systems will are likely to require compiler-generated metadata whether they use handles or direct pointers).

If one uses handles, and uses one linked list for live handles (the same storage can be used to hold a linked list for dead handles needing reallocation), one can, after marking the master record for each handle, proceed through the list of handles, in allocation order, and copy the block referred to by that handle to the beginning of the heap. Because handles will be copied in order, there will be no need to use a second heap area. Further, generations may be supported by keeping track of some top-of-heap pointers. When compactifying memory, start by just compactifying items added since the last GC. If that doesn't free up enough space, compactify items added since the last level 1 GC. If that doesn't free up enough space, compactify everything. The marking phase would probably have to act upon objects of all generations, but the expensive compactifying stage would not.

Actually, using a handle-based approach, if one is marking things of all generations, one could if desired compute on each GC pass the amount of space that could be freed in each generation. If half the objects in Gen2 are dead, it may be worthwhile to do a Gen2 collection so as to reduce the frequency of Gen1 collections.

Yes, the IBM APL interpreter uses handles, to pretty good effect. — Hot Licks, Jul 04 '14 at 22:02

score 4 · Answer 5 · answered Aug 01 '11 at 17:34

I have implemented a Cheney-style copying garbage collector in C in about 400 SLOC. I did it for a statically-typed language and, to my surprise, the harder part was actually communicating the information which things are pointers and which things aren't. In a dynamically typed language this is probably easier since you must already use some form of tagging scheme.

There also is a new version of the standard book on garbage collection coming out: "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Jones, Hosking, Moss. (The Amazon UK site says 19 Aug 2011.)

score 3 · Answer 6 · edited Jul 27 '16 at 10:55

3

Garbage collection implementation in Lisp

Building LISP | http://www.lwh.jp/lisp/

Arcadia | https://github.com/kimtg/arcadia

edited Jul 27 '16 at 10:55

Steven Shaw

6,063
3
33
44

answered Sep 20 '14 at 14:58

KIM Taegyoon

1,917
21
18

1

Wow! I think I'm going to throw out all the disorganized crap I've written trying to implement my own LISP-like language and start with that Building LISP tutorial you linked to. The main thing I like about is it's actually written in C - most tutorials on making LISP-like languages are written in LISP-like languages - nice for academia but pointless in reality. – ArtOfWarfare Feb 28 '15 at 18:33
A similar recommendation from [Build Your Own Lisp](http://www.buildyourownlisp.com/contents) is the article [Baby's First Garbage Collector](http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/) – Steven Shaw Jul 27 '16 at 03:22

score 2 · Answer 7 · answered Jul 29 '11 at 07:28

2

Read Memory Management: Algorithms and Implementations in C/C++. It's a good place to start.

answered Jul 29 '11 at 07:28

cprogrammer

5,503
3
36
56

score 0 · Answer 8 · edited May 23 '17 at 12:26

I'm doing similar work for my postscript interpreter. more info via my question. I agree with Delnan's comment that a simple mark-sweep algorithm is a good place to start. You'll need functions to set-mark, check-mark, clear-mark, and iterators for all your containers. One easy optimization is to clear-mark whenever allocating a new object, and clear-mark during the sweep; otherwise you'll need an entire pass to clear marks before you start setting them.

How to implement a garbage collector?

8 Answers8

Linked