GC and userdata mark and sweep

[Benjamin Legros <legros@...>]

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.