Garbage Collection
in [TCL]
|
Prev: How to localize the "About" menu entry in Tk8.5.8/Cocoa? [solved]
Next: using expect to test as text-based menu
From: chintu on 15 Mar 2010 08:26 Working with Tcl i never come across with Garbage collection or memory overflow error, may be i never used long strings :) But going through the ideas posted on Tcl website under Gsoc'10 link, i found "Garbage Collection for Tcl objects" idea that attracts my attention. I gone through whole idea and decided to work on it. These days i am searching and working on, all most all the algorithms for garbage collection and their Tcl implementation. i come across with "Tri color marking" algorithm which looks like it can be implemented, but getting some conceptual problems. i am also trying some different algorithms and searching for the best possible algorithms to be implemented easily. Am i on right track?? i need help. Please guide....
From: Alexandre Ferrieux on 15 Mar 2010 09:01 On Mar 15, 1:26 pm, chintu <prans...(a)gmail.com> wrote: > Working with Tcl i never come across with Garbage collection or memory > overflow error, may be i never used long strings :) > But going through the ideas posted on Tcl website under Gsoc'10 link, > i found "Garbage Collection for Tcl objects" idea that attracts my > attention. I gone through whole idea and decided to work on it. > > These days i am searching and working on, all most all the algorithms > for garbage collection and their Tcl implementation. > i come across with "Tri color marking" algorithm which looks like it > can be implemented, but getting some conceptual problems. i am also > trying some different algorithms and searching for the best possible > algorithms to be implemented easily. > > Am i on right track?? i need help. Please guide.... Ah, maybe the item's title is slightly misleading :} Indeed, what Steve is referring to as "garbage collection" in http://wiki.tcl.tk/23186#pagetoce0162b46 is specifically "non- monotonous allocation of the blocks holding Tcl_Objs". He gives links, please follow them. As a short summary: Tcl's memory management system works with fixed- size 'objects', called Tcl_Obj, whose application-level lifecycle is handled by refcounting. This refcounting is bullet-proof because no circular references can be made (copy-on-write only ever builds acyclic graphs). But the system-level lifecycle if that of the blocks holding many of them, that are currently just malloc'ed and never freed, mainly for a lack of incentive so far, and also for lack of per- object info allowing to retrieve the containing block. In this context, Steve's suggestion is to go beyond the mere suggestions offered in https://sourceforge.net/tracker/?func=detail&aid=2960042&group_id=10894&atid=110894 and actually do the job. As you can see, the problem is *not* about app-level lifecycle (aptly covered by refcounts), but rather about efficiently arranging for the blocks to be freed at some point. So far I can see two approaches: (a) (slightly) slow down every Tcl_Obj allocation/disposal to update its containing block's count of non-free objects; free the block when it reaches zero (possibly with an hysteresis to avoid single-object "tremor"). Also implies more complex structures and address arithmetics in the block to avoid adding a pointer field to every individual object. (b) don't touch individual Tcl_Obj allocation/disposal, but have a slower block-collector that essentially scans all objects of blocks looking for full blocks of free objects. This can be very slow, and possibly do nothing (if allocated objects are scattered over the blocks). In addition, it may imply explicit script-level action [gc] because external libraries' failing malloc()s cannot be retried after a gc pass (while Tcl's can). I have a slight preference for (a) but this can be affected by a measurement of the performance impact on individual allocations. -Alex
From: blacksqr on 17 Mar 2010 01:13 The original poster seems extremely eager to take on this problem as a summer of code project. I am eager to see it tackled, but I'm not qualified to mentor such a project should it be judged feasible. I hope that if this project makes the cut, Alexandre and/or Donal can be tempted to mentor it. --Steve H.
From: chintu on 19 Mar 2010 10:08 On Mar 17, 10:13 am, blacksqr <stephen.hunt...(a)alum.mit.edu> wrote: > The original poster seems extremely eager to take on this problem as a > summer of code project. I am eager to see it tackled, but I'm not > qualified to mentor such a project should it be judged feasible. I > hope that if this project makes the cut, Alexandre and/or Donal can be > tempted to mentor it. > > --Steve H. yaa... m very much ablaze to work on this problem.... :) ya help from alexandre and donal... will be bonus for me.. :)
From: chintu on 19 Mar 2010 10:18
On Mar 15, 6:01 pm, Alexandre Ferrieux <alexandre.ferri...(a)gmail.com> wrote: > On Mar 15, 1:26 pm, chintu <prans...(a)gmail.com> wrote: > > > Working with Tcl i never come across with Garbage collection or memory > > overflow error, may be i never used long strings :) > > But going through the ideas posted on Tcl website under Gsoc'10 link, > > i found "Garbage Collection for Tcl objects" idea that attracts my > > attention. I gone through whole idea and decided to work on it. > > > These days i am searching and working on, all most all the algorithms > > for garbage collection and their Tcl implementation. > > i come across with "Tri color marking" algorithm which looks like it > > can be implemented, but getting some conceptual problems. i am also > > trying some different algorithms and searching for the best possible > > algorithms to be implemented easily. > > > Am i on right track?? i need help. Please guide.... > > Ah, maybe the item's title is slightly misleading :} > > Indeed, what Steve is referring to as "garbage collection" inhttp://wiki.tcl.tk/23186#pagetoce0162b46is specifically "non- > monotonous allocation of the blocks holding Tcl_Objs". He gives links, > please follow them. > > As a short summary: Tcl's memory management system works with fixed- > size 'objects', called Tcl_Obj, whose application-level lifecycle is > handled by refcounting. This refcounting is bullet-proof because no > circular references can be made (copy-on-write only ever builds > acyclic graphs). But the system-level lifecycle if that of the blocks > holding many of them, that are currently just malloc'ed and never > freed, mainly for a lack of incentive so far, and also for lack of per- > object info allowing to retrieve the containing block. > > In this context, Steve's suggestion is to go beyond the mere > suggestions offered in > > https://sourceforge.net/tracker/?func=detail&aid=2960042&group_id=108... > > and actually do the job. > > As you can see, the problem is *not* about app-level lifecycle (aptly > covered by refcounts), but rather about efficiently arranging for the > blocks to be freed at some point. So far I can see two approaches: > > (a) (slightly) slow down every Tcl_Obj allocation/disposal to > update its containing block's count of non-free objects; free the > block when it reaches zero (possibly with an hysteresis to avoid > single-object "tremor"). Also implies more complex structures and > address arithmetics in the block to avoid adding a pointer field to > every individual object. > > (b) don't touch individual Tcl_Obj allocation/disposal, but have a > slower block-collector that essentially scans all objects of blocks > looking for full blocks of free objects. This can be very slow, and > possibly do nothing (if allocated objects are scattered over the > blocks). In addition, it may imply explicit script-level action [gc] > because external libraries' failing malloc()s cannot be retried after > a gc pass (while Tcl's can). > > I have a slight preference for (a) but this can be affected by a > measurement of the performance impact on individual allocations. > > -Alex Thanks.... for replying I was down with fever.. so posting a little late... :( I understand your Point (a) of your approach, i was thinking like this only.. :) Point(b) not that clear to me.. :( The Tcl_obj -> typedef struct Tcl_Obj { int refCount; ----> [you mean if this become 0 object is deleted. It doesnt happen now with Tcl compiler???] char *string; Tcl_ObjType *typePtr; ---> [what this command do??] union { int intValue; double doubleValue; VOID *otherValuePtr; struct { int field1; int field2; } twoIntValue; } internalRep; } Tcl_Obj; Thanxx once again for helping me out... :) |