rapid lifetime based collection of transient user data objects?

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

rapid lifetime based collection of transient user data objects?

Ross Bencina
Hello Everyone

I would like to know about available techniques for achieving
eager/rapid collection of short-lived user data in Lua. I'm thinking of
things like scope-based, static-lifetime based GC hinting, or maybe
reference counting.

I notice that there has been discussion in the past, some related to
resource cleanup for exception handling [1] and some related to rapid
temporary resource recycling [2]. My interest is in the latter.

What I have in mind is a vector processing system where "vector objects"
are used with the same syntax used for numbers in lua (infix operators,
functions returning vectors etc). I would like to achieve efficient CPU
data cache usage for large temporary user data objects by reusing the
same objects rather than having a bunch of temporary and intermediate
values polluting the cache until the GC collects them.

Here's an example of the kinds of eager resource deallocation I'm
thinking of:

In an expression such as the following, where a, b, c, d are user data:

a = (b + c) + d;

the subexpression b+c will generate a temporary user data.

1) I would like the (b+c) temporary to be collected/freed/recycled
directly after the temporary's last use.

2) If it can be known that this expression is the last use of either b,
c, and/or d, I would like those objects to also be
collected/freed/recycled at that point.

I understand that this is not how GC usually works but is there some way
to achieve this in Lua without resorting to explicit allocation and
freeing functions?

Given that these user data are number-like and cannot hold references to
other objects, I think one approach might be to use reference counting.
Also at least within expressions, and for objects created and used only
in a single scope, it might be relatively easy to determine their
lifetime using static analysis.

It looks like LuaRC/LuaPlus [3, 4] reference counting system might be
one possible approach. Does that seem like a good fit for what I've
described above? Are there other options or approaches I should know
about? How have other people solved this problem? Are these issues being
considered at all for main-line Lua development or are they considered
out of scope?

Thanks very much,

Ross

[1] Subject: [Patch] Finalization of function objects
http://lua-users.org/lists/lua-l/2008-01/msg00138.html

[2] Lua: Improving deterministic resource cleanup
http://john.neggie.net/2009/lua/resource_finalization

[3] Subject: Re: Reference counting patch for Lua 5.1?
http://lua-users.org/lists/lua-l/2007-04/msg00278.html

[4] http://luaplus.org/


Reply | Threaded
Open this post in threaded view
|

Re: rapid lifetime based collection of transient user data objects?

Joshua Jensen-2
----- Original Message -----
From: Ross Bencina
Date: 10/28/2011 8:56 PM

> Given that these user data are number-like and cannot hold references
> to other objects, I think one approach might be to use reference
> counting. Also at least within expressions, and for objects created
> and used only in a single scope, it might be relatively easy to
> determine their lifetime using static analysis.
>
> It looks like LuaRC/LuaPlus [3, 4] reference counting system might be
> one possible approach. Does that seem like a good fit for what I've
> described above? Are there other options or approaches I should know
> about? How have other people solved this problem? Are these issues
> being considered at all for main-line Lua development or are they
> considered out of scope?
>
> [3] Subject: Re: Reference counting patch for Lua 5.1?
> http://lua-users.org/lists/lua-l/2007-04/msg00278.html
>
I can't recall if I ever did a standalone LuaRC 5.1, but the reference
counting is definitely in the LuaPlus [1] source code.  Look for
LUA_REFCOUNT and copy the changes into your copy of Lua.  It works in
almost all instances, and it is very effective at keeping memory under
control.  I also like that it adds deterministic finalization to Lua.

[1] https://github.com/jjensen/luaplus51-all

-Josh

Reply | Threaded
Open this post in threaded view
|

Re: rapid lifetime based collection of transient user data objects?

Ross Bencina
On 29/10/2011 6:03 PM, Joshua Jensen wrote:
> I can't recall if I ever did a standalone LuaRC 5.1, but the reference
> counting is definitely in the LuaPlus [1] source code. Look for
> LUA_REFCOUNT and copy the changes into your copy of Lua. It works in
> almost all instances, and it is very effective at keeping memory under
> control. I also like that it adds deterministic finalization to Lua.

Thanks for your fast reply Josh,

Is there a write-up somewhere of how the LuaPlus reference counting
works? I'm wondering about things like: Does it replace the current Lua
GC with reference counting for all objects? or can it be applied
selectively to certain types? Does it perform cycle detection? How does
it performe compared to the standard Lua GC?

One thing that would concern me about using eager reference counting for
absolutely everything is that it could cause spikes in CPU usage when a
large tree of objects becomes unreachable -- whereas with incremental GC
the time taken by a GC cycle can be bounded. Perhaps there is a way of
having incremental/bounded time resource deallocation with reference
counting too.

