GC order

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

GC order

Bilyk, Alex
Lua5 manual states that user data objects are collected in the order reverse to that of their creation. It, however, doesn't say anything about the order of GC in general. Hence, given two arbitrary Lua objects O1 and O2, can assumption be made that O1 is destroyed after O2 if it was created before O2 and vice versa?

Another question I have is about GC in weak tables. Given a weak table with both keys and values being weak, is there any specific order in which a key is collected with respect to its value?

Also, assuming objects are collected in a specific order in Lua 5, is this likely to change in future versions of Lua? 

For the moment I make no assumptions on the order at which objects and key/values are destroyed, but, I wish I could make one:)

Thank you,
Alex 

Reply | Threaded
Open this post in threaded view
|

GC order

Basile STARYNKEVITCH
>>>>> "Bilyk," == Bilyk, Alex <[hidden email]> writes:

    Bilyk,> Lua5 manual states that user data objects are collected in
    Bilyk,> the order reverse to that of their creation. It, however,
    Bilyk,> doesn't say anything about the order of GC in
    Bilyk,> general. Hence, given two arbitrary Lua objects O1 and O2,
    Bilyk,> can assumption be made that O1 is destroyed after O2 if it
    Bilyk,> was created before O2 and vice versa?


Even if the current implementation enforces this, I think that you
should not expect this in all cases. Imagine another Lua
implementation (and such beast exist, e.g. the lua interpeter coded
in Ocaml inside QuickC-- see www.cminusminus.org for more). Then it
probably won't have the same destruction order than the original Lua.

In GC-ed implementations, destructions can occur at any time (or even
not at all: consider an execution so quick that no GC is needed at
all!)

-- 

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

Reply | Threaded
Open this post in threaded view
|

Re: GC order

Roberto Ierusalimschy
In reply to this post by Bilyk, Alex
> For the moment I make no assumptions on the order at which objects and
> key/value s are destroyed, but, I wish I could make one:)

What assumptions do you wish?

-- Roberto

Reply | Threaded
Open this post in threaded view
|

RE: GC order

Bilyk, Alex
In reply to this post by Bilyk, Alex
1. Lua objects are collected in the order exactly reverse to the order of their creation.
2. In weak tables with both keys and values being weak a key gets collected prior to its value or in reverse but always the same way regardless of their object types. 

Alex

 -----Original Message-----
From: 	Roberto Ierusalimschy [[hidden email]] 
Sent:	Wednesday, May 07, 2003 12:34 PM
To:	Multiple recipients of list
Subject:	Re: GC order 

> For the moment I make no assumptions on the order at which objects and
> key/value s are destroyed, but, I wish I could make one:)

What assumptions do you wish?

-- Roberto


Reply | Threaded
Open this post in threaded view
|

RE: GC order

RLak
In reply to this post by Bilyk, Alex
Alex Bilyk escribió:

> 1. Lua objects are collected in the order exactly reverse to the order of
their creation.

That strikes me as being unreasonably rigid; it would severely restrict
options for efficient garbage collection. In particular, implementing Lua
on top of a system which already features garbage collection may not be
possible, or at least it may not be possible to take advantage of native
garbage collection.

In any case, I cannot think of a good reason for this requirement. I
suspect that what you actually want is for userdata finalisation to be
called in the reverse order to creation; that is documented as current Lua
behaviour. Since you cannot put __gc methods on Lua objects other than
userdata, the order of destruction of non-userdata objects is irrelevant.

> 2. In weak tables with both keys and values being weak a key gets
collected
> prior to its value or in reverse but always the same way regardless of
their object types.

This requirement is unclear. What if an object is both a key and a value of
different weak tables (or even the same weak table)? What if this
requirement contradicts requirement 1? Which takes priority?

Again, I suspect you are looking for something different: the requirement
is likely to be that the key is deleted from the table before the value (or
vice versa), and when that happens with respect to running finalisers. It
is clear that every object must be deleted from every weak table prior to
the object actually being reaped, but it may or may not be deleted prior to
being finalised.

-----

Finalisers are controversial in every garbage collection system; there are
too many implementation options and the precise choice taken can affect
program behaviour in very subtle ways. My rule of thumb is that if a
finaliser depends on such implementation decisions, the program design
needs to be looked at again three times.

