GC and userdata mark and sweep

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

GC and userdata mark and sweep

Benjamin 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.

Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Peter Cawley
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 <[hidden email]> 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.
>
>
Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Benjamin Legros

Thanks a lot for the pointers, this is exactly what I need!
I'll make a small test case to see it work.

Cheers,
Ben
Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Patrick Donnelly
In reply to this post by Benjamin Legros
Hi Benjamin,

On Sat, May 30, 2009 at 9:09 AM, Benjamin Legros <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Florian Weimer
In reply to this post by Benjamin Legros
* Benjamin Legros:

> 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.

Are you referring to traversal by your application, or by the garbage
collector?
Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Mark Hamburg
I concur with the suggestion that you should start by putting the node  
data in userdata and the links in userdata environment tables. This  
will avoid needing to make changes to the GC. Furthermore, if you are  
storing the links between nodes as refs, then they won't get GC'd  
anyway, so changing the GC wasn't going to help you anyway.

What you could do to make traversal fast is store the pointers between  
the data for nodes in the nodes themselves and in the environment  
tables. You could do this as follows:

1. Maintain a global weak-valued table mapping addresses (light  
userdata) to full userdata. This is so that you can easily go from a C  
pointer to the appropriate Lua value. Creating a node then looks  
something like the following. This leaves the userdata for the created  
node on the top of the stack because you don't want it to get GC'd.  
So, don't forget to pop it off when done with initialization and  
linking it in.

(Please excuse any errors. I haven't programmed against the Lua C API  
in a while.)

        void PushNodeMap( lua_State* L ) {
                lua_pushlightuserdata( L, &PushNodeMap ); // Just looking for a  
unique key
                lua_gettable( L, LUA_REGISTRYINDEX ); // Look up the node map
                if( lua_isnil( L, -1 ) ) {
                        lua_pop( L, 1 );
                        lua_newtable( L );
                        lua_newtable( L ); // Metatable
                        lua_pushliteral( "v" );
                        lua_setfield( L, -2, "__mode" );
                        lua_setmetatable( L, -2 );
                }
        }

        Node* CreateNode( lua_State* L ) {
                Node* n = (Node*) lua_newuserdata( L, sizeof( *n ) );
                lua_newtable( L ); // Environment table for node
                lua_setfenv( L, -2 );
                PushNodeMetatable( L );
                lua_setmetatable( L, -2 );
                PushNodeMap( L );
                lua_pushlightuserdata( L, n );
                lua_pushvalue( L, -3 ); // The userdata
                lua_settable( L, -3 ); // nodeMap[ lightud( n ) ] = fullud( n )
                lua_pop( L, 1 ); // Pop nodemap
                return n;
        }

2. When you want to set a link in a node, you need to also set the  
environment table for the node.

        void SetNodeLink( lua_State* L, Node* node, Node** field, Node*  
value ) {
                PushNodeMap( L );
                lua_pushlightuserdata( L, node );
                lua_gettable( L, -2 ); // node as full userdata
                lua_getfenv( L, -1 ); // Get the environment table
                lua_pushlightuserdata( L, field ); // key
                lua_pushlightuserdata( L, value );
                lua_gettable( L, -5); // value as full userdata
                lua_settable( L, -3 ); // node.env[ field ] = value
                lua_pop( L, 3 ); // Pop map, node, and environment
                *field = value;
        }

Note that a value of NULL works because we won't find anything when we  
do the lookup in the node map.

The above scheme could work perfectly well with polymorphic nodes.

One can imagine optimized versions of the above that get to assume  
we've already put the target node on the stack (e.g, because it's the  
target of a method). If the value wire up is being triggered from Lua,  
we may also have the Lua value already on the stack thereby obviating  
the need for the node map.

If setting links on nodes is rare enough, then one might want to delay  
creating a specialized environment for a node until we actually set  
something in the node.

This actually plays well to a modification that I was looking at  
making to Lua to provide a pseudo-index for the environment table of  
the first item in the stack frame. That's easy enough to write, but  
it's difficult to do in a way that maintains binary compatibility with  
existing compiled C code unless one assumes a limit on upvalues.

