9 ms·

New Garbage Collector

190 points by dochtman 14y ago

simcop2387 14y ago
The more and more I read about modern garbage collection design the more and more it seems to be remeniscent of filesystem design. It makes me wonder if there's some large parallels between them that can be used advantageously to benefit both. Things that people have learned work well on filesystems might apply to garbage collection and vice versa.
- oconnor0 14y ago
  How so? Could you explain in more detail?
  - simcop2387 14y ago
    A lot of what I've seen in the structures of how they keep track of things efficiently seem to be very similar. Though filesystems are adding a bit of extra data to it compared to the GC, (filenames, locations, etc) a number of the design constraints and things seem to be very very similar. Like the idea to keep track of what's free and doing the allocation seem to have very similar solutions even given the different constraints. I think part of this might also be because some of the more modern filesystems are being designed to also consider SSD which end up even closer to normal memory. The way that (at least at a layman's understanding) btrfs seems to handle COW looks very similar to how this new garbage collection is being designed for lua. And the arenas look very much like the extants in ext4 (not sure about that in btrfs). This also makes me wonder if a design that takes caching of the drive into account could make some small improvements on things. EDIT: added small snippet about the arenas.
    - ithkuil 14y ago
      Filesystems and memory allocation algorithms do have something in common. The problem of allocating memory and managing free space etc exists also without GC. When hierarchical filesystems behave as pure trees, it's always possible to simply deallocate the storage of a deleted file, because the file cannot be pointed by more than one entry in the tree. Unix filesystems, however, do have a way of creating several references to the same file, namely hard links. In order to handle these multiple references (like having a program with multiple variables pointing to the same object) a kind of GC algorithm is used, which is simply a "reference counting GC". Reference counting is a simple technique which is appropriate in several cases but has it's drawbacks and it's One of these drawbacks can be illustrated by this quote: "One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.” Moon patiently told the student the following story: “One day a student came to Moon and said: ‘I understand how to make a better garbage collector... ”"
      - caf 14y ago
        This drawback is why sensible UNIX filesystems don't allow you to create hardlinks to directories.
- dons 14y ago
  Convergence. When we all have persistent, solid state drives, your filesystem will be your heap and GC...
  - jmaygarden 14y ago
    To what solid state drive technology are you referring that would make good use as a heap? I wouldn't think that NAND flash would be suitable due to the write/erase constraints.
    - VMG 14y ago
      MRAM maybe? (http://en.wikipedia.org/wiki/Magnetoresistive_random-access_memory http://en.wikipedia.org/wiki/Magnetoresistive_random-access_...)
    - mburns 14y ago
      Memristors?
    - dons 14y ago
      Was thinking of this article earlier this week: http://lwn.net/Articles/498289/ http://lwn.net/Articles/498289/ (which I'm presuming is some MRAM thing)
    - jasonwatkinspdx 14y ago
      1.) If capacity increases, for a given workload, overwriting updates save less capacity. So even without new technology, there's a trend towards less overwrites of a given block for a fixed workload. 2.) Memristor Memory
    - Tuna-Fish 14y ago
      NAND flash is going away. Right now it loses half it's write endurance, and it's eraseblocks double in size, every shrink. Eraseblocks are already at 4MB and write endurance is below a 1000 writes, pretty soon additional shrinks will bring no value. This happens because of fundamental physical limits, and no-one believes they can be overcome -- even the biggest proponents are talking about delaying the inevitable for a few years instead of avoiding it. Right now, there is a hundred-billion-dollar stampede going on for finding out it's successor. Players include: MRAM (Toshiba, Hitachi, Hynix, IBM, Everspin(Freescale spinoff), Samsung, NEC) FeRAM (Ramtron, IBM, TI, Fujitsu, Samsung, Matsushita, Oki, Toshiba, Infineon, Hynix, Symetrix) ReRAM (HP, ITRI, IMEC, Panasonic, Rambus) CBRAM (NEC, Sony, Axon, Micron) PRAM (Intel, IBM, ST Micro, Samsung, Numoxys) I might have missed a few backers. Also, all names after a technology are not working together, especially in FeRAM there are multiple competing approaches. An interesting commonality about these technologies is that they all aim to be universal memories. That is, they intend to eventually replace both DRAM and Flash, and some are even aiming for the last cache levels in cpus. This will probably lead to some changes in system design. Although I think the people who are calling for the death of filesystems are going about it all wrong -- I expect the role of filesystems to expand, not shrink. All they need is new block layers. Note that while everyone says memristors (ReRAM), they aren't even the most likely candidate (if I'd have to pick, I'd say PRAM), HP just has the best marketing.
- ajross 14y ago
  I don't see the technical reasoning there, but I agree that there's a thematic parallel: they're both reasonably straightforward ideas with very clean user-facing stories. They can both be implemented very simply (literally as part of an undergraduate course -- I remember writing both). And they both have undesirable performance problems in certain regimes, the solution to which has been the unending quest of generations of incredibly smart programmers and academics. They have led to staggering complexity, weird bugs, huge near-unmaintainable codebases, and uncounted PhD theses. Whole careers have been aimed at this stuff. And frankly it's been, from many perspectives, mostly a waste. ZFS/btrfs are, for 95% of problems, indistinguishable from FFS/ext2 implementations that are a tiny fraction of their size. Modern Java and .NET VMs still have latency issues under GC pressure that were equally visible in Emacs Lisp a quarter century ago. Applications which have hard requirements that fly in the face of these systems don't use them. Serious storage servers don't use the filesystem except vestigially (i.e. they do manual sync on very large files, or they use a block device directly). Serious realtime apps don't do GC and manage memory themselves. And that's not going to change no matter how many PhD's we throw at the problem.
  - cokernel_hacker 14y ago
    I am afraid that is not even close to accurate. If you define "95% of problems" to be "reading and writing data such that data is read and written" sure, great. However, there are two little, minor things that file systems care about: performance and safety. FFS/ext2 have neither of things. Neither ext2 nor FFS contain a journal nor do the copy-on-write metadata. Heck, if you "upgrade" to ext3, you get the journal but nothing that protects you from bit-rot. If you look at most drives on the market, you will see devices capable of corrupting data for certain after three years. Your journal'd filesystem does jack in this case, all it can do is ensure proper ordering of writes to metadata, no guarantees that the data will be any good once written. How about performance? Well, if you look at FFS/ext2 they are essentially terrible. Block-at-a-time allocators with no extent configuration. Good luck getting the most out of your storage media when you have your block tree data-structure. Granted, ZFS suffers from the same issue but btrfs's extent tree configuration certainly does not. IIRC, the state of the art ext[23] implementations use read ahead to ameliorate the problem but does not fundamentally cure it. If you look at ext4, they have adopted extent trees via their Htree structure. A filesystem like zfs/btrfs is pretty imune to bitrot, they can easily mirror their metadata and avoid overwriting their metadata like FFS/ext[234] making torn writes non-issues. They avoid the many pathologies that your "simpler" filesystem and trades the complexity for not needing a fsck mechanism in the face of data-corruption, one should only be needed in the face of implementation bugs (you should note that ZFS has no fsck, btrfs just recently obtained one). Oh, and if any of you think soft updates work, they don't. While it would be great if they really did work but in a world where drives actively reorder writes and do not respect SCSI/SATA/misc transport commands to flush their internal caches, then you do not get safety. This set of drives is considerably huge. tl;dr You are oversimplifying the complex.
- nwmcsween 14y ago
  'Filesystems' as in arbitrary data serialized to an arbitrary backing is absurdly stupid when said data has a structure as with all data. A semantic system that understands the data needs to be implemented at some point - why have n parsing implementations for a single data format? With a semantic 'object system' data becomes apart of programming.
Raphael_Amiard 14y ago
This is great news ! I don't know if Mike Pall reads Hacker News, but a couple ideas come to my mind : - May it be a good idea to create a KickStarter page ? I know LuaJit has its own donation mecanism, but it may help it gain further exposure. I know i'd be willing to donate for a better GC in either case. - Mike mentions it has to be a non-moving collector, which is usually known for having worse performance than moving collectors. Also, a non-moving generational collector (and incremental, since this is also a requirement) is hard to get right. I tried implementing a GC along the lines of this paper : http://www.pllab.riec.tohoku.ac.jp/papers/icfp2011UenoOhoriOtomoAuthorVersion.pdf http://www.pllab.riec.tohoku.ac.jp/papers/icfp2011UenoOhoriO... which presents a fast non moving collector. Incidentally it has ideas similar to those presented in this article. Maybe it could be a good source of inspiration ? I realize the ideas are maybe not as production grade since there is only one language implementation with a GC of this sort.
- kingkilr 14y ago
  Kickstarter (last I checked) requires you to be American, so it won't fly for Mike (who is German).
- mikemike 14y ago
  Yes, I thought about crowdfunding. But I fear that a) the Lua community is way too small to gather enough interest and b) it looks like the whole crowdfunding idea is rapidly deteriorating into an arms race of marketing experts. So many people are now jumping on that bandwagon. You'll never make it, unless you stay on the frontpages somehow. Alas, I'm not good at marketing and a garbage collector is a very technical and very unsexy project (for most people, anyway). I should make up a silly name for it, that bears no relation to what it does. Yeah, that would do ... Thank you for the link to the paper! I'll check it out. I have good evidence that it's possible to create a non-moving GC that doesn't suck. It's a bit like marrying the best-of-breed of malloc implementations with the best-of-breed of incremental mark & sweep collectors. Plus some crazy ideas I'll have to experiment with first ...
  - Raphael_Amiard 14y ago