Objects with finalisers are in a sort of limbo after being collected; they
still exist but they are in heaven's antechamber, as it were. The finaliser
runs in a sort of grey world filled with phantoms; it has access to objects
not visible to the naked eye. In this curious world, objects can disappear
without notice; but they can also be resurrected and given a new lease of
life. I think that what you are looking for is to put a bit of order in
this murky reality, but one must always take care when moving through the
netherworld.

In any event, the current Lua implementation appears to be the following:

1) unmarked weak values are deleted from both weak-value and weak-key-value
tables.
2) finalisers are run on deletable userdata with finalisers (i.e. __gc
metamethods) in reverse creation order.
3) all weak tables have all deletable nodes removed. (i.e. <key,value>
pairs where either the key or the value is nil, or the key or value is weak
and unmarked.)
4) all deletable objects are actually deallocated. (Note: an object which
was finalised at step 2 is not deletable at this point. It will be
deletable on the next GC cycle if it was not resurrected. This is also true
of the strong partner of a weak member of a weak-table node; this latter
fact can create memory leaks.)

I believe that any order for steps (1), (2), and (3) could have been
chosen; the only difference it makes is the number of phantoms available to
finalisers. I don't suppose that it would be problematic for the Lua
specification to choose and document one particular order, but it hasn't.

For what it's worth, I think I would have chosen order (2), (1;3), which
seems to be slightly more predictable, and possibly more useful than (1;3),
(2). (steps 1 and 3 can be done simultaneously if step 2 doesn't
intervene.) But as I said, relying on this particular behaviour is likely
to end in tears.

I would also have thought that, since only userdata can have finalisers,
that an API lua_setfinaliser(L, <userdata>) would be easier for both Lua
and Lua-integrators alike, and more efficient as well. Perhaps that could
be considered for Lua 5.1

Rici







Reply | Threaded
Open this post in threaded view
|

compiling lua with dev-cpp (gcc 3.2)

Milo Spirig
Hi

Im trying to compile LUA 5.0 as a static library with dev-cpp (gcc 3.2)
under Windows. I added all the files from the src und src/lib directory to
the project und compiled it. Then I linked this library to my test project
und compiled again, but now I'm getting a linker error for all the lua calls
like:


[Linker error] undefined reference to `lua_open'

../src/ai_lua.o(.text$get_registry__Q37luabind6detail14class_registryP9lua_S
tate+0x25):ai_lua.cpp: undefined reference to `lua_gettable'

 
../src/ai_lua.o(.text$stage1__Q37luabind6detail12create_classP9lua_State+0x1
0):ai_lua.cpp: undefined reference to `lua_gettop'

../src/ai_lua.o(.text$is_class_object__Q27luabind6detailP9lua_Statei+0x7e):a
i_lua.cpp: undefined reference to `lua_settop'

...

(and I'm sure I linked the library correctly)

Can anybody help me? 

thanks
Milo


Reply | Threaded
Open this post in threaded view
|

RE: GC order

Bilyk, Alex
In reply to this post by Bilyk, Alex
Thanks,

As I said I didn't make any assumptions on the order in my code but was wondering if garbage collection has any other rules similar to that on the order of user data collection. Your response clearly indicates that no other rules can be assumed and/or used for making code dependant on them. The thing I wanted to do is this (still want but not as much). Given a co-routine I would like to associate a user data object with it that would get collected before the co-routine itself does. In other words, given a co-routine with no outstanding references to it I would like for some designated user data get garbage collected/finalized before the co-routine itself does. 

Alex

 -----Original Message-----
From: 	[hidden email] [[hidden email]] 
Sent:	Thursday, May 08, 2003 9:40 AM
To:	Multiple recipients of list
Subject:	RE: GC order


[chop-chop]
-----

Finalisers are controversial in every garbage collection system; there are
too many implementation options and the precise choice taken can affect
program behaviour in very subtle ways. My rule of thumb is that if a
finaliser depends on such implementation decisions, the program design
needs to be looked at again three times.

Totally agree.

Objects with finalisers are in a sort of limbo after being collected; they
still exist but they are in heaven's antechamber, as it were. The finaliser
runs in a sort of grey world filled with phantoms; it has access to objects
not visible to the naked eye. In this curious world, objects can disappear
without notice; but they can also be resurrected and given a new lease of
life. I think that what you are looking for is to put a bit of order in
this murky reality, but one must always take care when moving through the
netherworld.

In any event, the current Lua implementation appears to be the following:

1) unmarked weak values are deleted from both weak-value and weak-key-value
tables.
2) finalisers are run on deletable userdata with finalisers (i.e. __gc
metamethods) in reverse creation order.
3) all weak tables have all deletable nodes removed. (i.e. <key,value>
pairs where either the key or the value is nil, or the key or value is weak
and unmarked.)
4) all deletable objects are actually deallocated. (Note: an object which
was finalised at step 2 is not deletable at this point. It will be
deletable on the next GC cycle if it was not resurrected. This is also true
of the strong partner of a weak member of a weak-table node; this latter
fact can create memory leaks.)

