RE: Garbage collection

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

RE: Garbage collection

David Bhowmik
Thanks for your feedback Joshua. I have now written a patch for lua to turn
its garbage collection into a pseudo reference counting system, and this is
working swimingly. I was wondering what platforms your game was available
for because we are currently working on PC but are considering porting out
engine to the PS2 and XBox. Do you know how lua performs on these platforms?
Is there anything to watch out for?

Dave

-----Original Message-----
From: Joshua Jensen [[hidden email]]
Sent: 11 October 2002 17:44
To: Multiple recipients of list
Subject: RE: Garbage collection


> I am having trouble with Lua garbage collection. I am using 
> Lua as an agent system for a real time game. Basically the 
> mark and sweep system takes to long. Having a small threshold 
> requires garbage collecting regularly, which means marking a 
> lot of data regularly and cleaning up a little of it. The 
> marking takes to long to do so regularly. Having a high 
> threshold requires marking less regularly which is better but 
> cleaning up loads of data in one sweep, which takes to long. 
> There is no good balance here. Has anyone found a way around this?

Don't cause anything to allocate during the real-time.

Seriously.

It was the only way to ship Amped: Freestyle Snowboarding.  No closures
could be generated on the fly.  No tables could be generated on the fly.
No strings could be generated on the fly.  The allocations were
identified, and pregenerated before the real-time ran.

So, instead of filling in myTable like this in the real-time:

myTable = {}
myTable.Var1 = 5
myTable.Var2 = "Hi"

myTable was made global, generated before the real-time loop, with all
the possible fields in place.

