Re: GC and userdata mark and sweep

[Peter Cawley <lua@...>]

If you're doing what I understand you to be doing, and want to move
the core objects and relationships between those objects entirely from
Lua to C in order to improve memory usage and traversal time, then I
believe it can be done.

First, as you stated, each object becomes a userdata rather than a
table (presumably with an appropriate metatable attached to it, in
order for the remaining Lua portion of the app to interact fully with
it). Each userdata would then have an array of references
(connections) to other objects (or multiple categorised arrays, but
that's an implementation detail), with the critical point being these
references. It sounds like you really want these references to be raw
pointers to other bits of userdata, thus making it quick to traverse
(in C). Doing so would mean that the garbage collector wouldn't know
about these references, and may consider valid objects to be garbage.

Currently, when a userdata is marked [as non-garbage], the GC will
propogate that mark to the userdata's metatable and environment table.
One option would be to maintain duplicates of a userdata's internal
references in a Lua table, and make that table the userdata's
environment table. A better option (for your needs, though probably
not generally) would be to tweak the GC to propagate marks on your
userdata onto the other userdata which it references internally.

The important functions to look at are reallymarkobject, propagatemark
and traversetable in the lgc.c source file. I would begin by modifying
the Udata structure (lobject.h) and add two new fields to it:
"GCObject *gclist;" and "void (*traverse)(global_State*, Udata*);",
and then before you forget, initialise these fields to NULL for all
new userdata by default (luaS_newudata in lstring.c). The thinking
here is that your special userdatum which require special treatment by
the GC will set a non-NULL traverse function, which will be called by
the GC to propagate marks, and the gclist member is required as part
of this. Returning to reallymarkobject in lgc.c, the LUA_TUSERDATA
case needs to be modified. If gco2u(o)->traverse is NULL, then the
existing code should be executed. If it is not NULL, then code similar
to the function/table/thread case should be executed:
"gco2u(o)->gclist = g->gray; g->gray = o;". Moving onto propagatemark,
it needs a new case to handle userdata, perhaps something like the
following:
case LUA_TUSERDATA: {
  lua_assert(u->traverse != NULL);
  Udata *u = gco2u(o);
  g->gray = u->gclist;
  u->traverse(g, u);
  return sizeof(Udata) + u->len;
}

There are now two things remaining to implement - setting of the
traverse variable for special userdata, and the implementation of said
traverse function(s). Important to both of these things is converting
from a userdata pointer (in the traditional C API sense) back to a
Udata pointer. Once you know that a userdata is immediately prefixed
by a Udata structure, this becomes trivial:
static inline Udata* userdata2Udata(void* ud) {return ((Udata*)ud) - 1;}
Setting the traverse variable is simple - when a special userdata is
constructed, get the Udata pointer for it, and set the variable.
Writing the traverse function(s) is also simple - cast the Udata
pointer back into a userdata pointer (the inverse of the
userdata2Udata function), iterate over its internal array(s), and then
call markobject with a Udata pointer for every element in the array.

Note that I have not tried the above, or done anything similar before,
but it should (mostly) work.

On Sat, May 30, 2009 at 4:09 PM, Benjamin Legros <legros@mercs-eng.com> wrote:
>
> Hello,
>
> I've been writing a 3d application for some years now, largely based on Lua.
> The core of the program is a dependency graph a la Maya. That is we have
> graph nodes that contain attributes which are holding data, and these
> attributes can be connected to other attributes, letting data to travel
> through the whole graph.
> Each node is a table, and each attribute is a table with list of (backward
> and forward) connections to other attributes.
>
> For instance, we have 3d objects containing matrices, connections to
> materials, connections to lights and various other nodes. Evaluating an
> attribute or chaging an attribute's value usually involves traversing the
> scene graph.
>
> So far so good.
>
> But as time goes, the scene graph is growing bigger as we are maintaining
> bigger and bigger 3d scenes. The memory footprint of the graph is now all
> but negligeable (several hundreds of Mb in the worst cases), and the time
> taken to traverse the graph is getting quite painful.
>
> Yet this is not especially a Lua issue (having a C or C++ core would lead to
> the same problems), cutting the memory footprint and the graph traversal
> time by 2 or 3 wouldn't hurt... So we are considering moving the core of the
> graph to C++ with Lua userdata, and keeping the higher layers of the app in
> Lua for ease of development.
>
> We could use the Lua registry mechanism (luaL_ref and luaL_unref) for
> maintaining connections between userdata, but I suspect this won't help much
> in both memory and raw performances departments -- memory taken by the
> attributes connections would just be moved into the registry, and traversing
> the graph would constantly imply indirect referencing the registry...
>
> I am now envisageing to tweak the lua gc core so userdata can 'mark and
> sweep' other userdata. So I would like to know if some people here have any
> experience in this district, or if there are some good reason not to do this
> -- perhaps there are other ways I didn't see... Do you think, you Lua Gurus,
> it is feasible, and in this case do you have some leads to follow?
>
> For those who might wonder, we have solid knowledge of userdata (or so I
> think :)) and data are currently tightly packed as Lua arrays not to waste
> memory/time. I'm also having some good time reading literature about
> incremental garbage collection, tri color marking and whatever might help
> me. Eventually, I **really** enjoy Lua programming and would be delighted to
> have any other elegant option not involing break the whole thing down!
>
> Sorry for the (too) long post and thanks in advance for your suggestions!
>
> Cheers,
> Benjamin Legros
>
> --
> For your information, the app I'm working on is a 3d renderer, with OpenGL
> previs, aimed at 3d animation. The whole renderer core is written in C/C++
> while the editor is much written in Lua. We also make sweet use of Lua in
> the renderer for scripted procedural geometry.
>
>