snprbob86 14y ago
This document uses a bunch of jargon that I couldn't find good explanations/definitions for. Is there a good GC survey out there? If I wanted to write a modern GC and knew nothing about it, where would I look to get started? What should I read to get up to speed?
- cjensen 14y ago
  "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by Richard Jones and Rafael D Lins. Very readable and approachable. I read the entire book, which I almost never do with technical books.
  - snprbob86 14y ago
    Thanks. I'll add it to the queue :-)
  - me2i81 14y ago
    There's a newer book (2011), "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, Antony Hoskins and Eliot Moss. I haven't read the new one, but it seems to cover a lot of the recent activity around Java GC.
  - cwzwarich 14y ago
    The recent followup "The Garbage Collection Handbook: The Art of Automatic Memory Management" is much more up-to-date, but it has a bit less coverage of the more elementary techniques.
- silentbicycle 14y ago
  Wilson's "Uniprocessor Garbage Collection Techniques" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2438 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2...) is what you want: an excellent survey paper of fundamental garbage collector designs. I highly recommend the Jones/Hosking/Moss book, but it assumes familiarity with the basics. Pick it up if the Wilson paper intrigues you. The previous edition of the book (Jones & Lins) is good, too, but the new one adds a lot of important material on real-time GC, concurrent GC, and interactions between GC and runtime systems.
