Fri Oct 8 09:27:10 CEST 2010
Trying to implement pointer reversal mark GC
The point: build a CELL store + GC that is very memory efficient to be
run on an embedded ARM target with about 64k RAM. It doesn't need to
My eye has fallen on mark/sweep with pointer reversal mark (not using
a stack) and possibly a lazy sweep (during alloc).
The cell store can use 14-16 bit pointers so we can fit a cell in one
During traversal, a cell can be in one of 3 states:
- not marked / traversed (FREE)
- marked, left reversed (TODO)
- marked, right reversed (DONE)
This leaves one more state to encode full object pointers.
So how to implement the pointer swapping. What are the operations on
- recurse left
- recurse right
My confusion seems to be about return. Recurse left will swap
pointers left, recurse right will swap pointers right but return will
restore pointer + it needs to know where to put it and whether to
So the marking is really about what state the object is in: did we
initiate a left recurse or a right recurse.
Let's write the traversal as an interpreter of the current code. It
can be in one of 3 states: TAG_FREE, TAG_CAR, TAG_CDR.
What are the invariants? The current pointer points to a node that is
in one of 3 states indicating where the back pointer is.
FREE CAR CDR
^ ^ ^ ^
| | | |
[ x | x ] [ x | x ] [ x | x ]
In the CAR and CDR cases, an extra storage element is necessary to
hold the overwritten pointer to the subtree under investigation.
Let's use a more interpreter-friendly terminology:
IP = current subtree under investigation
RP = location of continuation
Let's call them code and continuation: c, k.
Ok, this works pretty well!
Next: either implement struct/vectors on top of binary trees, or build
a different machine alltogether. The latter might be best since we
could keep only run-time on the embedded target, and repl + compiler
on the host?
Write the whole thing in racket.
Represent code and continuations simply as pairs.