tag:blogger.com,1999:blog-273593670040001243.post1299193571159156082..comments2022-03-28T05:51:26.366-07:00Comments on Useless Factor: A quick intro to garbage collectionAnonymoushttp://www.blogger.com/profile/00902922561603041049noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-273593670040001243.post-69015500998367805272008-03-01T09:00:00.000-08:002008-03-01T09:00:00.000-08:00libGarbageCollector has serious flaws:1. it's not ...libGarbageCollector has serious flaws:<BR/><BR/>1. it's not really incremental; it has degenerate cases incurring long pauses, which kind of defeats the purpose of a heavyweight incremental algorithm.<BR/><BR/>2. it incurs three words of overhead per allocated object, <B>not including</B> per-object headers reserved by malloc/header, which can be up to 2 or 3 words on its own! That means up to 6 words per object.<BR/><BR/>That's simply unacceptable overhead for functional-type languages which typically allocate many small objects. Better to allocate large regions using malloc to create small custom GC heaps.<BR/><BR/>As for this blog post, reference-counting isn't really a "naive" algorithm. Bacon demonstrated that <A HREF="http://www.research.ibm.com/people/d/dfb/papers/Bacon04Unified.pdf" REL="nofollow">all garbage collection algorithms are actually hybrids of tracing and ref-counting</A>. There has been significant research in reducing the cost of ref-counting as well, and ref-counting is now within 15% of the throughput of tracing GCs. Bacon also published a local cycle-collection algorithm which outperforms tracing in tight heaps, such as embedded devices, or for programs with large live data sets. <BR/><BR/>The cost of ref-counting is proportional to the cost of tracing dead objects, whereas the cost of mark-sweep is the cost of tracing live objects. If you have a large old generation with long-lived objects, ref-counting is thus more suitable than mark-sweep. Mark-sweep is more suitable for the young generation, where there's a high death rate. So combining mark-sweep for the young generation and ref-counting for the old gen is a good match. Thus was born <A HREF="http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2003/CS/CS-2003-08.ps" REL="nofollow">age-oriented</A> GC, a concurrent GC that almost matches concurrent mark-sweep in throughput with maximum pause times on the order of 2.5ms.<BR/><BR/>Bacon et al. then refined their cycle-collection algorithm in <A HREF="http://www.research.ibm.com/people/d/dfb/papers/Paz05Efficient.pdf" REL="nofollow">Efficient On-the-Fly Cycle Collection</A>, and the age-oriented collector is now even more efficient.<BR/><BR/>If Factor needs a concurrent, incremental GC suitable for code and data collection, check out "Efficient On-the-Fly Cycle Collection". I'll probably end up using it as well.<BR/><BR/>Long live ref-counting! ;-)Sandro Magihttps://www.blogger.com/profile/05446177882449578817noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-28550127032637775612008-02-28T11:21:00.000-08:002008-02-28T11:21:00.000-08:00I did some more reading. Now I think I understand...I did some more reading. Now I think I understand Slava's objections better.<BR/><BR/>Although libgarbagecollector allows you to specify how memory is allocated and freed, since the collector doesn't move objects, you run into the fragmentation problem whether you use malloc or not.ebbhttps://www.blogger.com/profile/13637191794150667952noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-89249960502932276012008-02-28T09:04:00.000-08:002008-02-28T09:04:00.000-08:00Dan,Thanks for posting this stuff and answering my...Dan,<BR/><BR/>Thanks for posting this stuff and answering my question. As a new Factor tinkerer and not-so-new dynamic languages fan, it makes for interesting reading.<BR/><BR/>Slava,<BR/><BR/>Are you referring to the library's use of malloc to allocate it's own book-keeping data structures? In it's current version, the library gives the user control over how his objects are allocated and freed -- you don't have to use malloc if you don't want to.<BR/><BR/>Also, reading the Io OOPSLA 2005 slides, I read that Io has a generational collector. Maybe Io's implementation builds a generational collector on top of the library by clever use of the mark and free callbacks?ebbhttps://www.blogger.com/profile/13637191794150667952noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-2306655544569290082008-02-27T16:41:00.000-08:002008-02-27T16:41:00.000-08:00I should also mention libgarbagecollector's use of...I should also mention libgarbagecollector's use of libc malloc precludes scanning the entire heap or saving the heap to a file (Factor is image based).<BR/><BR/>None of this should be taken as bashing Dekote's work; his garbage collector library is small and easy to understand, and it works very well in the context in which it is used -- lightweight scripting.Slava Pestovhttps://www.blogger.com/profile/02768382790667979877noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-27625585247609296642008-02-27T16:39:00.000-08:002008-02-27T16:39:00.000-08:00I've looked at Io's libgarbagecollector in the pas...I've looked at Io's libgarbagecollector in the past but decided it was not good enough for Factor. First it is not generational so it is only suitable for small heaps. It also sits on top of the C library's malloc so heap fragmentation and free list scanning are a concern.Slava Pestovhttps://www.blogger.com/profile/02768382790667979877noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-16050683256676322252008-02-27T12:10:00.000-08:002008-02-27T12:10:00.000-08:00Eric,I didn't know about libgarbagecollector; that...Eric,<BR/>I didn't know about libgarbagecollector; that might be something to look into for using in Factor. Right now, Factor uses (for data) a three-generation copying collector and (for code) a mark-sweep collector. The GC isn't sound because a full data GC doesn't happen at the same time as a full code GC, so if there's code that nothing refers to, but doesn't fill up the code heap, and that code refers to data which exausts the data memory, the code won't be collected. But, more importantly, an incremental algorithm like libgarbagecollector's would eliminate noticeable pauses, which would be very good. (I'd be surprised if using libgarbagecollector didn't require rewriting large parts of it, though.)Anonymoushttps://www.blogger.com/profile/00902922561603041049noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-54447661142016664312008-02-27T12:00:00.000-08:002008-02-27T12:00:00.000-08:00My guess is that you're already aware of it, but j...My guess is that you're already aware of it, but just in case, I thought I'd mention libgarbagecollector as it is "a plug-in garbage collector library designed to be used by high level language implementors".<BR/><BR/>http://tinyurl.com/339y5z<BR/><BR/>Out of curiousity: what sort of gc algorithm does Factor currently use?ebbhttps://www.blogger.com/profile/13637191794150667952noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-70682352352819144192008-02-27T11:23:00.000-08:002008-02-27T11:23:00.000-08:00anonymous,Some GC mechanisms are faster and others...anonymous,<BR/>Some GC mechanisms are faster and others are slower. Historically, some scanning GC algorithms took multi-second pauses and had significantly less throughput than manual memory management. It's not completely clear-cut. It's hard to eliminate these pauses, which in the worst case take more time than any single malloc/free call, without some very complicated incremental or concurrent technique. (One concurrent technique is to take Erlang's route and just have a bunch of small heaps with no sharing.) Anyway, even if GC were always slower, the benefits of automatic memory management are so great that it'd be worth it.<BR/><BR/>Gwenhwyfaer,<BR/>Yeah, I know, I guess i just explained this badly, so I reworded that.Anonymoushttps://www.blogger.com/profile/00902922561603041049noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-22737040222098262982008-02-27T09:54:00.000-08:002008-02-27T09:54:00.000-08:00dan: Re conservative GC: it's not just that you ha...dan: Re conservative GC: it's not just that you have to assume any word "is a pointer", it's worse - any word <I>might be</I> a pointer. So non-pointers cause incorrect retention, and any GC method which mutates pointers (eg. mark & compact) cannot be used. Static typing can help, but only if type information is available to the GC process, which requires compiler co-operation (or <I>really</I> good debugging metadata).<BR/><BR/>kobi: Each of erlang's processes might be very small, but there are thousands of them, and they might be distributed across many nodes - and unfortunately complete distributed garbage collection is impossible in the presence of patchily-reliable distributed systems (see the <A HREF="http://www.iecc.com/gclist/GC-faq.html" REL="nofollow">GC FAQ</A>).gwenhwyfaerhttps://www.blogger.com/profile/03775254923855147509noreply@blogger.comtag:blogger.com,1999:blog-273593670040001243.post-35674407694386365452008-02-27T06:05:00.000-08:002008-02-27T06:05:00.000-08:00Hey dan, actually when a program is garbage collec...Hey dan, actually when a program is garbage collected, it's usually faster than a malloced and freed, or perceived to be anyway.<BR/>that's because there aren't the extra operations of freeing when in the critical or main code, and it (the gc) is saved for later.<BR/>Also, I know that erlang's GC happens very fast, simply because each process is very small, and the gc happens within the process. so this is a way of working around inventing some super intelligent GC. hth, kobiAnonymousnoreply@blogger.com