pcwalton 14y ago
This is very interesting, because it's extremely similar to the design that we need for Rust. We need: * A generational GC, preferably bump-allocating so that we can win on allocation-heavy workloads. * A non-thread-safe GC, because all GC'd data is local to a single task in Rust (and we enforce this in the type system). * A precise GC, because (a) we don't want accidental or malicious leaks due to misinterpreting non-pointers as pointers; and (b) because we need precise GC metadata to clean up shared data and run destructors when tasks fail. * An incremental GC, because minimizing pause times is absolutely critical for browsers. * A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily (i.e. when allowing pointers to live in registers). Fixing this would require a significant portion of all target code to be rewritten. Also of particular interest is the ability for individual allocation sites to choose to bump allocate only, in the interests of performance (but at the expense of fragmentation). This could potentially allow Rust programmers to fine-tune their allocation behavior and trade performance for fragmentation when it makes sense to do so. Very cool, and I'll be sure to keep an eye on this.
- Raphael_Amiard 14y ago
  > A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily This is a shame that this is so badly documented. I stumbled upon this way after having coded the whole code generator of my Z3 project (https://github.com/raph-amiard/Z3 https://github.com/raph-amiard/Z3 - Ocaml bytecode -> LLVM compiler). The fact that you have to explicitly handle live roots with stacks instructions defeats a lot of the purpose of LLVM IR.
  - pcwalton 14y ago
    I've got a bunch of code in a branch to allow register roots: https://github.com/pcwalton/llvm/tree/noteroots-ir https://github.com/pcwalton/llvm/tree/noteroots-ir It just automatically roots live values that are pointers in a nonzero addrspace. Still doesn't support copying GC, and only works in the fast instruction selector at the moment, but it goes a long way toward making GC performant in LLVM.
    - 14y ago
kokoloko 14y ago
Each language is rolling out its own GC. Why not share some efforts in a common library?
- pjmlp 14y ago
  It's called JVM and .NET.
  - warmwaffles 14y ago
    Can't really use that with Lua and Ruby
    - pjmlp 14y ago
      Really?! Lua: http://sourceforge.net/projects/luaj/ http://sourceforge.net/projects/luaj/ https://bitbucket.org/xixs/anlua https://bitbucket.org/xixs/anlua http://luaforge.net/projects/luanet/ http://luaforge.net/projects/luanet/ Ruby: http://jruby.org/ http://jruby.org/ http://www.ironruby.net/ http://www.ironruby.net/
- draegtun 14y ago
  libgarbagecollector - http://www.dekorte.com/projects/opensource/libgarbagecollector/ http://www.dekorte.com/projects/opensource/libgarbagecollect... libgarbagecollector is a plug-in garbage collector library designed to be used by high level language implementors. It's used in the Io programming language.
- BruceM 14y ago
  There's Boehm, MPS (http://www.ravenbrook.com/project/mps/ http://www.ravenbrook.com/project/mps/) Apple's AutoZone, and others. As mentioned above, I'm regularly talking with Ravenbrook about liberalizing the license on MPS and doing some work on modernizing it. I've hopes that that might happen this year. And some of the language specific ones are pretty good ... SGen in Mono seems interesting. The GC in ClozureCL is interesting as well.
- ufo 14y ago
dllthomas 14y ago
>It must be non-copying, due to various constraints in the Lua/C API. I don't see this. The Lua GC has to know what's visible from C, in order to avoid freeing those objects. If it knows what's visible from C, then it strictly just needs to avoid copying those objects. If it moves them to an uncollected area when C references them, and back when C dereferences them, then it can use a copying collector on the Lua-only objects. This actually might work very well, if C-referenced objects are going to tend to be much longer lived. Of course, copying the objects into and out of the uncollected region will itself be some work. I have no idea if the ideal algorithm is in this space, I just think that either they discarded copying collectors prematurely, or there's something I'm missing, so either I get to learn something or they do; is there a constraint I've missed?
- mikemike 14y ago
  There's no explicit API to pin objects from the C side. Ok, so there's an implicit contract on which pointers to internal VM objects are still valid, once the C side has gotten them (const char *lua_tostring() is the biggest offender). But this contract a) does not lead to a practical implementation and b) is violated by plenty of C modules for Lua, because Lua didn't have a moving GC, so nobody bothered to follow it. Now ... the interesting objects, that benefit most from the defragmentation effects of a moving GC, are the variable-sized objects. Sadly, userdata cannot be moved at all and strings are the only other interesting object type. Well ... see above. [Table objects are not variable-size. Only their array and hash parts are. But these are singly-linked from the table object and can easily be moved around, anyway. The addresses of these memory blocks are never exposed by the VM.]
  - tedunangst 14y ago
    If you had a bit free, you could track which objects escape to C. But it's probably not worth going that way. Well, maybe. Programs that generate tons of strings may only occasionally escape them, so maybe moving them as part of the C call would be a good idea.
  - daurnimator 14y ago
    I would argue in recent years people have been more aware of the non-guarantee of static pointers in the lua api; and a moving GC would be feasible. There was talk that the next lua version (after 5.2) would have a moving GC...