I believe that any order for steps (1), (2), and (3) could have been
chosen; the only difference it makes is the number of phantoms available to
finalisers. I don't suppose that it would be problematic for the Lua
specification to choose and document one particular order, but it hasn't.

For what it's worth, I think I would have chosen order (2), (1;3), which
seems to be slightly more predictable, and possibly more useful than (1;3),
(2). (steps 1 and 3 can be done simultaneously if step 2 doesn't
intervene.) But as I said, relying on this particular behaviour is likely
to end in tears.

I would also have thought that, since only userdata can have finalisers,
that an API lua_setfinaliser(L, <userdata>) would be easier for both Lua
and Lua-integrators alike, and more efficient as well. Perhaps that could
be considered for Lua 5.1

Rici








Reply | Threaded
Open this post in threaded view
|

Re: GC order

Roberto Ierusalimschy
In reply to this post by RLak
> Since you cannot put __gc methods on Lua objects other than userdata,
> the order of destruction of non-userdata objects is irrelevant.

They are more than irrelevant; they are undetectable. Lua has no way
to know when an object without a _gc method is collected. So, you
can implement the collection for those objects in any order you want,
without breaking the specification.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

RE: compiling lua with dev-cpp (gcc 3.2)

Nick Trout
In reply to this post by Milo Spirig
> Im trying to compile LUA 5.0 as a static library with dev-cpp 
> (gcc 3.2) under Windows. I added all the files from the src 
> und src/lib directory to the project und compiled it. Then I 
> linked this library to my test project und compiled again, 
> but now I'm getting a linker error for all the lua calls
> like:

http://lua-users.org/wiki/LuaFaq
http://lua-users.org/wiki/BuildingLua
http://lua-users.org/lists/lua-l/2000-11/msg00006.html
http://lua-users.org/lists/lua-l/2000-11/msg00004.html
http://lua-users.org/lists/lua-l/2002-09/msg00046.html


Reply | Threaded
Open this post in threaded view
|

RE: GC order

Nick Trout
In reply to this post by Bilyk, Alex
> Alex Bilyk escribió:
> 
> > 1. Lua objects are collected in the order exactly reverse 
> to the order 
> > of
> their creation.
> 
RL> That strikes me as being unreasonably rigid; it would 
> severely restrict options for efficient garbage collection. 
> In particular, implementing Lua on top of a system which 
> already features garbage collection may not be possible, or 
> at least it may not be possible to take advantage of native 
> garbage collection.

I agree with Rici. We should not be imposing restrictions on the way
garbage collection works at this point in time (since it's the major
refactoring in Lua 5.1). Above all I want an *efficient* garbage
collection implementaion - just search the archives for similar voices.
An incremental garbage collection routine (with generational
optimisation?! ;-D ) is difficult enough to write without imposing
potentially project specific restrictions on GC. In a previous post I
made the point that garbage collection is not a magical catch all. If
you're relying on the _implementation_ of GC to tidy up your application
then the solution could most likely be improved. Lets keep Lua clean and
simple please.

Regards,
Nick


Reply | Threaded
Open this post in threaded view
|

Re: GC order

Roberto Ierusalimschy
In reply to this post by Bilyk, Alex
> Given a co-routine I would like to associate a user data object with it
> that would get collected before the co-routine itself does. In other
> words, given a co-routine with no outstanding references to it I would
> like for some designated user data get garbage collected/finalized
> before the co-routine itself does.

