tag:blogger.com,1999:blog-273593670040001243.post4361684192035085520..comments2022-03-28T05:51:26.366-07:00Comments on Useless Factor: Some more advanced GC techniquesAnonymoushttp://www.blogger.com/profile/00902922561603041049noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-273593670040001243.post-53379499755078350392008-03-24T09:05:00.000-07:002008-03-24T09:05:00.000-07:00Sun's Garbage First paper is available here.http:/...Sun's Garbage First paper is available here.<BR/><BR/>http://research.sun.com/jtech/pubs/04-g1-paper-ismm.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-13660581951838910262008-03-23T20:55:00.000-07:002008-03-23T20:55:00.000-07:00Wasn't looking for credit, just wanted to identify...Wasn't looking for credit, just wanted to identify myself so you know who you were talking to. :-)<BR/><BR/>Re: justice, it just seemed like you covered ref-counting as, "it's hard to get right in a concurrent setting", which doesn't reflect the state of the art since the turn of the century. Ref-counting seems one of the only one we know how to get right! Mark-sweep is another that also uses the efficient "sliding views" used in Bacon's ref-counting collector.<BR/><BR/>As for cycle-collection algorithms, Bacon's is the most efficient that I know of (the most recent I've read at least), and his on-the-fly age-oriented garbage collection is pretty compelling compared to other concurrent GCs. Bacon has pointed out many problems with previous supposedly "concurrent" GC algorithms, and his algos suffer no such problems. Highly recommended if you have the time.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-41744060289604890212008-03-23T20:42:00.000-07:002008-03-23T20:42:00.000-07:00Sandro, Thanks. I should have credited you with th...Sandro, Thanks. I should have credited you with the link you gave me. It's true that I didn't do refcounting justice, but I didn't really do any other technique justice either, since it was all a short summary. To everything that's relevant justice would mean writing a book. I hope no one misinterprets this as an attempt to cover everything.<BR/><BR/>I forgot about the cycle collection paper you listed, so thanks for providing it again. Many many cycle-collecting refcounting GCs have been made, and I'm nowhere near up-to-date on the research on them (or any other aspect of this field).Anonymoushttps://www.blogger.com/profile/00902922561603041049noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-61590005429403105942008-03-23T20:29:00.000-07:002008-03-23T20:29:00.000-07:00I posted the reference to the Unified Theory of GC...I posted the reference to the Unified Theory of GC on your first blog post.<BR/><BR/>You don't do ref-counting justice in your post. In <A HREF="http://useless-factor.blogspot.com/2008/02/quick-intro-to-garbage-collection.html#c6901550099836780527" REL="nofollow">my original post</A>, I had already provided a reference to a state of the art concurrent, ref-counting garbage collector, which also provides a proof of correctness. I'll provide it again: <A HREF="http://www.research.ibm.com/people/d/dfb/papers/Paz05Efficient.pdf" REL="nofollow">Efficient On-the-Fly Cycle Collection</A>.<BR/><BR/>As far as I know, there are proofs of correctness only for concurrent ref-counting algorithms, which is a pretty damning criticism of other concurrent GCs given how difficult concurrent algorithms are.<BR/><BR/>figg, nice reference to RC. First I'd heard of it.<BR/><BR/>As for region-based memory management: it's unclear whether there is an optimal, general region-inference algorithm. The paper introducing Makholm-Niss region inference (Makholm's thesis too) provides some evidence that region-inference will always need a little guidance to infer optimal object lifetimes, and this shouldn't be too surprising as all typing schemes require a little information in order to derive the rest. What form this information takes is an open question however.<BR/><BR/>Regions can be manually managed however. See the Cyclone language for instance. Fluett showed that linear typing is all you really need to enable safe region-based manual memory management.Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-10440119503738390632008-03-23T19:45:00.000-07:002008-03-23T19:45:00.000-07:00figg, Thanks for the pointers. I don't know enough...figg, Thanks for the pointers. I don't know enough about region inference to write about it, but that stuff looks interesting. I assumed it was fundamentally flawed because memory usage patterns can't, in general, be completely known before runtime, but I guess I'm wrong.Anonymoushttps://www.blogger.com/profile/00902922561603041049noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-69324233357914996202008-03-23T19:30:00.000-07:002008-03-23T19:30:00.000-07:00How about regions?Region inference is a memory man...How about regions?<BR/><BR/>Region inference is a memory management method for computer programming. It is an alternative to manual memory management and garbage collection.<BR/><BR/>Region inference involves associating variables or objects with a "region" in a stack-like construct. Older regions are lower on the stack, and younger regions are higher. Regions are analyzed statically to determine when they "die" - and all the variables or objects associated with that region die with the region. Whenever an older region is determined to be "dead", all younger regions die with it.<BR/><BR/>See:<BR/><BR/>http://citeseer.ist.psu.edu/tofte97regionbased.html<BR/><BR/>This paper describes a memory management discipline for programs that perform dynamic memory allocation and de-allocation. At runtime, all values are put into regions. The store consists of a stack of regions. All points of region allocation and deallocation are inferred automatically, using a type and effect based program analysis. The scheme does not assume the presence of a garbage collector. <BR/><BR/>Also:<BR/><BR/>http://berkeley.intel-research.net/dgay/rc/<BR/><BR/>RC is a dialect of C that adds safe, region-based memory management to C: <BR/> <BR/>Region-based memory management allocates objects in a program-specified region. Objects cannot be freed individually; instead regions are deleted with all their contained objects. Region-based memory management is a fairly common programming style, for instance it is used in the Apache web server (where the regions are called pools and also used to manage other resources).<BR/>RC is safe: RC maintains for each region r a reference count of the number of external pointers to objects in r, i.e., of pointers not stored within r. Deleting a region with a non-zero reference count causes a runtime error (abort). Thus RC programs cannot access freed memory. The overhead for safety in RC is low (less than 11% on a group of realistic benchmarks).<BR/><BR/>And:<BR/><BR/>http://citeseer.ist.psu.edu/pereira02dynamic.html<BR/><BR/> We present a garbage collection scheme based on reference counting and region inference which, unlike the standard reference counting algorithm, handles cycles correctly. In our algorithm, the fundamental operations of region inference are performed dynamically. No assistance is required from the programmer or the compiler, making our algorithm particularly well-suited for use in dynamically-typed languages such as scripting languagesAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-31744851309226001482008-03-23T12:42:00.000-07:002008-03-23T12:42:00.000-07:00The real question; how do you find time to hack on...The real question; how do you find time to hack on factor and write these blog posts.<BR/><BR/>I am impressed with the factor team.Berlin Brown Discussionshttps://www.blogger.com/profile/14524539202704556506noreply@blogger.com