caf 14y ago
It would be easier to follow if you used actual colours rather than several shades of grey in your description of your 4-colour design.

190 points by dochtman 14y ago

The more and more I read about modern garbage collection design the more and more it seems to be remeniscent of filesystem design. It makes me wonder if there's some large parallels between them that can be used advantageously to benefit both. Things that people have learned work well on filesystems might apply to garbage collection and vice versa.

oconnor0 14y ago
How so? Could you explain in more detail?
- simcop2387 14y ago
  A lot of what I've seen in the structures of how they keep track of things efficiently seem to be very similar. Though filesystems are adding a bit of extra data to it compared to the GC, (filenames, locations, etc) a number of the design constraints and things seem to be very very similar. Like the idea to keep track of what's free and doing the allocation seem to have very similar solutions even given the different constraints. I think part of this might also be because some of the more modern filesystems are being designed to also consider SSD which end up even closer to normal memory. The way that (at least at a layman's understanding) btrfs seems to handle COW looks very similar to how this new garbage collection is being designed for lua. And the arenas look very much like the extants in ext4 (not sure about that in btrfs). This also makes me wonder if a design that takes caching of the drive into account could make some small improvements on things. EDIT: added small snippet about the arenas.
  - ithkuil 14y ago
    Filesystems and memory allocation algorithms do have something in common. The problem of allocating memory and managing free space etc exists also without GC. When hierarchical filesystems behave as pure trees, it's always possible to simply deallocate the storage of a deleted file, because the file cannot be pointed by more than one entry in the tree. Unix filesystems, however, do have a way of creating several references to the same file, namely hard links. In order to handle these multiple references (like having a program with multiple variables pointing to the same object) a kind of GC algorithm is used, which is simply a "reference counting GC". Reference counting is a simple technique which is appropriate in several cases but has it's drawbacks and it's One of these drawbacks can be illustrated by this quote: "One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.” Moon patiently told the student the following story: “One day a student came to Moon and said: ‘I understand how to make a better garbage collector... ”"
    - caf 14y ago
      This drawback is why sensible UNIX filesystems don't allow you to create hardlinks to directories.
dons 14y ago
Convergence. When we all have persistent, solid state drives, your filesystem will be your heap and GC...
- jmaygarden 14y ago
  To what solid state drive technology are you referring that would make good use as a heap? I wouldn't think that NAND flash would be suitable due to the write/erase constraints.
  - VMG 14y ago
    MRAM maybe? (http://en.wikipedia.org/wiki/Magnetoresistive_random-access_memory http://en.wikipedia.org/wiki/Magnetoresistive_random-access_...)
  - mburns 14y ago
    Memristors?
  - dons 14y ago
    Was thinking of this article earlier this week: http://lwn.net/Articles/498289/ http://lwn.net/Articles/498289/ (which I'm presuming is some MRAM thing)
  - jasonwatkinspdx 14y ago
    1.) If capacity increases, for a given workload, overwriting updates save less capacity. So even without new technology, there's a trend towards less overwrites of a given block for a fixed workload. 2.) Memristor Memory
  - Tuna-Fish 14y ago
    NAND flash is going away. Right now it loses half it's write endurance, and it's eraseblocks double in size, every shrink. Eraseblocks are already at 4MB and write endurance is below a 1000 writes, pretty soon additional shrinks will bring no value. This happens because of fundamental physical limits, and no-one believes they can be overcome -- even the biggest proponents are talking about delaying the inevitable for a few years instead of avoiding it. Right now, there is a hundred-billion-dollar stampede going on for finding out it's successor. Players include: MRAM (Toshiba, Hitachi, Hynix, IBM, Everspin(Freescale spinoff), Samsung, NEC) FeRAM (Ramtron, IBM, TI, Fujitsu, Samsung, Matsushita, Oki, Toshiba, Infineon, Hynix, Symetrix) ReRAM (HP, ITRI, IMEC, Panasonic, Rambus) CBRAM (NEC, Sony, Axon, Micron) PRAM (Intel, IBM, ST Micro, Samsung, Numoxys) I might have missed a few backers. Also, all names after a technology are not working together, especially in FeRAM there are multiple competing approaches. An interesting commonality about these technologies is that they all aim to be universal memories. That is, they intend to eventually replace both DRAM and Flash, and some are even aiming for the last cache levels in cpus. This will probably lead to some changes in system design. Although I think the people who are calling for the death of filesystems are going about it all wrong -- I expect the role of filesystems to expand, not shrink. All they need is new block layers. Note that while everyone says memristors (ReRAM), they aren't even the most likely candidate (if I'd have to pick, I'd say PRAM), HP just has the best marketing.
ajross 14y ago
I don't see the technical reasoning there, but I agree that there's a thematic parallel: they're both reasonably straightforward ideas with very clean user-facing stories. They can both be implemented very simply (literally as part of an undergraduate course -- I remember writing both). And they both have undesirable performance problems in certain regimes, the solution to which has been the unending quest of generations of incredibly smart programmers and academics. They have led to staggering complexity, weird bugs, huge near-unmaintainable codebases, and uncounted PhD theses. Whole careers have been aimed at this stuff. And frankly it's been, from many perspectives, mostly a waste. ZFS/btrfs are, for 95% of problems, indistinguishable from FFS/ext2 implementations that are a tiny fraction of their size. Modern Java and .NET VMs still have latency issues under GC pressure that were equally visible in Emacs Lisp a quarter century ago. Applications which have hard requirements that fly in the face of these systems don't use them. Serious storage servers don't use the filesystem except vestigially (i.e. they do manual sync on very large files, or they use a block device directly). Serious realtime apps don't do GC and manage memory themselves. And that's not going to change no matter how many PhD's we throw at the problem.
- cokernel_hacker 14y ago
  I am afraid that is not even close to accurate. If you define "95% of problems" to be "reading and writing data such that data is read and written" sure, great. However, there are two little, minor things that file systems care about: performance and safety. FFS/ext2 have neither of things. Neither ext2 nor FFS contain a journal nor do the copy-on-write metadata. Heck, if you "upgrade" to ext3, you get the journal but nothing that protects you from bit-rot. If you look at most drives on the market, you will see devices capable of corrupting data for certain after three years. Your journal'd filesystem does jack in this case, all it can do is ensure proper ordering of writes to metadata, no guarantees that the data will be any good once written. How about performance? Well, if you look at FFS/ext2 they are essentially terrible. Block-at-a-time allocators with no extent configuration. Good luck getting the most out of your storage media when you have your block tree data-structure. Granted, ZFS suffers from the same issue but btrfs's extent tree configuration certainly does not. IIRC, the state of the art ext[23] implementations use read ahead to ameliorate the problem but does not fundamentally cure it. If you look at ext4, they have adopted extent trees via their Htree structure. A filesystem like zfs/btrfs is pretty imune to bitrot, they can easily mirror their metadata and avoid overwriting their metadata like FFS/ext[234] making torn writes non-issues. They avoid the many pathologies that your "simpler" filesystem and trades the complexity for not needing a fsck mechanism in the face of data-corruption, one should only be needed in the face of implementation bugs (you should note that ZFS has no fsck, btrfs just recently obtained one). Oh, and if any of you think soft updates work, they don't. While it would be great if they really did work but in a world where drives actively reorder writes and do not respect SCSI/SATA/misc transport commands to flush their internal caches, then you do not get safety. This set of drives is considerably huge. tl;dr You are oversimplifying the complex.
nwmcsween 14y ago
'Filesystems' as in arbitrary data serialized to an arbitrary backing is absurdly stupid when said data has a structure as with all data. A semantic system that understands the data needs to be implemented at some point - why have n parsing implementations for a single data format? With a semantic 'object system' data becomes apart of programming.

Raphael_Amiard 14y ago

This is great news ! I don't know if Mike Pall reads Hacker News, but a couple ideas come to my mind : - May it be a good idea to create a KickStarter page ? I know LuaJit has its own donation mecanism, but it may help it gain further exposure. I know i'd be willing to donate for a better GC in either case. - Mike mentions it has to be a non-moving collector, which is usually known for having worse performance than moving collectors. Also, a non-moving generational collector (and incremental, since this is also a requirement) is hard to get right. I tried implementing a GC along the lines of this paper : http://www.pllab.riec.tohoku.ac.jp/papers/icfp2011UenoOhoriOtomoAuthorVersion.pdf http://www.pllab.riec.tohoku.ac.jp/papers/icfp2011UenoOhoriO... which presents a fast non moving collector. Incidentally it has ideas similar to those presented in this article. Maybe it could be a good source of inspiration ? I realize the ideas are maybe not as production grade since there is only one language implementation with a GC of this sort.

kingkilr 14y ago
Kickstarter (last I checked) requires you to be American, so it won't fly for Mike (who is German).
mikemike 14y ago
Yes, I thought about crowdfunding. But I fear that a) the Lua community is way too small to gather enough interest and b) it looks like the whole crowdfunding idea is rapidly deteriorating into an arms race of marketing experts. So many people are now jumping on that bandwagon. You'll never make it, unless you stay on the frontpages somehow. Alas, I'm not good at marketing and a garbage collector is a very technical and very unsexy project (for most people, anyway). I should make up a silly name for it, that bears no relation to what it does. Yeah, that would do ... Thank you for the link to the paper! I'll check it out. I have good evidence that it's possible to create a non-moving GC that doesn't suck. It's a bit like marrying the best-of-breed of malloc implementations with the best-of-breed of incremental mark & sweep collectors. Plus some crazy ideas I'll have to experiment with first ...
- Raphael_Amiard 14y ago