You can do that. First, you must store the userdata in the coroutine
(e.g., in its stack, or in its global table, if it has a separated
global table). So, the userdata cannot be collected before the coroutine.

Then, you must store an entry (userdata -> coroutine) in a table with
weak keys (but strong values). That entry will not prevent the userdata
from being collected. The main point here is that a weak key is only
cleared *after* its __gc method runs. That means that, when the __gc
method runs, you still can safely retrieve the coroutine from this
table. (This is not by chance; it is the reason why weak keys are
only cleared after running the __gc methods).

-- Roberto

Reply | Threaded
Open this post in threaded view
|

RE: GC order

Nick Trout
In reply to this post by Bilyk, Alex
AB> As I said I didn't make any assumptions on the order in my 
> code but was wondering if garbage collection has any other 
> rules similar to that on the order of user data collection. 
> Your response clearly indicates that no other rules can be 
> assumed and/or used for making code dependant on them. The 
> thing I wanted to do is this (still want but not as much). 
> Given a co-routine I would like to associate a user data 
> object with it that would get collected before the co-routine 
> itself does. In other words, given a co-routine with no 
> outstanding references to it I would like for some designated 
> user data get garbage collected/finalized before the 
> co-routine itself does. 


Could you use a mechanism like this?

function thingUpdate(object)
  while true do
    if not updateObject(object) then
      object:delete()
      object = nil
      return
    end
    coroutine.yield()
  end
end

....

obj = createObject("type")
coroutine.create(thingUpdate, obj)

We are not using GC to delete user data, we delete it explicitly. Lua
will delete the user data object which wraps the pointer to your
"object", and the coroutine, in its own time in no specific order. You
can't expect Lua to do your user object management in specific ways
using GC as pointed out in other posts. You'll either have to do it
explicitly or put in some sort of object management layer. This should
work for light or full userdata.

I'm assuming you have some sort of destructor code in the object which
must be called before the coroutine ends (e.g. to detach itself from
some lists?). It sounds like you gave the GC metamethod wired up to call
this. I think Ricis posts discusses the pros and cons of this approach.
If this is the case it should probably be removed and an explicit
delete() called instead.

It would be nice to think that data we give to Lua to manage will be
collected in certain ways but this can quickly become application
specific. I appreciate the order of user data deletion is ordered but
when things are mixed you lose this property. Its best to think of
garbage collection as things disappearing off the radar, rather than
forming an orderly queue to get deleted. I have probably missed
something as I don't really understand why you require 2 collection
cycles to delete these two objects.

/Nick



Reply | Threaded
Open this post in threaded view
|

Re: GC order

RLak
In reply to this post by Bilyk, Alex
> You can do that. First, you must store the userdata in the coroutine
> (e.g., in its stack, or in its global table, if it has a separated
> global table). So, the userdata cannot be collected before the coroutine.

> Then, you must store an entry (userdata -> coroutine) in a table with
> weak keys (but strong values). That entry will not prevent the userdata
> from being collected. The main point here is that a weak key is only
> cleared *after* its __gc method runs. That means that, when the __gc
> method runs, you still can safely retrieve the coroutine from this
> table. (This is not by chance; it is the reason why weak keys are
> only cleared after running the __gc methods).

Sorry, Roberto, but that won't work. I have pointed this out a few times.

The weak table has a strong reference to the coroutine. Strong references
are marked and traversed. The coroutine has a reference to the userdata. So
the userdata is marked. So the reference to the coroutine is never deleted
from the weak table. Consequently neither the coroutine nor the userdata
will ever get collected.

See <http://lua-users.org/wiki/GarbageCollectingWeakTables>

gentoo lua-5.0 # bin/lua
Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> -- Create an object b
> b = {}
> -- Create a which refers to b
> a = {b}
> -- create a weaktable in which b points to a
> weak = setmetatable({}, {__mode = "k"})
> weak[b] = a
> -- Get rid of the only references to a and b other than the weak one
> a, b = nil, nil
> -- what's in the table?
> table.foreach(weak, print)
table: 0x8069e38        table: 0x806a0b8
> -- garbage collect a few times
> collectgarbage()
> collectgarbage()
> collectgarbage()
> collectgarbage()
> -- what's in the table?
> table.foreach(weak, print)
table: 0x8069e38        table: 0x806a0b8



