5 ms·

> They almost "just work", except for circular references Well, and they're often slower since they require mutating the reference count on every single time a

> They almost "just work", except for circular references Well, and they're often slower since they require mutating the reference count on every single time a field is stored. You can optimize that using lazy reference counting, or not updating refcounts for references on the stack and instead scanning the stack before a collection. But at that point... you're halfway to implementing a tracing collector. Every refcounting implementation eventually gets "optimized" to the point that it has most of a tracing collector hiding inside of it. I think it's simpler, cleaner, and faster to just start with tracing in the first place. There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. That being said, ref-counting is fine for other kinds of resource management where resources are pretty coarse-grained and don't have cyclic references. For example, I think Delphi uses ref-counting to manage strings, which makes a lot of sense. Many games use ref-counting for tracking resources loaded from disc, and that also works well. In both of those cases, there's nothing to trace through, and the overhead of updating refcounts is fairly low.

blattimwind 7y ago
> There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. Reference counting and address-semantics (which prohibits moving objects, so even if you work around the refcount, you can only do a tracing GC, but you don't get to compact) are deeply ingrained into CPython's C API as well, which is very widely used.
nostrademons 7y ago
There's a classic paper that shows that refcounting and GC are in fact duals of each other, where GC is effectively tracing live objects and refcounting is tracing dead objects: https://dl.acm.org/citation.cfm?id=1028982 https://dl.acm.org/citation.cfm?id=1028982 This had a number of important corollaries to this. One is that they have opposite performance characteristics: GCs make creating new references fast but then create a large pause when RAM is exhausted and a collection happens, while refcounts make creating new references slow and create a large pause when large object graphs are freed all at once. Another is that nearly all high-performance memory management systems are hybrids of the two: lazy refcounting is basically like implementing a local garbage collector and then feeding the live set of that into the refcounts, while generational garbage collection is like implementing a local refcount (the write barrier) and feeding the results of that into the root set.
ridiculous_fish 7y ago
Objective-C and then Swift are surely the most serious goes at fast widely used RC languages. Neither requires mutating the reference count on every store, and neither seems at risk of growing a tracing GC. ObjC had some elision tricks like objc_retainAutoreleasedReturnValue, but more importantly the optimizer was taught about RC manipulation. Swift then extended this with a new ABI that minimizes unnecessary mutations. The big advantages of this scheme are efficient COW collections and a simpler FFI (very important with Swift). More generally RC integrates better. Imagine teaching the JS GC to walk the Java heap!
- pjmlp 7y ago
  So efficient that Swift's RC implementation loses against all major tracing GC implementations. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
  - jmull 7y ago
    That project doesn’t compare GC implementations, so it’s probably not that useful here. Also, the Swift implementation is a bit questionable if performance is a goal. That is, why not try to remove the memory management from the inner loop? Probably the first thing to try is value types instead of reference types, which are more generally preferred anyway.
    - pjmlp 7y ago
      Sure it does, memory management impacts the performance of the task being achieved, writing an high-speed network driver.
      - jmull 7y ago
        By that measure, every project is a good measure of GC performance. Is that really a good argument? I believe all general purpose languages let the code allocate memory and therefore will let you allocate memory in a way inefficient to your task.
tyingq 7y ago
"There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception" Perl is also ref counted. Swift too. Edit: Also TCL, and PHP is mostly recounted...the "GC" just deals with circular refs.
- lizmat 7y ago
  Just for the record: Raku (née Perl 6) most definitely does not do refcounting. If you want to do serious async programming, refcounting becomes a nightmare to get right and/or a source of potential deadlocks.
smueller1234 7y ago
For what it's worth, Perl (5) has the same problem as CPython. Accordingly, there's not only heaps of allocation- and ref-counting-avoidance optimizations (eg. the stack isn't recounted) but also heaps of bugs from the optimizations. Again, the (main) stack not owning references is the biggest source of these bugs. The problem with predictable destruction, we typically called "timely destruction", but more accurate would've been "immediate destruction" and if your language guarantees it, it tends to be great for automatically releasing resources (memory, file handles,...) in a lexically predictable manner. Softening any such guarantee should lead to entertaining resource races magically appearing in the real world. It occurs to me now that I never checked what pypy guarantees if anything? We (Perl) never really came up with a great strategy for working around this (you tended to get the worst of both worlds in most naive reimplementations of the behavior in a GC-based interpreter) and while I certainly haven't tried to work out a clean argument to the effect, I'm fairly convinced it won't fly at all.
- lizmat 7y ago
  Raku (née Perl 6) has phasers that will be called when exiting a scope. One such idiom is: { # do stuff my $dbh = DB.connect(...); # do stuff LEAVE .disconnect with $dbh; # do stuff } Whenever the scope is left (this could be because of an execution error, or a `return`), the code of the LEAVE phaser will be executed. The `with $dbh` checks whether the $dbh variable contains an instantiated object. If so, it topicalizes (set $_ to it) and calls the disconnect method (`.disconnect` being short for `$_.disconnect`). For more complex uses, and more tuneable finalizing, there is the `FINALIZER` module in the ecosystem: https://modules.raku.org/dist/FINALIZER https://modules.raku.org/dist/FINALIZER
  - smueller1234 7y ago
    Sure, but "schedule action at scope exit" is an easy (assuming your runtime already knows how to unwind the stacks) problem to solve. "Perform escape analysis and guarantee immediate destruction; efficiently without full gc nor refcounting" is not and they're not the same problem at all.

blattimwind 7y ago

> There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception and they would switch to tracing if they could. They can't because they exposed deterministic finalization to the user which means now their GC strategy is a language "feature" that they're stuck with. Reference counting and address-semantics (which prohibits moving objects, so even if you work around the refcount, you can only do a tracing GC, but you don't get to compact) are deeply ingrained into CPython's C API as well, which is very widely used.

nostrademons 7y ago

There's a classic paper that shows that refcounting and GC are in fact duals of each other, where GC is effectively tracing live objects and refcounting is tracing dead objects: https://dl.acm.org/citation.cfm?id=1028982 https://dl.acm.org/citation.cfm?id=1028982 This had a number of important corollaries to this. One is that they have opposite performance characteristics: GCs make creating new references fast but then create a large pause when RAM is exhausted and a collection happens, while refcounts make creating new references slow and create a large pause when large object graphs are freed all at once. Another is that nearly all high-performance memory management systems are hybrids of the two: lazy refcounting is basically like implementing a local garbage collector and then feeding the live set of that into the refcounts, while generational garbage collection is like implementing a local refcount (the write barrier) and feeding the results of that into the root set.

ridiculous_fish 7y ago

Objective-C and then Swift are surely the most serious goes at fast widely used RC languages. Neither requires mutating the reference count on every store, and neither seems at risk of growing a tracing GC. ObjC had some elision tricks like objc_retainAutoreleasedReturnValue, but more importantly the optimizer was taught about RC manipulation. Swift then extended this with a new ABI that minimizes unnecessary mutations. The big advantages of this scheme are efficient COW collections and a simpler FFI (very important with Swift). More generally RC integrates better. Imagine teaching the JS GC to walk the Java heap!

pjmlp 7y ago
So efficient that Swift's RC implementation loses against all major tracing GC implementations. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
- jmull 7y ago
  That project doesn’t compare GC implementations, so it’s probably not that useful here. Also, the Swift implementation is a bit questionable if performance is a goal. That is, why not try to remove the memory management from the inner loop? Probably the first thing to try is value types instead of reference types, which are more generally preferred anyway.
  - pjmlp 7y ago
    Sure it does, memory management impacts the performance of the task being achieved, writing an high-speed network driver.
    - jmull 7y ago
      By that measure, every project is a good measure of GC performance. Is that really a good argument? I believe all general purpose languages let the code allocate memory and therefore will let you allocate memory in a way inefficient to your task.

tyingq 7y ago

"There's a reason almost no widely used language implementation relies on ref-counting. CPython is the only real exception" Perl is also ref counted. Swift too. Edit: Also TCL, and PHP is mostly recounted...the "GC" just deals with circular refs.

lizmat 7y ago
Just for the record: Raku (née Perl 6) most definitely does not do refcounting. If you want to do serious async programming, refcounting becomes a nightmare to get right and/or a source of potential deadlocks.

smueller1234 7y ago

For what it's worth, Perl (5) has the same problem as CPython. Accordingly, there's not only heaps of allocation- and ref-counting-avoidance optimizations (eg. the stack isn't recounted) but also heaps of bugs from the optimizations. Again, the (main) stack not owning references is the biggest source of these bugs. The problem with predictable destruction, we typically called "timely destruction", but more accurate would've been "immediate destruction" and if your language guarantees it, it tends to be great for automatically releasing resources (memory, file handles,...) in a lexically predictable manner. Softening any such guarantee should lead to entertaining resource races magically appearing in the real world. It occurs to me now that I never checked what pypy guarantees if anything? We (Perl) never really came up with a great strategy for working around this (you tended to get the worst of both worlds in most naive reimplementations of the behavior in a GC-based interpreter) and while I certainly haven't tried to work out a clean argument to the effect, I'm fairly convinced it won't fly at all.

lizmat 7y ago
Raku (née Perl 6) has phasers that will be called when exiting a scope. One such idiom is: { # do stuff my $dbh = DB.connect(...); # do stuff LEAVE .disconnect with $dbh; # do stuff } Whenever the scope is left (this could be because of an execution error, or a `return`), the code of the LEAVE phaser will be executed. The `with $dbh` checks whether the $dbh variable contains an instantiated object. If so, it topicalizes (set $_ to it) and calls the disconnect method (`.disconnect` being short for `$_.disconnect`). For more complex uses, and more tuneable finalizing, there is the `FINALIZER` module in the ecosystem: https://modules.raku.org/dist/FINALIZER https://modules.raku.org/dist/FINALIZER
- smueller1234 7y ago
  Sure, but "schedule action at scope exit" is an easy (assuming your runtime already knows how to unwind the stacks) problem to solve. "Perform escape analysis and guarantee immediate destruction; efficiently without full gc nor refcounting" is not and they're not the same problem at all.