In other words, either make the necessary changes to your real-time Lua
codebase (by breakpointing the realloc function for Lua to determine
where memory allocations are), or don't count on using Lua during your
real-time.  :(

-Josh

Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

Brownsword
The main issue is that the PS2 is a fairly low clock rate by today's standards, and it has a small L1 cache, no L2 cache, and the memory is high latency RamBus memory.  Walking many data structures is therefore a rather expensive operation, and this is my single greatest point of concern about using Lua on this platform.  

I'd haven't been following the discussions lately -- what is the current plan for GC in Lua 5, and when can we expect to see an implementation of it to test with?  What are the caveats to the reference counting scheme David mentioned?



-----Original Message-----
From: David Bhowmik [[hidden email]]
Sent: Monday, October 21, 2002 6:00 AM
To: Multiple recipients of list
Subject: RE: Garbage collection


Thanks for your feedback Joshua. I have now written a patch for lua to turn
its garbage collection into a pseudo reference counting system, and this is
working swimingly. I was wondering what platforms your game was available
for because we are currently working on PC but are considering porting out
engine to the PS2 and XBox. Do you know how lua performs on these platforms?
Is there anything to watch out for?

Dave

-----Original Message-----
From: Joshua Jensen [[hidden email]]
Sent: 11 October 2002 17:44
To: Multiple recipients of list
Subject: RE: Garbage collection


> I am having trouble with Lua garbage collection. I am using 
> Lua as an agent system for a real time game. Basically the 
> mark and sweep system takes to long. Having a small threshold 
> requires garbage collecting regularly, which means marking a 
> lot of data regularly and cleaning up a little of it. The 
> marking takes to long to do so regularly. Having a high 
> threshold requires marking less regularly which is better but 
> cleaning up loads of data in one sweep, which takes to long. 
> There is no good balance here. Has anyone found a way around this?

Don't cause anything to allocate during the real-time.

Seriously.

It was the only way to ship Amped: Freestyle Snowboarding.  No closures
could be generated on the fly.  No tables could be generated on the fly.
No strings could be generated on the fly.  The allocations were
identified, and pregenerated before the real-time ran.

So, instead of filling in myTable like this in the real-time:

myTable = {}
myTable.Var1 = 5
myTable.Var2 = "Hi"

myTable was made global, generated before the real-time loop, with all
the possible fields in place.

In other words, either make the necessary changes to your real-time Lua
codebase (by breakpointing the realloc function for Lua to determine
where memory allocations are), or don't count on using Lua during your
real-time.  :(

-Josh

Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

Roberto Ierusalimschy
> what is the current plan for GC in Lua 5 [...]

We are planning to release 5.0, and then to start working in a
generational GC for 5.1. To make a new GC for 5.0 would delay too much
its final release.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

Nick Trout-5
In reply to this post by David Bhowmik
> Andrew Brownsword:
> The main issue is that the PS2 is a fairly low clock rate by 
> today's standards, and it has a small L1 cache, no L2 cache, 
> and the memory is high latency RamBus memory.  Walking many 
> data structures is therefore a rather expensive operation, 
> and this is my single greatest point of concern about using 
> Lua on this platform.  

Perhaps someone will write VU-Lua! Still wont fix your GC cache woes
though. The generational GC will help as the walks won't be so long.
>From what I've read a very high percentage of the objects that get
deleted are newer ones, so if you minimise object creation your code and
call the GC regularly perhaps this will deal with this issue.

> What are the 
> caveats to the reference counting scheme David mentioned?

Cyclic referencing could cause some objects never to be deleted if they
become isolated. Mark and sweep avoids this problem. Python is reference
counted and has to have a separate library to find cyclic references.

It slightly complicates object management from the C side because you
have to manage the reference count to Lua objects when you want to
reference them. There is potential for error here if don't reference and
unreference them correctly. You may be able to hide all of this in the
Lua API though, instead of handling the reference counts directly as you
do in Python. The Boost library has features to hide this functionality
for Python.


If I understand the problem, a danger with the generational method is
that objects will jump write barrier after a certain age and eventually
the older objects will need to be sweeped. This will lead to the same
problem that we have now ie. The GC taking too long. I wonder if Lua had
an explicit object release/destroy function if this would removed the
necessity for the "older sweep". eg.

obj = {}
destroy(obj) -- this sets obj to nil and frees the table object
associated with it.

There is a danger here that this will leave dangling pointers/references
from other objects so perhaps to compliment this you could have a
reference count method which counts the number of references to an
object. Eg.

obj = {}
-- count the number of references to the object referenced by obj
-- which will include obj itself.
assert( refcount(obj)==1 ) 
destroy(obj)

There may be many circumstances where you have objects which you know
you can delete and don't need the GC to pick these up. Obviously if you
let the GC handle everything then there is less chance of error, this is
an optimisation, which is optional. The benefit is the GC could be
called less often and in conjunction with a generation GC may provide
efficient GC without the need for a complicated incremental system
(which would scan everything and may be less efficient, but
distributed).

Regards,
Nick




Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

Thatcher Ulrich
On Wed, 23 Oct 2002, Nick Trout wrote:
>
> > What are the
> > caveats to the reference counting scheme David mentioned?
>
> Cyclic referencing could cause some objects never to be deleted if they
> become isolated. Mark and sweep avoids this problem. Python is reference
> counted and has to have a separate library to find cyclic references.

I've been thinking about this a little -- the regular mark-sweep
should be able to collect cyclic stuff, right?  So reference-counting
is sort of an incremental collector for non-cyclic structures.  The
great thing about reference counting is that it's simple and easy to
understand.  Has David posted his patch publically?

> It slightly complicates object management from the C side because you
> have to manage the reference count to Lua objects when you want to
> reference them. There is potential for error here if don't reference and
> unreference them correctly. You may be able to hide all of this in the

I think the existing Lua API should be adequate -- a lua_ref just
increments the object's ref count when it's created via lua_ref(), and
decrements it when it's destroyed via lua_unref().  No need to expose
the concept of the ref count outside of the core.

-Thatcher


Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

Nick Trout-5
In reply to this post by David Bhowmik

> [[hidden email]] On Behalf Of Thatcher Ulrich
> Sent: Wednesday, October 23, 2002 4:23 PM

> I've been thinking about this a little -- the regular mark-sweep
> should be able to collect cyclic stuff, right?  So reference-counting
> is sort of an incremental collector for non-cyclic structures.  The
> great thing about reference counting is that it's simple and easy to
> understand.  Has David posted his patch publically?

If the patch is public then I don't know where it is. 

Maybe you could use the two together. Python has had to resort to this.
I believe their cyclic collector is a script library so Lua would have
the advantage of a faster C based one. I've no idea what algorithm they
use but I don't think its mark and sweep.
http://www.python.org/doc/current/lib/module-gc.html


> > It slightly complicates object management from the C side 
> because you
> > have to manage the reference count to Lua objects when you want to
> > reference them. There is potential for error here if don't 
> reference and
> > unreference them correctly. You may be able to hide all of 
> this in the
> 
> I think the existing Lua API should be adequate -- a lua_ref just
> increments the object's ref count when it's created via lua_ref(), and
> decrements it when it's destroyed via lua_unref().  No need to expose
> the concept of the ref count outside of the core.

I havent had time to check and I don't know if there are differences in
Lua 5, but from what I remember you could use ref and unref as you
describe. I don't think you'd have to alter their functionality as they
are reference counting/locking Lua objects already. The internals of Lua
would, I think, need some work. So this patch will be interesting to
see.

You may get problems when you get "islands" of objects which the M&S
collector would delete but have C references to and should not be
deleted. Lua_ref() locks these objects for C. There may have to be a
separate counter for Lua internally which the C count would override.

A (total) reference count method to return the number of references to
an object would still be a very useful debugging tool for making sure
that you are releasing objects when you think you are. (eg. When you do
a obj=nil).

Nick






Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

David Bhowmik
In reply to this post by David Bhowmik
The patch is pretty nasty. It replaces a few of the functions in lgc and
also the setting of globals and table objects so that all assignments are
referenced and unreferenced accordingly. it uses the 'marked' field in
strings and userdata structures counting negatively so as not to be confused
with reserved string references, and uses the 'mark' pointer field in
closures etc as an int as this is no longer required for chaining objects
when marking. Ugly I know, but it means not having to rework loads of lua. 

There is only a need to mark the stack, tag functions and locked objects,
everything else is marked by its reference count. The collection is spread
so as to do a portion of the collection every time it is called. We are
using it for a real time agent system so we call it directly ourselves a few
times a second. We are running a couple of hundred agents each updating
twenty times a second and creating and discarding loads of user types every
time they do this. The patch has removed the gc stammer from our engine.

I haven't as yet sorted anything for circular referenced islands and am at
present throwing an error if anyone does this. Does anyone have any good
policies for dealing with this?


-----Original Message-----
From: Nick Trout [[hidden email]]
Sent: 24 October 2002 01:24
To: Multiple recipients of list
Subject: RE: Garbage collection




> [[hidden email]] On Behalf Of Thatcher Ulrich
> Sent: Wednesday, October 23, 2002 4:23 PM

> I've been thinking about this a little -- the regular mark-sweep
> should be able to collect cyclic stuff, right?  So reference-counting
> is sort of an incremental collector for non-cyclic structures.  The
> great thing about reference counting is that it's simple and easy to
> understand.  Has David posted his patch publically?

If the patch is public then I don't know where it is. 

Maybe you could use the two together. Python has had to resort to this.
I believe their cyclic collector is a script library so Lua would have
the advantage of a faster C based one. I've no idea what algorithm they
use but I don't think its mark and sweep.
http://www.python.org/doc/current/lib/module-gc.html


> > It slightly complicates object management from the C side 
> because you
> > have to manage the reference count to Lua objects when you want to
> > reference them. There is potential for error here if don't 
> reference and
> > unreference them correctly. You may be able to hide all of 
> this in the
> 
> I think the existing Lua API should be adequate -- a lua_ref just
> increments the object's ref count when it's created via lua_ref(), and
> decrements it when it's destroyed via lua_unref().  No need to expose
> the concept of the ref count outside of the core.

I havent had time to check and I don't know if there are differences in
Lua 5, but from what I remember you could use ref and unref as you
describe. I don't think you'd have to alter their functionality as they
are reference counting/locking Lua objects already. The internals of Lua
would, I think, need some work. So this patch will be interesting to
see.

You may get problems when you get "islands" of objects which the M&S
collector would delete but have C references to and should not be
deleted. Lua_ref() locks these objects for C. There may have to be a
separate counter for Lua internally which the C count would override.

A (total) reference count method to return the number of references to
an object would still be a very useful debugging tool for making sure
that you are releasing objects when you think you are. (eg. When you do
a obj=nil).

Nick





Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

Nick Trout-5
In reply to this post by David Bhowmik
> On Behalf Of Thatcher Ulrich
> Sent: Wednesday, October 23, 2002 4:23 PM
>
> I think the existing Lua API should be adequate -- a lua_ref just
> increments the object's ref count when it's created via lua_ref(), and
> decrements it when it's destroyed via lua_unref().  No need to expose
> the concept of the ref count outside of the core.

There may be a slight performance issue here, and I think this is why
Python lets you handle referencing directly. Consider a swap function:
after you have swapped the values of the variables the reference count
is exactly the same, but if you reference count through the API then
you'll increment and decrement the count on the variables whilst
swapping, when its actually unncesssary. Python allows "deferred"
reference counting so that you can just tot up the necessary counts
afterwards. Actually Lua the assignment (as opposed to C) may be
slightly easier as you can do "a,b=b,a" but you get the point. I think
any extra cost incurred here is outweighed by the hiding of the whole
system.

http://www.iecc.com/gclist/GC-algorithms.html#Variations "Deferred
reference counting"


> On Behalf Of David Bhowmik
> Sent: Thursday, October 24, 2002 9:45 AM
> 
> The patch is pretty nasty. It replaces a few of the functions 
> in lgc and
> also the setting of globals and table objects so that all 
> assignments are
> referenced and unreferenced accordingly. 

Do you just use lua_ref and unref?

> it uses the 'marked' field in strings and userdata structures counting
negatively so as not 
> to be confused with reserved string references, and uses the 'mark'
pointer field in
> closures etc as an int as this is no longer required for 
> chaining objects when marking. Ugly I know, but it means not having to
rework 
> loads of lua. 

So as it stands you cannot use the M&S GC without seperating this out.

> There is only a need to mark the stack, tag functions and 
> locked objects,
> everything else is marked by its reference count. The 
> collection is spread
> so as to do a portion of the collection every time it is 
> called. 

If everything is marked, can you not free it when the ref count (with no
mark) is 0? I assume you can't do this because you something nasty might
happen in the Lua executor and you'd rather free stuff outside of there.

> We are
> using it for a real time agent system so we call it directly 
> ourselves a few
> times a second. We are running a couple of hundred agents 
> each updating
> twenty times a second and creating and discarding loads of 
> user types every
> time they do this. The patch has removed the gc stammer from 
> our engine.

[in the tone of Mr Burns] Excellent 

> I haven't as yet sorted anything for circular referenced 
> islands and am at
> present throwing an error if anyone does this. Does anyone 
> have any good
> policies for dealing with this?

Reenable M&S GC and call that! Perhaps once its made generational,
working with the RC objects, the hit will be minimal.

-- cyclic references
A = {}
B = { a = A }
A.b = B

A = nil -- should not delete A even if we meant to

I guess there are a few strategies: 
- Use an algorithm to determine where the islands are and delete them
(eg. M&S).
- Remove the cyclic dependencies so the object will be deleted.
- Use an interface that will prevents cyclic dependencies (proxies?):

Eg.
A = {}
B = { a = function() return A end }
A.b = function() return B end

A = nil
C = B.a() -- is now nil (untested!)

This is more inefficient and complicated. It is just a suggestion but if
used sparingly may help.

Regards,
Nick







Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

tom7ca
In reply to this post by Thatcher Ulrich
> I've been thinking about this a little -- the regular mark-sweep
> should be able to collect cyclic stuff, right?  So
reference-counting
> is sort of an incremental collector for non-cyclic structures.  The
> great thing about reference counting is that it's simple and easy to
> understand.  Has David posted his patch publically?

Reference counting is not "incremental" in any interesting
sense: there is no bound on the number of blocks freed by any single
assignment.  In fact, the same is true even for completely manual
storage management: calling "free" is not a constant time operation,
so even if you move to more complicated reference counting schemes,
you still lose.

I really don't understand this infatuation with reference counting:
it's inefficient on the average, it does not guarantee bounded
latency, and it leaks storage in the presence of circular structures.
 Implementing it right is a lot of work and it infects every single
piece of C code with error prone operations.  And, unlike garbage
collection, where you have to worry about GC pauses only when you
allocate something new, reference counting may hit you with memory
management pauses on any assignment.

If you want soft or hard real-time response for dynamic memory
allocation, well-implemented garbage collectors are not only
convenient, they are pretty much your only choice.  Anything else may
appear to work most of the time, but it doesn't guarantee anything.
It would be great for Lua to get a real-time or soft real-time or
incremental GC.  Until then, paying a little attention to when you
allocate storage, using storage pools, and invoking the garbage
collector frequently when your process is idle probably will work just
as well as reference counting, if not better.

Tom.


Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

David Bhowmik
In reply to this post by David Bhowmik

-----Original Message-----
From: Nick Trout [[hidden email]]
Sent: 24 October 2002 21:54
To: Multiple recipients of list
Subject: RE: Garbage collection

> Do you just use lua_ref and unref?

No, I am using Lua 4 we haven't oved on to 5 yet so I dont know how the GC
works for that. lua_ref keeps a list of object that have been referenced.
When the GC is called it goes throught this list and marks the objects. This
ends up being a deep marking process down through tables. It then does the
global table and stack etc in the same way. So using lua_ref saves no time
on marking.

> So as it stands you cannot use the M&S GC without seperating this out.

Because it reuses the fields m&s is replaced.


> If everything is marked, can you not free it when the ref count (with no
> mark) is 0? I assume you can't do this because you something nasty might
> happen in the Lua executor and you'd rather free stuff outside of there.

No. As desribed earlier, the lua_ref lock system does not mark any objects
until it calls the gc routine. Although a ref count may be at 0, the object
may be in the lock list.


> Reenable M&S GC and call that! Perhaps once its made generational,
> working with the RC objects, the hit will be minimal.

yeah cant wait to see that. Our user data usage hit is for new objects. This
will cheapen the marking process. It would be nice it lua allowed you to
spread the ammount of collection being done so the sweep didnt take so long
and did less at a go. We could then set a M&S size that didnt effect our
engine performance.


Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

David Bhowmik
In reply to this post by David Bhowmik
No need to get religious. M&S may be appropriate for you but not for
problems like ours. We have no idle time. 

> And, unlike garbage collection, where you have to worry about GC pauses
only when you
> allocate something new, reference counting may hit you with memory
> management pauses on any assignment.

m&s takes time on allocation and then a massive hit on collection of loads
at once. Reference counting spreads the collection hit. For some problems
that is a better solution. There are problems with cirular references but if
done properly that is all.

-----Original Message-----
From: tom7ca [[hidden email]]
Sent: 25 October 2002 10:41
To: Multiple recipients of list
Subject: Re: Garbage collection


> I've been thinking about this a little -- the regular mark-sweep
> should be able to collect cyclic stuff, right?  So
reference-counting
> is sort of an incremental collector for non-cyclic structures.  The
> great thing about reference counting is that it's simple and easy to
> understand.  Has David posted his patch publically?

Reference counting is not "incremental" in any interesting
sense: there is no bound on the number of blocks freed by any single
assignment.  In fact, the same is true even for completely manual
storage management: calling "free" is not a constant time operation,
so even if you move to more complicated reference counting schemes,
you still lose.

I really don't understand this infatuation with reference counting:
it's inefficient on the average, it does not guarantee bounded
latency, and it leaks storage in the presence of circular structures.
 Implementing it right is a lot of work and it infects every single
piece of C code with error prone operations.  And, unlike garbage
collection, where you have to worry about GC pauses only when you
allocate something new, reference counting may hit you with memory
management pauses on any assignment.

If you want soft or hard real-time response for dynamic memory
allocation, well-implemented garbage collectors are not only
convenient, they are pretty much your only choice.  Anything else may
appear to work most of the time, but it doesn't guarantee anything.
It would be great for Lua to get a real-time or soft real-time or
incremental GC.  Until then, paying a little attention to when you
allocate storage, using storage pools, and invoking the garbage
collector frequently when your process is idle probably will work just
as well as reference counting, if not better.

Tom.

Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

tom7ca
> No need to get religious. M&S may be appropriate for you but not for
> problems like ours. We have no idle time. 

As I said, the current Lua collector may well not work for you. 
So, something needs to be done.  The question is: what?

> Reference counting spreads the collection hit. 

The problem is that it doesn't in general.  Reference
counting can give you worse collection hits than even
Lua's simple garbage collector, because a single assignment
can result in very large numbers of objects becoming
unreferenced.

If you need real-time performance or soft real-time performance,
the way to do it is to implement a real-time or soft real-time
memory manager.  But reference counting isn't one of those, 
and implementing it for that purpose is a waste of time.

Implementing a real-time or soft real-time garbage collector
isn't all that hard.  Why not just solve the problem and
do things right?





Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

Thatcher Ulrich
On Oct 27, 2002 at 04:35 -0000, tom7ca wrote:
> > No need to get religious. M&S may be appropriate for you but not for
> > problems like ours. We have no idle time. 
> 
> As I said, the current Lua collector may well not work for you. 
> So, something needs to be done.  The question is: what?
> 
> > Reference counting spreads the collection hit. 
> 
> The problem is that it doesn't in general.  Reference
> counting can give you worse collection hits than even
> Lua's simple garbage collector, because a single assignment
> can result in very large numbers of objects becoming
> unreferenced.

A couple observations:

1) David's reference-counting system collects incrementally, based on
   what he's said so far.  So it's not true, as far as I can tell,
   that his system can cause bad collection hits.

2) You are correct that the traditional reference-counting approach
   (delete an object when its last ref is released) can potentially
   cause huge chains of objects to be deleted.  I.e., this is the case
   when you have a large tree of objects, which is rooted at a single
   global variable, and you set that variable to nil.  However,
   whether this is actually a problem is definitely application- and
   program-dependent.  In the specific case of game development,
   traditional reference counting is very common in C++ engines, and
   very effective (in my experience).  The "bad collection hit" tends
   to occur exactly where you want it to: when you're trashing the old
   "level" (i.e. big chunk of game content), and getting ready to load
   the next one.

   If this is actually a problem in practice, it's very easy to fix:
   just put unreferenced objects on a "garbage list", to be freed
   incrementally.