Reply | Threaded
Open this post in threaded view
|

Re: GC order

Roberto Ierusalimschy
> Sorry, Roberto, but that won't work. I have pointed this out a few times.
> [...]

 Yes, you are right. So the only solution is to "lock" the coroutine in
the metatable of the userdata...

-- Roberto

Reply | Threaded
Open this post in threaded view
|

AW: compiling lua with dev-cpp (gcc 3.2)

Milo Spirig
In reply to this post by Nick Trout
Thanks, I could finally find the problem, the compiler was missing some
flags to compile strictly c-code.

cu
Milo

-----Ursprüngliche Nachricht-----
Von: [hidden email] [[hidden email]]
Im Auftrag von Nick Trout
Gesendet: Donnerstag, 8. Mai 2003 20:17
An: Multiple recipients of list
Betreff: RE: compiling lua with dev-cpp (gcc 3.2)



> Im trying to compile LUA 5.0 as a static library with dev-cpp
> (gcc 3.2) under Windows. I added all the files from the src 
> und src/lib directory to the project und compiled it. Then I 
> linked this library to my test project und compiled again, 
> but now I'm getting a linker error for all the lua calls
> like:

http://lua-users.org/wiki/LuaFaq http://lua-users.org/wiki/BuildingLua
http://lua-users.org/lists/lua-l/2000-11/msg00006.html
http://lua-users.org/lists/lua-l/2000-11/msg00004.html
http://lua-users.org/lists/lua-l/2002-09/msg00046.html



Reply | Threaded
Open this post in threaded view
|

Re: compiling lua with dev-cpp (gcc 3.2)

Asko Kauppi-3
In reply to this post by Milo Spirig

Might be you compiled the library as C++ but still use 'extern "C"' to access it? The fact that DevCpp treats any '*.C' files (with uppercase suffix) automatically as C++ source does not help here. I hope they didn't but they seem fixed doing so.

