4 ms·

Mark-sweep-compact is another GC algorithm that supports bump allocation, and doesn't have the 2x overhead of semispace.

deleted 9y ago
[deleted]
dfox 9y ago
The point is that you need moving GC for bump-allocation to be possible. Traditional mark-and-sweep is non-moving while semispace collector is the simplest to describe moving GC. The practical takeaway from all that is that usual generational GC constructions with semispace minor collections and mark-and-sweep/compact major collections are in the complexity/efficiency sweet spot. By the way it is possible and trivial, although somewhat non obvious, to construct non-moving generational GC. The general idea is that for simple M&S you have some list of live objects which you replace that with multiple per-generation lists (Claus Gittinger mentions this in his VM design talks, which probably means that at some point such GC was used by ST/X).
- ridiculous_fish 9y ago
  Moving collectors get you best allocation throughput but impose other costs, which are hard to measure because they are design constraints. Obviously you cannot have a moving conservative collector so you must have stack maps, safe points, etc. Or interactions with native code. How can native code hold a reference to a potentially movable object? .NET allows pinned pointers (obviously hurting compaction efficiency) while JNI uses double-dereferenced handles, of which there's a limit (65k in Android!) Compare to, say, JavaScriptCore, which uses a non-moving collector, and simply conservatively scans native stacks. Whether these costs are important depends on your use case, but it's important to remember that we're rarely building isolated systems. > non-moving generational GC Yes, that's what Apple built for its ill-fated experiment with GC! Amusingly Apple also built its inverse: a moving manual memory manager. Google MoreMasters for some retro fun!
  - dfox 9y ago
    The design space has one non-obvious but fundamental strict dividing line: if you can constrain the mutator code enough to be able to insert write barriers for generation GC you also can constrain it enough to have all the metadata to support moving GC at least to the extent of opportunistic compaction (eg. what CLR and SBCL on i386 does, both of which have conservationaly scanned stack because building stack map for register-constrained platforms like i386 is essentially impossible). On the other hand BEAM has AFAIK non-moving generational GC implemented in the aforementioned way which is in this case trivial as you don't need any write barriers and remembered set when heap objects are inherently immutable. (In this it is somewhat relevant that Boehm GC for some time had API that allowed you to signal the time extent of mutatibility of given heap object to the GC, AFAIK it is no-op since some 6.x version and the concurrent/incremental/generational bits of it work on basis of mprotect() and handling SIGSEGV)
    - ridiculous_fish 9y ago
      Aside from the stack, another key challenge for moving GCs is hash tables keyed on object identity. If the object can move the raw address is no longer a suitable hash. .NET at one point stored an extra per-object word, which was either (via its LSB) a random hash code or a pointer to a metadata object that held the lock, etc. Python did this cute thing where moved objects would get an extra word allocated to store the moved-from address, which was where the hash was stored. Apple's plan for its (not-released) ObjC moving GC was to directly teach the GC about hash tables, so it could rehash on collection (!). Do you know how other implementations handle this? BEAM's GC is indeed a marvel both because of the immutability and also the enforced process isolation, so that each process can do its own GC independently. As you say, constrain the mutator...
      - dfox 9y ago
        Cpython has non-moving GC so this is not an issue. On the other hand CPython's hashmap implementation is probably most educational open source hashmap implementation that you can find, because it is full of wonderful and portable performance hacks (for one thing the hash values of CPython's objects is intentionally computed such that the distribution is non-uniform which allows tuning of the hashmap implementation for common cases). As for having tight coupling between moving GC and hashmap implementation there is another reason why you want to do that: weak pointers and hashmaps that are either weak keyed or weak valued which both are things that are useful for the VM implementation itself (symbol tables, method dispatch caches, identity maps for FFI...).

deleted 9y ago

[deleted]

dfox 9y ago

The point is that you need moving GC for bump-allocation to be possible. Traditional mark-and-sweep is non-moving while semispace collector is the simplest to describe moving GC. The practical takeaway from all that is that usual generational GC constructions with semispace minor collections and mark-and-sweep/compact major collections are in the complexity/efficiency sweet spot. By the way it is possible and trivial, although somewhat non obvious, to construct non-moving generational GC. The general idea is that for simple M&S you have some list of live objects which you replace that with multiple per-generation lists (Claus Gittinger mentions this in his VM design talks, which probably means that at some point such GC was used by ST/X).

ridiculous_fish 9y ago
Moving collectors get you best allocation throughput but impose other costs, which are hard to measure because they are design constraints. Obviously you cannot have a moving conservative collector so you must have stack maps, safe points, etc. Or interactions with native code. How can native code hold a reference to a potentially movable object? .NET allows pinned pointers (obviously hurting compaction efficiency) while JNI uses double-dereferenced handles, of which there's a limit (65k in Android!) Compare to, say, JavaScriptCore, which uses a non-moving collector, and simply conservatively scans native stacks. Whether these costs are important depends on your use case, but it's important to remember that we're rarely building isolated systems. > non-moving generational GC Yes, that's what Apple built for its ill-fated experiment with GC! Amusingly Apple also built its inverse: a moving manual memory manager. Google MoreMasters for some retro fun!
- dfox 9y ago
  The design space has one non-obvious but fundamental strict dividing line: if you can constrain the mutator code enough to be able to insert write barriers for generation GC you also can constrain it enough to have all the metadata to support moving GC at least to the extent of opportunistic compaction (eg. what CLR and SBCL on i386 does, both of which have conservationaly scanned stack because building stack map for register-constrained platforms like i386 is essentially impossible). On the other hand BEAM has AFAIK non-moving generational GC implemented in the aforementioned way which is in this case trivial as you don't need any write barriers and remembered set when heap objects are inherently immutable. (In this it is somewhat relevant that Boehm GC for some time had API that allowed you to signal the time extent of mutatibility of given heap object to the GC, AFAIK it is no-op since some 6.x version and the concurrent/incremental/generational bits of it work on basis of mprotect() and handling SIGSEGV)
  - ridiculous_fish 9y ago
    Aside from the stack, another key challenge for moving GCs is hash tables keyed on object identity. If the object can move the raw address is no longer a suitable hash. .NET at one point stored an extra per-object word, which was either (via its LSB) a random hash code or a pointer to a metadata object that held the lock, etc. Python did this cute thing where moved objects would get an extra word allocated to store the moved-from address, which was where the hash was stored. Apple's plan for its (not-released) ObjC moving GC was to directly teach the GC about hash tables, so it could rehash on collection (!). Do you know how other implementations handle this? BEAM's GC is indeed a marvel both because of the immutability and also the enforced process isolation, so that each process can do its own GC independently. As you say, constrain the mutator...
    - dfox 9y ago
      Cpython has non-moving GC so this is not an issue. On the other hand CPython's hashmap implementation is probably most educational open source hashmap implementation that you can find, because it is full of wonderful and portable performance hacks (for one thing the hash values of CPython's objects is intentionally computed such that the distribution is non-uniform which allows tuning of the hashmap implementation for common cases). As for having tight coupling between moving GC and hashmap implementation there is another reason why you want to do that: weak pointers and hashmaps that are either weak keyed or weak valued which both are things that are useful for the VM implementation itself (symbol tables, method dispatch caches, identity maps for FFI...).