Re: GC and userdata mark and sweep

[Patrick Donnelly <batrick@...>]

Hi Benjamin,

On Sat, May 30, 2009 at 9:09 AM, 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!

I believe you are pre-optimizing your program before you fully move
over to userdata from tables. A change to the GC will most likely lead
you to only headache. I believe you should first try to maintain
connections using userdata environment tables. Following that if
unsatisfactory, use of the registry with luaL_ref and luaL_unref (with
appropriate __gc metamethods) will most likely yield a performance
boost. Only after trying both of these (and possibly rethinking how
you are designing this) should you make the drastic decision of
modifying the GC. From just my own experience and instinct, I believe
you will find the results of using luaL_ref and luaL_unref to be
comparable to your proposed GC tweak.

IMHO,

-- 
-Patrick Donnelly

"Let all men know thee, but no man know thee thoroughly: Men freely
ford that see the shallows."

- Benjamin Franklin