So: change names to lowercase, ensure you compile/link either as ANSI C (i'd recommend) or C++.

-ak


Milo Spirig kirjoittaa torstaina, 8. toukokuuta 2003, kello 20:03:

Hi

Im trying to compile LUA 5.0 as a static library with dev-cpp (gcc 3.2)
under Windows. I added all the files from the src und src/lib directory to the project und compiled it. Then I linked this library to my test project und compiled again, but now I'm getting a linker error for all the lua calls
like:


[Linker error] undefined reference to `lua_open'

../src/ ai_lua.o(.text$get_registry__Q37luabind6detail14class_registryP9lua_S
tate+0x25):ai_lua.cpp: undefined reference to `lua_gettable'


../src/ ai_lua.o(.text$stage1__Q37luabind6detail12create_classP9lua_State+0x1
0):ai_lua.cpp: undefined reference to `lua_gettop'

../src/ ai_lua.o(.text$is_class_object__Q27luabind6detailP9lua_Statei+0x7e):a
i_lua.cpp: undefined reference to `lua_settop'

...

(and I'm sure I linked the library correctly)

Can anybody help me?

thanks
Milo



Reply | Threaded
Open this post in threaded view
|

RE: GC order

Bilyk, Alex
In reply to this post by Bilyk, Alex
OK,
I think I have all the answers I needed. I am using IDs to identify co-routines, which gives me full control over their life time as far the application code is concerned. 

By the way, why not to use object reference counts and base garbage collection on these. As soon as the ref count goes to 0 there is no doubt the object can be collected and it's very easy to write GC incremental or not. Granted, Lua will be a notch slower and perhaps lager but how much slower I wonder? Every time a new reference to the object is created the count goes 1 up. Every time the reference being removed the count goes 1 down. Removing items off the stack would be suffering the most I would guess. I am just wondering if you have ever considered this as an option for Lua's GC.

Thanks you,
Alex.

 -----Original Message-----
From: 	[hidden email] [[hidden email]] 
Sent:	Thursday, May 08, 2003 1:07 PM
To:	Multiple recipients of list
Subject:	Re: GC order


> You can do that. First, you must store the userdata in the coroutine
> (e.g., in its stack, or in its global table, if it has a separated
> global table). So, the userdata cannot be collected before the coroutine.

> Then, you must store an entry (userdata -> coroutine) in a table with
> weak keys (but strong values). That entry will not prevent the userdata
> from being collected. The main point here is that a weak key is only
> cleared *after* its __gc method runs. That means that, when the __gc
> method runs, you still can safely retrieve the coroutine from this
> table. (This is not by chance; it is the reason why weak keys are
> only cleared after running the __gc methods).

Sorry, Roberto, but that won't work. I have pointed this out a few times.

The weak table has a strong reference to the coroutine. Strong references
are marked and traversed. The coroutine has a reference to the userdata. So
the userdata is marked. So the reference to the coroutine is never deleted
from the weak table. Consequently neither the coroutine nor the userdata
will ever get collected.

See <http://lua-users.org/wiki/GarbageCollectingWeakTables>

gentoo lua-5.0 # bin/lua
Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> -- Create an object b
> b = {}
> -- Create a which refers to b
> a = {b}
> -- create a weaktable in which b points to a
> weak = setmetatable({}, {__mode = "k"})
> weak[b] = a
> -- Get rid of the only references to a and b other than the weak one
> a, b = nil, nil
> -- what's in the table?
> table.foreach(weak, print)
table: 0x8069e38        table: 0x806a0b8
> -- garbage collect a few times
> collectgarbage()
> collectgarbage()
> collectgarbage()
> collectgarbage()
> -- what's in the table?
> table.foreach(weak, print)
table: 0x8069e38        table: 0x806a0b8




Reply | Threaded
Open this post in threaded view
|

RE: GC order

Nick Trout
In reply to this post by Bilyk, Alex

> By the way, why not to use object reference counts and base 
> ...
> I am just wondering if you have ever 
> considered this as an option for Lua's GC.

I swapped from Python to Lua for embedding because of reference counting
;-). There was a discussion about this a while back if you have a look
through lua-l. Someone even patched Lua 4 to use ref counting. A couple
of reasons are: cyclic referencing stops collection, and reference
counting user objects is more erroneous. Mark and sweep is simple and
avoids both these problems.

/Nick


Reply | Threaded
Open this post in threaded view
|

RE: GC order

Nijdam
In reply to this post by Bilyk, Alex
Most reference based systems suffer from circularity problems and require careful consideration from the "user" of the components.

-men

At 13:52 5/8/2003 -0700, you wrote:
OK,
I think I have all the answers I needed. I am using IDs to identify co-routines, which gives me full control over their life time as far the application code is concerned.

By the way, why not to use object reference counts and base garbage collection on these. As soon as the ref count goes to 0 there is no doubt the object can be collected and it's very easy to write GC incremental or not. Granted, Lua will be a notch slower and perhaps lager but how much slower I wonder? Every time a new reference to the object is created the count goes 1 up. Every time the reference being removed the count goes 1 down. Removing items off the stack would be suffering the most I would guess. I am just wondering if you have ever considered this as an option for Lua's GC.

Thanks you,
Alex.

 -----Original Message-----
From:   [hidden email] [[hidden email]]
Sent:   Thursday, May 08, 2003 1:07 PM
To:     Multiple recipients of list
Subject:        Re: GC order


> You can do that. First, you must store the userdata in the coroutine
> (e.g., in its stack, or in its global table, if it has a separated
> global table). So, the userdata cannot be collected before the coroutine.

> Then, you must store an entry (userdata -> coroutine) in a table with
> weak keys (but strong values). That entry will not prevent the userdata
> from being collected. The main point here is that a weak key is only
> cleared *after* its __gc method runs. That means that, when the __gc
> method runs, you still can safely retrieve the coroutine from this
> table. (This is not by chance; it is the reason why weak keys are
> only cleared after running the __gc methods).

Sorry, Roberto, but that won't work. I have pointed this out a few times.

The weak table has a strong reference to the coroutine. Strong references
are marked and traversed. The coroutine has a reference to the userdata. So
the userdata is marked. So the reference to the coroutine is never deleted
from the weak table. Consequently neither the coroutine nor the userdata
will ever get collected.

See <http://lua-users.org/wiki/GarbageCollectingWeakTables>

gentoo lua-5.0 # bin/lua
Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> -- Create an object b
> b = {}
> -- Create a which refers to b
> a = {b}
> -- create a weaktable in which b points to a
> weak = setmetatable({}, {__mode = "k"})
> weak[b] = a
> -- Get rid of the only references to a and b other than the weak one
> a, b = nil, nil
> -- what's in the table?
> table.foreach(weak, print)
table: 0x8069e38        table: 0x806a0b8
> -- garbage collect a few times
> collectgarbage()
> collectgarbage()
> collectgarbage()
> collectgarbage()
> -- what's in the table?
> table.foreach(weak, print)
table: 0x8069e38        table: 0x806a0b8


Reply | Threaded
Open this post in threaded view
|

RE: GC order

Bilyk, Alex
In reply to this post by Bilyk, Alex
So Lua is free of circularity problems? Does this mean that if A referred to B and B referred to A, there is a way in Lua one can somehow cause garbage-collection on either A or B? I was under impression it would have been the case where neither one would get GCed. I guess I am not sure what a circularity problem is. Hmm...

Alex.

-----Original Message-----
From: 	Marc Nijdam [[hidden email]] 
Sent:	Thursday, May 08, 2003 3:55 PM
To:	Multiple recipients of list
Subject:	RE: GC order

Most reference based systems suffer from circularity problems and require 
careful consideration from the "user" of the components.

-men

At 13:52 5/8/2003 -0700, you wrote:
>OK,
>I think I have all the answers I needed. I am using IDs to identify 
>co-routines, which gives me full control over their life time as far the 
>application code is concerned.
>
>By the way, why not to use object reference counts and base garbage 
>collection on these. As soon as the ref count goes to 0 there is no doubt 
>the object can be collected and it's very easy to write GC incremental or 
>not. Granted, Lua will be a notch slower and perhaps lager but how much 
>slower I wonder? Every time a new reference to the object is created the 
>count goes 1 up. Every time the reference being removed the count goes 1 
>down. Removing items off the stack would be suffering the most I would 
>guess. I am just wondering if you have ever considered this as an option 
>for Lua's GC.
>
>Thanks you,
>Alex.
>
>  -----Original Message-----
>From:   [hidden email] [[hidden email]]
>Sent:   Thursday, May 08, 2003 1:07 PM
>To:     Multiple recipients of list
>Subject:        Re: GC order
>
>
> > You can do that. First, you must store the userdata in the coroutine
> > (e.g., in its stack, or in its global table, if it has a separated
> > global table). So, the userdata cannot be collected before the coroutine.
>
> > Then, you must store an entry (userdata -> coroutine) in a table with
> > weak keys (but strong values). That entry will not prevent the userdata
> > from being collected. The main point here is that a weak key is only
> > cleared *after* its __gc method runs. That means that, when the __gc
> > method runs, you still can safely retrieve the coroutine from this
> > table. (This is not by chance; it is the reason why weak keys are
> > only cleared after running the __gc methods).
>
>Sorry, Roberto, but that won't work. I have pointed this out a few times.
>
>The weak table has a strong reference to the coroutine. Strong references
>are marked and traversed. The coroutine has a reference to the userdata. So
>the userdata is marked. So the reference to the coroutine is never deleted
>from the weak table. Consequently neither the coroutine nor the userdata
>will ever get collected.
>
>See <http://lua-users.org/wiki/GarbageCollectingWeakTables>
>
>gentoo lua-5.0 # bin/lua
>Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> > -- Create an object b
> > b = {}
> > -- Create a which refers to b
> > a = {b}
> > -- create a weaktable in which b points to a
> > weak = setmetatable({}, {__mode = "k"})
> > weak[b] = a
> > -- Get rid of the only references to a and b other than the weak one
> > a, b = nil, nil
> > -- what's in the table?
> > table.foreach(weak, print)
>table: 0x8069e38        table: 0x806a0b8
> > -- garbage collect a few times
> > collectgarbage()
> > collectgarbage()
> > collectgarbage()
> > collectgarbage()
> > -- what's in the table?
> > table.foreach(weak, print)
>table: 0x8069e38        table: 0x806a0b8



12