GC order

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

RE: GC order

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

They are collected as shown here:

Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> = gcinfo()
18      37
> a,b = {},{}
> a.b, b.a = b, a                    -- mutual reference
> a.string = string.rep('a', 100000)
> = gcinfo()
165     330
> b.string = string.rep('a', 100000) -- aha no duplicated strings!
> = gcinfo()
165     330
> b.string = string.rep('a', 100001)
> = gcinfo()
263     526
> collectgarbage()
> = gcinfo()
239     477
> a,b = nil,nil       -- we now have 2 unreachable tables
> = gcinfo()          -- not deleted yet
239     477
> collectgarbage()
> = gcinfo()          -- collected the island
31      61            



Reply | Threaded
Open this post in threaded view
|

RE: GC order

Bilyk, Alex
In reply to this post by Bilyk, Alex
Aha! Good to know.:) 
Thanks a lot,
AB

 -----Original Message-----
From: 	Nick Trout [[hidden email]] 
Sent:	Thursday, May 08, 2003 5:21 PM
To:	Multiple recipients of list
Subject:	RE: GC order


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

They are collected as shown here:

Lua 5.0  Copyright (C) 1994-2003 Tecgraf, PUC-Rio
> = gcinfo()
18 37

[chop-chop]


Reply | Threaded
Open this post in threaded view
|

Re: GC order

Michael T. Richter-3
In reply to this post by Nick Trout
> An incremental garbage collection routine (with generational
> optimisation?! ;-D ) is difficult enough to write without imposing
> potentially project specific restrictions on GC.

Would it be conceivable to make GC pluggable in some way?  I think part of
the problem some people may be having is that each different GC algorithm
has strengths and weaknesses and sometimes the weaknesses involve make Lua
unsuitable for their specific tasks.

For example, I find the current stop-n-go, mark/sweep algorithm just fine
for the kind of work I do.  I like it.  It's small and it does the job I
need it to do with no muss, no fuss, no bother.  Were I a game programmer,
however, I might very easily find the stop-n-go part of it to be
unacceptable.  An incremental, generational system would, indeed, be better.
On the other hand if I was doing something which required anything even
remotely hard in time requirements, even a generational system wouldn't be
that useful -- I'd be needing some form of interruptible concurrency.

I did work with one experimental Modula-3 (IIRC) environment long ago which
had this kind of pluggable GC.  It came with three different GC systems
which could be plugged into the environment and if those three weren't
suited to your purposes, you could always code your own and put it in place
yourself.  Now being an experimental system it was grotesquely inefficient
and hugely bloated, but I don't think this was a necessary trait -- it
reflected, rather, the hastily-assembled nature of the product.



Reply | Threaded
Open this post in threaded view
|

Re: GC order

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

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

OK, I finally figured out how to do this.

You need to create a proxy for the coroutine; the proxy would implement the
coroutines methods by calling the coroutine. You use the proxy instead of
the coroutine.

The proxy does not maintain a reference to the coroutine, but it does
maintain a reference to the userdata. There is a weak-keyed table from
userdata to coroutine, and the proxy uses that to find the coroutine (it
has a reference to the userdata).

Now, the only strong reference to the userdata is in the proxy, and the
only reference to the coroutine is in a weak-keyed table, where the
coroutine reference is a strong value. The userdata does not have any
references other than the weak table itself, and the coroutine has no
reference to the userdata, so there is no circular reference in the weak
table.

When the proxy is unreachable, so is the userdata and therefore its
finalisation method will run. The coroutine is also technically unreachable
but it will have been marked because it is a strong value in a weak-keyed
table, so it will still be around. The userdata can use the weak table
(using itself as a key) to access the coroutine, if it needs to. As long as
the userdata doesn't resurrect the coroutine by storing a reference to it
in some visible object, the coroutine will disappear on the next garbage
collection cycle.

Phew!

So we have something like this: (not tested)

do
  local udata2coro = setmetatable({}, {__mode = "k"})

  -- create a coroutine (proxy) and associate it with a udata
  -- all this effort will be wasted if the udata doesn't have
  -- a __gc method.

  function cocreate(fn, udata)
    local coro = co.create(fn)
    udata2coro[udata] = coro

    -- we must not reference coro anywhere in the proxy table.
    -- But the upvalue to udata is ok (even necessary)

    local proxy = {}

    -- if you knew how many arguments your coroutines wanted,
    -- you could write this more efficiently.
    function proxy:resume(...)
      return co.resume(udata2coro[udata], unpack(arg))
    end

    function proxy:status()
      return co.status(udata2coro[udata])
    end

    return proxy
  end