> If you need real-time performance or soft real-time performance,
> the way to do it is to implement a real-time or soft real-time
> memory manager.  But reference counting isn't one of those, 
> and implementing it for that purpose is a waste of time.

Well, in the specific case of game development, based on my experience
and discussions with other game developers, I think you're giving bad
and unfounded advice here.  If you have real-world experience to the
contrary, I'm all ears.

The real-time requirements of game programs may not fall squarely
under your definitions of hard or soft real-time.  I wrote some notes
about it here:

http://lua-users.org/wiki/GarbageCollectionInRealTimeGames

(I just added the last note, about reference counting.)

> Implementing a real-time or soft real-time garbage collector
> isn't all that hard.  Why not just solve the problem and
> do things right?

Well, it's not trivial, either.  But PaulV posted a patch that does
incremental mark-and-sweep.  See archives for a link.  However, it
still needs some bug-fixing.  I think it would be great if people
tried this patch and helped fix the bugs.

On the other hand, the average game developer might be more likely to
adopt a reference-counting approach, for two main reasons 1) it's
straightforward and familiar to many game programmers (so they
understand the tradeoffs, and what bugs look like), and 2) it's more
deterministic, so bugs in the GC tend to be easier to find and fix.

-- 
Thatcher Ulrich
http://tulrich.com

Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

