1

I started writing my own scripting language over the most recent weekend for both the learning experience and for my resume when I graduate high school. So far things have gone great, I can parse variables with basic types (null, boolean, number, and string) and mathematical expressions with operator precedence, and have a rudimentary mark and sweep garbage collector in place (after completing the mark/sweep collector I will implement a generational garbage collector, I know naive mark/sweep isn't very fast). I am unsure how to store the referenced objects for the garbage collector, though. As of now I have a class GCObject that stores a pointer to the it's memory and whether it is marked or not. Should I store a linked list to it's referenced objects in the class? I have looked at garbage collectors from other languages but I see no linked lists of references per GCObject, so it is confusing me.

TLDR: How do I store objects that are referenced by other objects in a mark and sweep garbage collector? Do I just store linked lists of objects in all my GCObjects?

Thanks guys.

Bob Jarvis - Слава Україні
  • 48,992
  • 9
  • 77
  • 110
Cole Shepherd
  • 53
  • 3

1 Answers1

3

You generally don't store the references to an object in anything but the locations at which those references naturally occur. During the mark operation, you don't need to know which references point to an object; rather, you need to know which references an object (or root) contains, so you can recursively mark those objects.

You also need, for the sweep phase, a way to iterate through all objects so you can finalise any unreferenced objects and return their storage to the allocation pool. How you would do this exactly depends on your general purpose allocator - you probably want to write a custom one.

(I'm assuming you don't want to do compaction - that's a whole lot more complicated).

davmac
  • 20,150
  • 1
  • 40
  • 68
  • Yes I already have a way to iterate through the objects, I was wondering if I should store the references the roots store in linked lists, or if there is some other way that I should do it. Linked lists just seem a bit overkill. – Cole Shepherd Apr 02 '12 at 23:32
  • You seem to be misunderstanding. You don't need to store "the references the roots store" in a list, or in anything else; those references are already stored - in the roots. – davmac Apr 03 '12 at 21:44
  • How are they stored in the roots, though, that's what I was asking. But I already found the answer elsewhere. Thanks anyways. – Cole Shepherd Apr 04 '12 at 16:35
  • 1
    For a non-relocating "mark and sweep" collector, one has to iterate through dead objects. Some GC frameworks, however, take a simpler approach: copy all live objects to a new heap and junk the old one. Such an approach avoids any per-dead-object cost for GC. – supercat Apr 25 '12 at 23:33