snprbob86 14y ago

This document uses a bunch of jargon that I couldn't find good explanations/definitions for. Is there a good GC survey out there? If I wanted to write a modern GC and knew nothing about it, where would I look to get started? What should I read to get up to speed?

cjensen 14y ago
"Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by Richard Jones and Rafael D Lins. Very readable and approachable. I read the entire book, which I almost never do with technical books.
- snprbob86 14y ago
  Thanks. I'll add it to the queue :-)
- me2i81 14y ago
  There's a newer book (2011), "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, Antony Hoskins and Eliot Moss. I haven't read the new one, but it seems to cover a lot of the recent activity around Java GC.
- cwzwarich 14y ago
  The recent followup "The Garbage Collection Handbook: The Art of Automatic Memory Management" is much more up-to-date, but it has a bit less coverage of the more elementary techniques.
silentbicycle 14y ago
Wilson's "Uniprocessor Garbage Collection Techniques" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2438 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2...) is what you want: an excellent survey paper of fundamental garbage collector designs. I highly recommend the Jones/Hosking/Moss book, but it assumes familiarity with the basics. Pick it up if the Wilson paper intrigues you. The previous edition of the book (Jones & Lins) is good, too, but the new one adds a lot of important material on real-time GC, concurrent GC, and interactions between GC and runtime systems.