tom7ca
> Well, in the specific case of game development, based on my
experience
> and discussions with other game developers, I think you're giving
bad
> and unfounded advice here.

I'm not aware of having given advice, let alone "bad and
unfounded advice.  I don't really care what you do in your
programs.  All I pointed out is that reference counting
is not real-time, while a real-time garbage collector
(by definition) is.  It's actually worse than that: anything 
that calls malloc or free fails to be real-time (or even soft 
real-time) because the C allocator makes no guarantees about 
latency.

> If you have real-world experience to the
> contrary, I'm all ears.

You have probably had the same experience but not thought
about it: programs that inexplicably pause for several seconds
after you Quit them, games that take forever to go from one
level to the next, games that crash after replaying the same
level several times, games that stutter, games that spew out pages
of messages about reference counts not being zero, etc.
Those are often consequences of various reference
counting schemes, and they are completely avoidable.

And that isn't even counting the less tangible consequences
of reference counting: obscure design decisions in an effort
to avoid circular references, unecessarily
high hardware requirements to make up for the overhead, etc.

> On the other hand, the average game developer might be more likely
to
> adopt a reference-counting approach, for two main reasons 1) it's
> straightforward

I think the sorry reliability of gaming software is actually a good 
illustration that this is not "straightforward" at all for game
developers and that game developers would do well to re-think
their approach.

