3 ms·
In addition to not technically needing a GC, a simple GC can be small if you don't care (much) about performance. One variation over a basic tricolor mark and s
by vidarh 8y ago
In addition to not technically needing a GC, a simple GC can be small if you don't care (much) about performance. One variation over a basic tricolor mark and sweep using linked lists for each "color" is basically (ruby-ish pseudocode):
# At this point all objects are in the "white" set. We don't know if they're reachable (in which case they're garbage)
# Mark roots
push_registers_to_stack
stack.each {|ob| grey.append(ob) } # You need to do this to any other roots as well, e.g. any pointers from bss.
# Iteratively scan every object, moving unscanned objects into the "grey" set (reachable but unscanned)
grey.each {|ob|
ob.referenced_objects.each {|ref| grey.append(ref) }
# "ob" has now been scanned, so moving it into the black set (reachable *and* scanned)
grey.delete(ob)
black.append(ob)
}
# What remains in the "white" set is now the garbage, so free it. You can also, if you want, move this aside and free it lazily.
white.each {|ob| ob.free }
white = black
A "real" implementation of the above can be done in <100 lines in many languages. Doing efficient gc gets more complex very quickly, though.
The mruby gc is a good place to see a more realistic tricolor mark and sweep that is also incremental and also includes a generational collection mode. It's about 1830 lines of verbose and well commented C including about 300 lines of test cases and a Ruby extension to interact with it. A simpler one like the above could certainly be much smaller even in C.
- kazinator 8y agoRuby-ish pseudo code is somewhat remote from working Forth.
- vidarh 8y agoIt's remote in that it looks very different, but not in terms of complexity. The operations used in the pseudo code are basically just. - Pushing registers onto the stack - Iterating over the stack - Appending to a linked list - Popping the first entry off a linked list - Iterating over a linked list - Calling a function/method ("free") to release the memory. In it's most naive form this would mean appending it to a linked list of free memory. The two first requires dipping into assembler in a lot of languages. The rest will be tiny in most languages, including Forth, but my Forth knowledge is very rudimentary hence why I didn't try.