Lua gc idea

[skaller <skaller@...>]

BTW: scanning the Lua gc code, it seems to use a naive
mark/sweep collection algorithm (my Felix collector does too).

This basically works by

(a) from the list of all objects, mark everything 'Garbage'.

(b) from the specified roots, chase pointers down, marking
everything seen on a recursive descent 'Valuable',
avoiding chasing down pointers to valuable objects.

(c) everything marked 'garbage' is garbage .. :)

Step (a) can be avoided. We keep a persistent variable
'parity' which is 0 or 1. When we allocate an object,
it gets marked immediately with the inverse of this flag

Now use the following algorithm:

(a) invert the parity flag
(b) chase pointers down as before, but using 'parity'
(c) everything marked 'parity' is valuable

The only caveat is that you must remove garbage
before running the algorithm again (or it will
magically become valuable).

Doing this saves trashing your cache twice 
(especially memory cached on disk by the VM),
potentially halving collection time.

Note that the 'mark' still has to be done once,
but it is done on allocation (and so probably has zero cost).

It looks like this can be implemented in the sweep,
by simply chaging this code:

#define ismarked(x)     ((x)->gch.marked & ((1<<4)|1))

to read (something like) this:

#define ismarked(x)     (!! ((x)->gch.marked & ((1<<4)|1)) ^ parity)

All the 'mark' code can then be chucked out.
The allocator must mark objects on allocation instead.

Hope this idea is useful (I'm using it in the Felix gc).

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net