Re: incremental garbage collector?

["Thatcher Ulrich" <tu@...>]

On Mar 05, 2002 at 01:48 -0300, Roberto Ierusalimschy wrote:
> > Likewise, I'd love to hand this off to the Lua authors.
> 
> We are not going to invest time on an incremental GC in the near        
> future, unless someone else builds a "proof of concept". A proof of     
> concept is an implementation that shows that we can have incremental    
> GC in Lua with (1) small complexity (mainly small size), (2) portable   
> code, and (3) small overhead.                                           

Fair enough -- I'm pretty sure the write barrier would impose a
significant time overhead (maybe between 10% and 50% overall, but
that's really a guess).  I think it would be possible to make it a
compile-time option.

Complexity and portability are not a real problem, I don't think.
Anyway, this is all theoretical unless someone wants to finish a
proof-of-concept!  I have a fairly substantial starting point, if
anyone wants to have a go...

> Lua is quite different from OCaml and other languages with incremental GC, 
> and I have no idea how such collectors would behave in Lua. (For 
> instance, tables in Lua are very dynamic [and can be very big], and so 
> write-barriers can be expensive.) 

The write barrier from my sketch looks like this:

/*
** Keeps the collector synchronized.
*/
void luaC_writebarrier (lua_State *L, TObject *new_value)
{
	if (G(L)->gcstate->phase == LGC_DORMANT
		|| new_value == NULL
		|| ttype(new_value) == LUA_TNUMBER
		|| ttype(new_value) == LUA_TNIL
		)
	{
		return;
	}

	lua_assert(ismarked(new_value) || st->phase != LGC_SWEEPING);	/* otherwise we missed something! */
	markobject(G(L)->gcstate, new_value);
}

/*
// luaC_writebarrier(L, new_value) needs to be called
// whenever a pointer is written to the stack or to a table key or
// value slot.

// luaC_writebarrier(L, new_value) needs to be called whenever a new
// node is allocated.
*/


-- 
Thatcher Ulrich <tu@tulrich.com>
http://tulrich.com