end

Well, that wasn't too hard. Let me know if it works.







Reply | Threaded
Open this post in threaded view
|

RE: GC order

Nick Trout
In reply to this post by Bilyk, Alex

> NT> An incremental garbage collection routine (with generational 
> > optimisation?! ;-D ) is difficult enough to write without imposing 
> > potentially project specific restrictions on GC.
> 
MR> Would it be conceivable to make GC pluggable in some way?  I 
> think part of the problem some people may be having is that 
> each different GC algorithm has strengths and weaknesses and 
> sometimes the weaknesses involve make Lua unsuitable for 
> their specific tasks.

I think this has been discussed before and I think the usual answer is:
Lua is not overly complex in implementation and therefore it's not
impossible to wire in your own solution. Also, a design goal of Lua is
simplicity. A generic interface to these mechanisms could slow Lua or
involve a major refactoring. And, even if you did write a pluggable
system, would people really (re)use it, and how reuseable would it be
between Lua versions? I suspect it would be difficult to draw some
lines.


> For example, I find the current stop-n-go, mark/sweep 
> algorithm just fine for the kind of work I do.  I like it.  
> It's small and it does the job I need it to do with no muss, 
> no fuss, no bother.  Were I a game programmer, however, I 
> might very easily find the stop-n-go part of it to be 
> unacceptable.  An incremental, generational system would, 
> indeed, be better. 

I assume there will be some sort of tuning interface for the IGC (e.g.
objects traversed per update?) so you could just set this to a maximum
and it would behave as now? And, if we had generational optimisations it
would be doing the same job but more optimally. The size of the
performance hits wrt GC is pretty minimal anyway and this only really
becomes a problem in real time systems. GC pauses are very noticeable in
some Java implementations because Java is a huge memory glutton, whereas
Lua is more economical (less time in GC less often). 


> On the other hand if I was doing something 
> which required anything even remotely hard in time 
> requirements, even a generational system wouldn't be that 
> useful -- I'd be needing some form of interruptible concurrency.

Incremental implementations are interruptible by definition. Eek, we
don't want (or need) concurrency! What is planned is incremental mark
and sweep. An optimisation of this would be an incremental generational
mark and sweep algorithm.


> I did work with one experimental Modula-3 (IIRC) environment 
> long ago which had this kind of pluggable GC.  It came with 
> three different GC systems which could be plugged into the 
> environment and if those three weren't suited to your 
> purposes, you could always code your own and put it in place 
> yourself.  Now being an experimental system it was 
> grotesquely inefficient and hugely bloated, but I don't think 
> this was a necessary trait -- it reflected, rather, the 
> hastily-assembled nature of the product.

It has been suggested that the Lua authors put in macros to implement
the write barrier necessary for the more advanced GCs. Different GC
implementations could then be built on this and a system as you suggest
would not be inconceivable. The authors have done a pretty good job
thusfar in implementing the language so I'm pretty happy to wait and see
what they surprise us with next. IGC has long been requested on this
list, above a modular implementation of Lua. Of course I'd be interested
in any comments the authors would like to make wrt your post.

Regards,
Nick




Reply | Threaded
Open this post in threaded view
|

Re: GC order

Michael T. Richter-3
> Eek, we don't want (or need) concurrency!

Whereas I've been toying with the idea of putting a low-priority thread in
Lua which implements a treadmill Just Because It Would Be Cool.  :-)



Reply | Threaded
Open this post in threaded view
|

RE: GC order

Nick Trout
In reply to this post by Bilyk, Alex

> > Eek, we don't want (or need) concurrency!
> 
MR> Whereas I've been toying with the idea of putting a 
> low-priority thread in Lua which implements a treadmill Just 
> Because It Would Be Cool.  :-)

Sounds interesting. I havent really used threads a lot; a problem
springs to mind. What would happen if you had a really intensive period
of processing, which required objects to be GC'd. If the low priority
thread only got called a couple of times it might not collect enough
garbage. Would it lag further and further behind? If you were on a
restricted memory system, couldn't you run out of memory? Would you end
up having to do more work in the low priotiy thread to clear out more of
the garbage? This probably works fine on a not-too-intensive system with
plenty of memory.

Given an incremental system I take it the amount of time spent
collecting will have to be adjusted proportionally to the lack of memory
on a limited memory system. Also, because of the nature of IGC I think
we are going to do more work to collect the same number of objects (as
objects will revert to grey/neutral) as the current system. So,
generational IGC could be a big saving?

/Nick


12