GC order

27 messages
12
Open this post in threaded view
|

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 > 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 ```
Open this post in threaded view
|

RE: GC order

 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] ```
Open this post in threaded view
|

Re: GC order

 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. ```
Open this post in threaded view
|

Re: GC order

 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. ```
Open this post in threaded view
|

RE: GC order

 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 ```
Open this post in threaded view
|

Re: GC order

 ```> 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. :-) ```
 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 ```