6 ms·

The main difference between the current mark-and-sweep garbage collector and the SpiderMonkey garbage collector is that the latter is a copying garbage collecto

The main difference between the current mark-and-sweep garbage collector and the SpiderMonkey garbage collector is that the latter is a copying garbage collector and precise, meaning that objects may change address during GC and that only typed values, not memory locations that might or might not be, must be trace Out of all the types of gc out there going to a copying gc seems not very compelling. Mark and sweep is not bad at all (well understood, straight forward to implement), and you don't have to worry about double dereferencing pointers (ie some implementations of Cheneys, I don't know if spidermonkey refercences are indirect pointers to one of two buffers).

sitharus 9y ago
Moving GCs are fairly non-intuitive. It seems like the extra overhead to do pointer updates and data copying would cause performance loss, but the generational nature of objects helps a lot. Copying means you get clean pages a lot faster and have fewer OS level allocations caused by pages sparsely populated with gen2 objects. The Microsoft .NET implementation use a copying GC. IIRC the HotSpot JVM GC is compacting as well. Conservative GCs are much easier when interacting with C though, especially if you have to share pointers.
- cbsmith 9y ago
  It also means you can have a much dumber allocator, which is particularly helpful if you do a lot of allocations that never survive long enough to need to be moved.
ww520 9y ago
Out of the 3 general garbage collector types - copying, mark & sweep, and reference count - copying is superior in general. The benefits of copying include: automatic compaction when copying from old heap to new heap (no memory fragmentation), improved locality (objects are closely packed), extremely fast reclamation (just throw away the old heap whereas mark & sweep needs to maintain/update the free list for different sizes of objects), great for systems with lots of objects dying young (mark & sweep needs to reclaim each died young object), cycle removal (ref count's pitfall), and generational GC is just an extension of the copying concept (in addition to copy from old heap to new heap, copy from younger generation to older generations).
- jchanimal 9y ago
  I agree. We used this architecture in Apache CouchDB, and it can also be seen in the Lucene fulltext index. The only downfall is needing enough free space to perform the copy.
  - bitwize 9y ago
    And this is where the "it takes five times as much RAM to run a GC'd program with the same performance as the equivalent program with explicitly managed memory" bit kicks in. Value semantics covers 95% of your object-lifetime needs. The other 5% can be covered with some form of reference counting and being smart about strong vs. weak references. Tracing GC is like bubble sort: almost always a suboptimal solution.
    - rurban 9y ago
      Not 5x as much ram. Exactly 2x more ram. You copy between two half spaces, back and forth. That's why it's usually also called semispace collector. What you are talking in the 2nd paragraph is total nonsense in a lisp world. Lisp solved this problem decades ago, with copying collectors. Stack values are 20%, plus refcounts do not work with rplac* able trees and are super slow.
      - bitwize 9y ago
        Yes -- five times as much RAM: http://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf http://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf As it turns out, compared to the analysis and tree traversal inherent in even a fast GC algorithm, the overhead of malloc() and free() is really quite small. So yes, it takes twice as much memory to use a copying GC, right out of the starting gate -- but in order to match the performance of the equivalent explicitly managed program, it takes even more memory on top of that. And real time -- forget about it. It takes highly tuned, specialized algorithms to run a GC language that can meet hard real-time deadlines. You'll know you've found a decent algorithm because it will be proprietary -- part of some expensive, specialized JVM the Navy uses to crunch radar data aboard ship or something. The conventional algorithms (stop-and-copy, generational, etc.) are all fucking terrible. And I wasn't talking about "in a Lisp world". Lisp is dead for real application development. Hell, the scruffies won, and C++ is now the predominant language in AI -- where Lisp was once said to thrive. Of course refcounts don't work if you try to build a graph with only one kind of reference. But a) you should know what kind of data structure you're building (cyclic or acyclic, graph or tree) and b) you should use weak references where possible to inform the deallocator which references not to chase. It's called being smart. Yes, it's a little more work than using a tracing GC, but it's still far less cognitively taxing or error-prone than using malloc() and free() manually.
__s 9y ago
Copying GC can be straight forward to implement: https://github.com/serprex/luwa/blob/d96ba8fc478813a0a65a65c6346d8ee646e5035c/rt/gc.lua https://github.com/serprex/luwa/blob/d96ba8fc478813a0a65a65c... Get to punt the allocator as a bump allocator
- blt 9y ago
  I found the interaction between the C call stack, the implicit call stack of the interpreted language, and the garbage collector to be tricky. However, I do not see why copying would be any more tricky than compacting.
cbsmith 9y ago
Copying GC is actually very compelling for the right use case (and in fact was part of the standard JVM GC model until it switched over to G1GC). It's particularly useful when you have small, fixed sized objects (hello there cons cell!) and low survivorship (hello eden space!). In the right use case it also helps performance because it increases cache locality.

sitharus 9y ago

Moving GCs are fairly non-intuitive. It seems like the extra overhead to do pointer updates and data copying would cause performance loss, but the generational nature of objects helps a lot. Copying means you get clean pages a lot faster and have fewer OS level allocations caused by pages sparsely populated with gen2 objects. The Microsoft .NET implementation use a copying GC. IIRC the HotSpot JVM GC is compacting as well. Conservative GCs are much easier when interacting with C though, especially if you have to share pointers.

cbsmith 9y ago
It also means you can have a much dumber allocator, which is particularly helpful if you do a lot of allocations that never survive long enough to need to be moved.

ww520 9y ago

Out of the 3 general garbage collector types - copying, mark & sweep, and reference count - copying is superior in general. The benefits of copying include: automatic compaction when copying from old heap to new heap (no memory fragmentation), improved locality (objects are closely packed), extremely fast reclamation (just throw away the old heap whereas mark & sweep needs to maintain/update the free list for different sizes of objects), great for systems with lots of objects dying young (mark & sweep needs to reclaim each died young object), cycle removal (ref count's pitfall), and generational GC is just an extension of the copying concept (in addition to copy from old heap to new heap, copy from younger generation to older generations).

jchanimal 9y ago
I agree. We used this architecture in Apache CouchDB, and it can also be seen in the Lucene fulltext index. The only downfall is needing enough free space to perform the copy.
- bitwize 9y ago
  And this is where the "it takes five times as much RAM to run a GC'd program with the same performance as the equivalent program with explicitly managed memory" bit kicks in. Value semantics covers 95% of your object-lifetime needs. The other 5% can be covered with some form of reference counting and being smart about strong vs. weak references. Tracing GC is like bubble sort: almost always a suboptimal solution.
  - rurban 9y ago
    Not 5x as much ram. Exactly 2x more ram. You copy between two half spaces, back and forth. That's why it's usually also called semispace collector. What you are talking in the 2nd paragraph is total nonsense in a lisp world. Lisp solved this problem decades ago, with copying collectors. Stack values are 20%, plus refcounts do not work with rplac* able trees and are super slow.
    - bitwize 9y ago
      Yes -- five times as much RAM: http://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf http://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf As it turns out, compared to the analysis and tree traversal inherent in even a fast GC algorithm, the overhead of malloc() and free() is really quite small. So yes, it takes twice as much memory to use a copying GC, right out of the starting gate -- but in order to match the performance of the equivalent explicitly managed program, it takes even more memory on top of that. And real time -- forget about it. It takes highly tuned, specialized algorithms to run a GC language that can meet hard real-time deadlines. You'll know you've found a decent algorithm because it will be proprietary -- part of some expensive, specialized JVM the Navy uses to crunch radar data aboard ship or something. The conventional algorithms (stop-and-copy, generational, etc.) are all fucking terrible. And I wasn't talking about "in a Lisp world". Lisp is dead for real application development. Hell, the scruffies won, and C++ is now the predominant language in AI -- where Lisp was once said to thrive. Of course refcounts don't work if you try to build a graph with only one kind of reference. But a) you should know what kind of data structure you're building (cyclic or acyclic, graph or tree) and b) you should use weak references where possible to inform the deallocator which references not to chase. It's called being smart. Yes, it's a little more work than using a tracing GC, but it's still far less cognitively taxing or error-prone than using malloc() and free() manually.

__s 9y ago

Copying GC can be straight forward to implement: https://github.com/serprex/luwa/blob/d96ba8fc478813a0a65a65c6346d8ee646e5035c/rt/gc.lua https://github.com/serprex/luwa/blob/d96ba8fc478813a0a65a65c... Get to punt the allocator as a bump allocator

blt 9y ago
I found the interaction between the C call stack, the implicit call stack of the interpreted language, and the garbage collector to be tricky. However, I do not see why copying would be any more tricky than compacting.

cbsmith 9y ago

Copying GC is actually very compelling for the right use case (and in fact was part of the standard JVM GC model until it switched over to G1GC). It's particularly useful when you have small, fixed sized objects (hello there cons cell!) and low survivorship (hello eden space!). In the right use case it also helps performance because it increases cache locality.