Thanks

Ross.

Reply | Threaded
Open this post in threaded view
|

Re: rapid lifetime based collection of transient user data objects?

Mike Pall-32
In reply to this post by Ross Bencina
Ross Bencina wrote:

> Here's an example of the kinds of eager resource deallocation I'm
> thinking of:
>
> In an expression such as the following, where a, b, c, d are user data:
>
> a = (b + c) + d;
>
> the subexpression b+c will generate a temporary user data.
>
> [...]
> Are there other options or approaches I should know about?

http://lua-users.org/lists/lua-l/2006-05/msg00204.html

--Mike

Reply | Threaded
Open this post in threaded view
|

Re: rapid lifetime based collection of transient user data objects?

Ross Bencina

On 29/10/2011 9:50 PM, Mike Pall wrote:

> Ross Bencina wrote:
>> Here's an example of the kinds of eager resource deallocation I'm
>> thinking of:
>>
>> In an expression such as the following, where a, b, c, d are user data:
>>
>> a = (b + c) + d;
>>
>> the subexpression b+c will generate a temporary user data.
>>
>> [...]
>> Are there other options or approaches I should know about?
>
> http://lua-users.org/lists/lua-l/2006-05/msg00204.html

Thanks Mike

That would certainly solve the issue with temporaries. I have a couple
of questions about that post:

I'm a little unclear whether that technique can be used to deal with
"crystalised" (evaluated) vectors/matricies. It seems to me that once
the internal expression tree has been evaluated, and that evaluated
datum is referenced by a Lua variable, then it's lifetime is subject to
the usual Lua GC. Is that correct?

E.g.:

a = b + c + d
print (a[1]) -- access an element of a. causes the expression tree to be
evaluated.

My understanding is that the datum pointed to by 'a' would now be
subject to usual Lua object lifetime. Does your approach have a way to
avoid this?


In that post you write:

 > In the case of a vector/matrix library for Lua I suggest using
 > fixed size userdata objects. They can hold up to a fixed size
 > expression in a plain list (in postfix order). This avoids
 > problems with tree reference counting and should be good enough
 > for most practical purposes.

How would this work if an expression is used at two sites, e.g.:

a = x + y

b = z + a

c = f(a)

d = g(b)

I'm not seeing how the common subexpression x+y would be evaluated only
once without "tree reference counting". Do I understand correctly? Are
you assuming this case is uncommon on practice?

Thank you

Ross.

Reply | Threaded
Open this post in threaded view
|

Re: rapid lifetime based collection of transient user data objects?

Tony Finch
In reply to this post by Ross Bencina
On 29 Oct 2011, at 03:56, Ross Bencina <[hidden email]> wrote:
>
> I would like to know about available techniques for achieving eager/rapid collection of short-lived user data in Lua.

The generational GC in Lua 5.2 should improve the handling of short-lived objects.

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/
Reply | Threaded
Open this post in threaded view
|

Re: rapid lifetime based collection of transient user data objects?

Joshua Jensen-2
In reply to this post by Ross Bencina
----- Original Message -----
From: Ross Bencina
Date: 10/29/2011 1:45 AM
> On 29/10/2011 6:03 PM, Joshua Jensen wrote:
>> I can't recall if I ever did a standalone LuaRC 5.1, but the reference
>> counting is definitely in the LuaPlus [1] source code. Look for
>> LUA_REFCOUNT and copy the changes into your copy of Lua. It works in
>> almost all instances, and it is very effective at keeping memory under
>> control. I also like that it adds deterministic finalization to Lua.
>
> Is there a write-up somewhere of how the LuaPlus reference counting works?
No.
> I'm wondering about things like: Does it replace the current Lua GC
> with reference counting for all objects?
All objects are reference counted.  The incremental collector in Lua 5.1
can still be called.
> or can it be applied selectively to certain types?
It cannot.
> Does it perform cycle detection?
No.  If you are going to end up with cycles, you'll need to call
lua_gc() on occasion.
> How does it performe compared to the standard Lua GC?
Well, the majority of the time, it isn't necessary to call lua_gc() at
all.  If you never have a cycle, you should never really need to call it.

Weak tables are not handled, if I recall correctly.

In terms of performance, reference counting occurs, and that adds
overhead to any TValue manipulation.  On the other hand, deterministic
finalization means that objects will fall out of scope at an 'end'.  
Memory is kept under control all the time.

The benchmarks against LuaRC 5.0 [1] look good.

I am unaware of anyone using the reference counting implementation under
Lua 5.1.

-Josh

[1] http://lua-users.org/lists/lua-l/2004-06/msg00369.html