[<<][libprim][>>][..]

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

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

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
a node?

   - recurse left
   - recurse right
   - return

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

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 ]
                      |                      |
                      v                      v   



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.

[Reply][About]

[<<][libprim][>>][..]