> 2) it's more
> deterministic, so bugs in the GC [presumably, you mean 
> reference counting] tend to be easier to find and fix.

That may or may not be true for C code.  But using
reference counting for Lua objects introduces the possibility
of leaks where previously you had reliable and correct
memory management.  That does not seem like a step forward.

Overall, my point is this.  Allowing for reference counting
in Lua just constrains the implementation further, and it
doesn't solve the real-time allocation problem.  And reference
counting is certainly not a good default allocation strategy
for Lua because it's inefficient and a pain to use from a C API.
Reference counting is probably the worst part of, for example,
the Python implementation.  Hard as it may be, if Lua is
to be used for (soft) real-time problems, I think it's better
to solve the problem correctly: fix the incremental collector
or implement a hard real-time collector.

Tom.


Reply | Threaded
Open this post in threaded view
|

RE: Garbage collection

David Bhowmik
In reply to this post by David Bhowmik
>> It's actually worse than that: anything 
>> that calls malloc or free fails to be real-time (or even soft 
>> real-time) because the C allocator makes no guarantees about 
>> latency.

I am not too sure of your point here. To me memory management refers to the
allocation and deallocation of memory blocks for use by your program,
whereas garbage collection refers to knowing when the blocks are not being
used by the program any more and can be collected. Garbage collection and
memory management are not the same thing. To illustrate, we have replaced
luaM_realloc() with our own memory manager that mallocs pools of lua data
structures on start up and frees the entire pool on program close down. Our
own user data types are also under control of such a memory manager. There
is no mallocing and freeing going on while the program runs. We are also
using a pseudo reference counting system, that collects incrementally so
there is no hit for chained objects. 