Anyway, even without this modification, this gives you code that can  
run entirely natively over the node graph but still relies on the Lua  
GC to manage node lifetimes.

Mark

P.S. Here's a version without the node map in which nodes are expected  
to already exist as Lua references:

Node* CreateNode( lua_State* L ) {
                Node* n = (Node*) lua_newuserdata( L, sizeof( *n ) );
                lua_newtable( L ); // Environment table for node
                lua_setfenv( L, -2 );
                PushNodeMetatable( L );
                lua_setmetatable( L, -2 );
                return n;
}

void SetNodeLink( lua_State* L, int nodeIndex, Node** field, int  
valueIndex ) {
        Node* v = (Node*) lua_touserdata( L, valueIndex );
        if( valueIndex < 0 && -valueIndex <= lua_gettop( L ) )
                valueIndex = lua_gettop( L ) + 1 + valueIndex;
        lua_getfenv( L, nodeIndex );
        lua_pushlightuserdata( L, v );
        lua_pushvalue( L, valueIndex );
        lua_settable( L, -3 );
        lua_pop( L, 1 );
        *field = v;
}


Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Asko Kauppi
In reply to this post by Benjamin Legros

Maybe you would benefit from a C++/Lua binding solution I've crafted  
at work. It's now ready but owned by the client. I should ask them if  
it can be open sourced, as MIT license.

So, currently I can tell you how it works but cannot share any code.  :)

Binding a C++ class to Lua is done by deriving it from LuaObject. If  
you want to bind an existing (non-Lua aware) class, you would derive  
from both that and LuaObject.

        class MyClass : public LuaObject { // it does use templates, this is  
oversimplification
        }

LuaObject has no data members, but it provides 'new(L)' and 'delete'  
overrides, allowing you to:

        new(L) MyClass( ...whatever constructor... )

This creates the object _into_ the memory acquired from Lua, and binds  
the object's destructor automatically to '__gc' metamethod.

That is the whole catch, really. You are now using Lua for your C++  
object's lifespan management.

(You can still also use the regular 'new' or local variable scoping or  
whatever, for 'MyClass'. It's just a class which knows how to jump to  
Lua.)

How this will work for you?

        class MyClass : public LuaObject {
                std::vector<MyClass*> siblings;
        }

You would push the sibling objects to Lua, as well. Then there's "one  
more thing".

You can keep Lua objects around for the whole lifespan of your object  
instance. Use it here to guarantee none of the vector-contained  
siblings get GC'ed before also your main instance has been.

This uses the Lua registry, of course. Each object using this feature  
has a table to references it will need. Lua GC will not touch those  
objects. Main object GC (actually, the C++ destructor that the GC  
calls) cleans that whole table, thus exposing the referred pieces for  
GC (unless something else still needs them).

We're using this system succesfully now in a scientific matrix  
calculation system, and I would say it is as fast as C++ and Lua can  
get.

Furthermore, it is lightwight in lines-of-code as well (one .h,  
one .cpp). It allows easy addition of any metamethods (we use __add,  
__sub etc.). All binding is done in the C++ side.  Personally, the  
best feature is not needing a binding generator, at all. They just  
complicate things, and break at Lua version changes.

- Asko


Benjamin Legros kirjoitti 30.5.2009 kello 18:09:

>
> 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.
>

Reply | Threaded
Open this post in threaded view
|

Re: GC and userdata mark and sweep

Benjamin Legros

Thanks everyone for your suggestions!

I understand the concept of using userdata environment table. Yet I have some concerns about it:
- I doubt that exploring the userdata environment through the C api provides sufficient gains -- scripted lua is probably doing a much better job
- Keeping pointers on userdata + references on userdata through userdata env will help improving perfs at the cost of doubling memory consumption -- well I can afford some more bytes

I have experienced a bit with Peter's tweak, and it seems to work. I'll run a monkey for a day or two and would anything go awry, I'll switch to keeping refs both in userdata and environment.
For what it's worth, the patch is pretty straight forward and contains a few dozens lines -- thanks to the lua code being incredibly small!

Ben