pcwalton 14y ago

This is very interesting, because it's extremely similar to the design that we need for Rust. We need: * A generational GC, preferably bump-allocating so that we can win on allocation-heavy workloads. * A non-thread-safe GC, because all GC'd data is local to a single task in Rust (and we enforce this in the type system). * A precise GC, because (a) we don't want accidental or malicious leaks due to misinterpreting non-pointers as pointers; and (b) because we need precise GC metadata to clean up shared data and run destructors when tasks fail. * An incremental GC, because minimizing pause times is absolutely critical for browsers. * A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily (i.e. when allowing pointers to live in registers). Fixing this would require a significant portion of all target code to be rewritten. Also of particular interest is the ability for individual allocation sites to choose to bump allocate only, in the interests of performance (but at the expense of fragmentation). This could potentially allow Rust programmers to fine-tune their allocation behavior and trade performance for fragmentation when it makes sense to do so. Very cool, and I'll be sure to keep an eye on this.

Raphael_Amiard 14y ago
> A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily This is a shame that this is so badly documented. I stumbled upon this way after having coded the whole code generator of my Z3 project (https://github.com/raph-amiard/Z3 https://github.com/raph-amiard/Z3 - Ocaml bytecode -> LLVM compiler). The fact that you have to explicitly handle live roots with stacks instructions defeats a lot of the purpose of LLVM IR.
- pcwalton 14y ago
  I've got a bunch of code in a branch to allow register roots: https://github.com/pcwalton/llvm/tree/noteroots-ir https://github.com/pcwalton/llvm/tree/noteroots-ir It just automatically roots live values that are pointers in a nonzero addrspace. Still doesn't support copying GC, and only works in the fast instruction selector at the moment, but it goes a long way toward making GC performant in LLVM.
  - 14y ago

kokoloko 14y ago

Each language is rolling out its own GC. Why not share some efforts in a common library?

pjmlp 14y ago
It's called JVM and .NET.
- warmwaffles 14y ago
  Can't really use that with Lua and Ruby
  - pjmlp 14y ago
    Really?! Lua: http://sourceforge.net/projects/luaj/ http://sourceforge.net/projects/luaj/ https://bitbucket.org/xixs/anlua https://bitbucket.org/xixs/anlua http://luaforge.net/projects/luanet/ http://luaforge.net/projects/luanet/ Ruby: http://jruby.org/ http://jruby.org/ http://www.ironruby.net/ http://www.ironruby.net/
draegtun 14y ago
libgarbagecollector - http://www.dekorte.com/projects/opensource/libgarbagecollector/ http://www.dekorte.com/projects/opensource/libgarbagecollect... libgarbagecollector is a plug-in garbage collector library designed to be used by high level language implementors. It's used in the Io programming language.
BruceM 14y ago
There's Boehm, MPS (http://www.ravenbrook.com/project/mps/ http://www.ravenbrook.com/project/mps/) Apple's AutoZone, and others. As mentioned above, I'm regularly talking with Ravenbrook about liberalizing the license on MPS and doing some work on modernizing it. I've hopes that that might happen this year. And some of the language specific ones are pretty good ... SGen in Mono seems interesting. The GC in ClozureCL is interesting as well.
ufo 14y ago

dllthomas 14y ago

>It must be non-copying, due to various constraints in the Lua/C API. I don't see this. The Lua GC has to know what's visible from C, in order to avoid freeing those objects. If it knows what's visible from C, then it strictly just needs to avoid copying those objects. If it moves them to an uncollected area when C references them, and back when C dereferences them, then it can use a copying collector on the Lua-only objects. This actually might work very well, if C-referenced objects are going to tend to be much longer lived. Of course, copying the objects into and out of the uncollected region will itself be some work. I have no idea if the ideal algorithm is in this space, I just think that either they discarded copying collectors prematurely, or there's something I'm missing, so either I get to learn something or they do; is there a constraint I've missed?

mikemike 14y ago
There's no explicit API to pin objects from the C side. Ok, so there's an implicit contract on which pointers to internal VM objects are still valid, once the C side has gotten them (const char *lua_tostring() is the biggest offender). But this contract a) does not lead to a practical implementation and b) is violated by plenty of C modules for Lua, because Lua didn't have a moving GC, so nobody bothered to follow it. Now ... the interesting objects, that benefit most from the defragmentation effects of a moving GC, are the variable-sized objects. Sadly, userdata cannot be moved at all and strings are the only other interesting object type. Well ... see above. [Table objects are not variable-size. Only their array and hash parts are. But these are singly-linked from the table object and can easily be moved around, anyway. The addresses of these memory blocks are never exposed by the VM.]
- tedunangst 14y ago
  If you had a bit free, you could track which objects escape to C. But it's probably not worth going that way. Well, maybe. Programs that generate tons of strings may only occasionally escape them, so maybe moving them as part of the C call would be a good idea.
- daurnimator 14y ago
  I would argue in recent years people have been more aware of the non-guarantee of static pointers in the lua api; and a moving GC would be feasible. There was talk that the next lua version (after 5.2) would have a moving GC...

caf 14y ago

It would be easier to follow if you used actual colours rather than several shades of grey in your description of your 4-colour design.