This sort of practice is common in much real-time software not just games. I
find it quite sophistical to imply that bugs and latencies in games are due
to the garbage collection systems when your judgement is based only on
superficial phenomenal evidence. As mentioned before, the only real issue
with reference counting systems is circular references. On this last matter
I more that accept your criticisms of the technique.

Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

Russell Y. Webb
The issue of garbage collectors is very interesting --- there are so many variations and trade-offs.

Personally, I think the best (and most Lua-like) solution is to make the garbage collector completely modular with a published way to redefine it with appropriate hooks (many of which can be empty) to define most any scheme. Then Lua should stick with it's current garbage collector in the interest of simplicity and small code size, while allowing a range of alternate solutions to flourish via a supported API (right now it's fairly modular, but that modularity is not supported or possible to replace without touching the source).

Of course the problem that arises will be, can efficiency and abstraction both be achieved in the API? One might have to resort to a redefinable lua_gc_data structure (for reference counts, marks, etc) that is part of every object which the garbage collector defines and only the garbage collector knows how to look inside of, since having the garbage collector maintain information in separate tables is inefficient for some models.

Russ


Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

Basile STARYNKEVITCH
>>>>> "Russell" == Russell Y Webb <[hidden email]> writes:

    Russell> The issue of garbage collectors is very interesting ---
    Russell> there are so many variations and trade-offs.

    Russell> Personally, I think the best (and most Lua-like) solution
    Russell> is to make the garbage collector completely modular with
    Russell> a published way to redefine it with appropriate hooks
    Russell> (many of which can be empty) to define most any scheme. [...]

I skipped most of Russell's (interesting) message 

Even if I do share this wish, I am not sure it is achievable in
practical terms.

For instance, if you wanted to use a generational copying GC in Lua
(which updates any pointer by copying live objects, and then free the
old region at once...) you'll have to

1. declare each object parameter and each object local variable

2. notify of each update within a Lua object.

(Lua objects here mean anything the GC has to take care of).

However, I do wish that Lua uses a different GC (or perhaps several
ones, configurable at compile-time), perhaps a generational copying
GC.

For people interested, I actually did implement a generational copying
GC for C which could perhaps be used in Lua. See
http://starynkevitch.net/Basile/qishintro.html for details.  You can
download the latest (unreleased) snapshot from
http://starynkevitch.net/Basile/qish-0.4pre5.tar.gz

More generally, changing the GC may requires change to the C API of
lua.


Regards.
-- 

Basile STARYNKEVITCH         http://starynkevitch.net/Basile/ 
email: basile<at>starynkevitch<dot>net 
alias: basile<at>tunes<dot>org 
8, rue de la Faïencerie, 92340 Bourg La Reine, France

Reply | Threaded
Open this post in threaded view
|

RE: Garbage Collection

Nick Trout-5
In reply to this post by David Bhowmik

> Everybody refers to reference counting as
> though it cannot catch cyclic structures.
> Rafael Lins, whom I believe is now in the
> Departamento de Electronica e Sistemas at
> the Universidade de Pernambuco, produced
> some beautiful gc reference counting
> algorithms that do catch cyclic structures.
> See "Cyclic Reference Counting with Lazy
> Mark-Scan", UKC Technical Report 75
> (1991). 

Well it can't, hence you have to use another algorithm to catch the
cyclic references!

I put the paper up on the wiki in PDF if anyone would like to read it:
(I assumed PDF is everyones format of choice).

http://lua-users.org/wiki/GarbageCollection

http://lua-users.org/files/wiki_insecure/gc/lins90cyclic.pdf




Reply | Threaded
Open this post in threaded view
|

Re: Garbage collection

Thatcher Ulrich
In reply to this post by tom7ca
On Oct 29, 2002 at 02:53 -0000, tom7ca wrote:
> [snip]

I think David answered your previous points better than I can; I just
want to pick up on the API issue...

> And reference counting is certainly not a good default allocation
> strategy for Lua because it's inefficient and a pain to use from a C
> API.  Reference counting is probably the worst part of, for example,
> the Python implementation.

OK, that may well be true; I haven't used the Python API.

But, it seems to me that the existing Lua reference-locking API is
completely agnostic about how the internal Lua GC operates.  See:

http://www.lua.org/manual/manual.html#5.14

Basically, a C program declares that it is interested in a particular
object, using the lua_ref() call.  lua_ref() returns a integer handle,
for use in retrieving the reference.  The C program calls lua_getref()
with the handle, to put the physical reference to the object on the
Lua stack.  When the C program no longer needs access to that object,
it frees the handle using lua_unref().

No details about the underlying GC implementation are exposed; ref
counting can work just as well as anything else behind this interface.

-- 
Thatcher Ulrich
http://tulrich.com

Reply | Threaded
Open this post in threaded view
|

Unsubscribe

brian knudsen

-----Oprindelig meddelelse-----
Fra: [hidden email]
[[hidden email]] På vegne af Thatcher Ulrich
Sendt: 29. oktober 2002 22:14
Til: Multiple recipients of list
Emne: Re: Garbage collection


On Oct 29, 2002 at 02:53 -0000, tom7ca wrote:
> [snip]

I think David answered your previous points better than I can; I just
want to pick up on the API issue...

> And reference counting is certainly not a good default allocation 
> strategy for Lua because it's inefficient and a pain to use from a C 
> API.  Reference counting is probably the worst part of, for example, 
> the Python implementation.

OK, that may well be true; I haven't used the Python API.

But, it seems to me that the existing Lua reference-locking API is
completely agnostic about how the internal Lua GC operates.  See:

http://www.lua.org/manual/manual.html#5.14

Basically, a C program declares that it is interested in a particular
object, using the lua_ref() call.  lua_ref() returns a integer handle,
for use in retrieving the reference.  The C program calls lua_getref()
with the handle, to put the physical reference to the object on the Lua
stack.  When the C program no longer needs access to that object, it
frees the handle using lua_unref().

No details about the underlying GC implementation are exposed; ref
counting can work just as well as anything else behind this interface.

-- 
Thatcher Ulrich
http://tulrich.com


12