8 ms·

I'm glad they didn't buy into the refcount meme that's so inexplicably popular these days.

by M_Bakhtiari 8y ago

ahamez 8y ago
Could you elaborate? Why would refcount be a bad idea ? (genuine question)
- M_Bakhtiari 8y ago
  Load-increment-store is slow. Load-decrement-branch-if-zero is slow. And you still need a tracing collector for cycles. So it's slow and still nondeterministic.
  - exikyut 8y ago
    Okay, what's better, from a generalist standpoint? I have a decent but very high-level sketched-out understanding of refcounting, but I know nothing else about what's out there, and would be curious to find out. Particularly what would work well on x86 and ARM. An odd and probably completely wrongheaded idea just came to mind: add collectible objects to a lock-free queue in one thread, collect them in another. I wonder if you could do the mark-and-sweep stage across threads too...?
    - pjmlp 8y ago
      Start by reaching out to "The Garbage Collection Handbook" that I mention in another thread.
    - jerven 8y ago
      Better, depends on tradeoff's. RefCounting misses a key feature that ZGC, C4, Shenandoah and other Java GCs do (but not e.g. GO) and that is compacting. Secondly when accessing ref counted objects concurrently ref counting needs to be thread safe. i.e. using atomics, this does have significant performance overheads. Pragmatically in high-throughput situations modern GC's perform better than simple GC. The new things in Java land is that the newest GCs have vastly reduced stop the world times (trending towards OS jitter times), while preserving compaction and without to bad throughput hits. (Even with the misfeatures of finalizers) My personal experience with Shenandoah shows that this changes the way we think about heap settings for java. i.e. just set -Xmx to 60% of machine ram and let idle collections make sure we never use more than 4% in normal days.
      - rurban 8y ago
        For me the biggest letdown of RC is dirtying an otherwise constant pristine page of memory with unneeded updates. Every little usage of that variable changes the variable because it has to update the RC. You are also forced to use two-word values instead of just one (many having even more), with cache trashing and complicated atomics. That's why usually a GC esp. a compacting one is so much faster than refcounting.
- pjmlp 8y ago
  Many think that refcount isn't a GC algorithm and that it is faster than GC. Well, refcounting is the basic way of implementing GC and is listed as GC algorithm in any serious CS book about GC algorithms like "The Garbage Collection Handbook". What many refer as GC is actually the GC algorithms that fall under the umbrella of tracing GC. Then refcounting is only faster than GC in very constrained scenarios: - no sharing across threads, otherwise locking is required for refcount updates - no deep datastructures, otherwise the call stack of cascading deletions will produce a stop similar to tracing GC - implementations need to be clever about nested deletions when refcount reaches 0, otherwise a stack overflow might happen - cyclic datastructures need programmer help to break cycles via weak dependencies or are just not allowed This is only relevant for naive refcount implementations, there are many optimisations, which endup turning a refcounting implementation into a tracing GC in disguise. Also just because a language uses a tracing GC algorithm, it does not prevent the existence of value types, or manual memory allocation for hot code paths, thus allowing for more productive coding, while offering the tools for memory optimisation when needed. This is not yet the case with Java, but even here it is part of the language's roadmap to fix this.
  - Jweb_Guru 8y ago
    > - no sharing across threads, otherwise locking is required for refcount updates That is not true. Most atomic refcount implementations are lockfree (you do need synchronization though). This optimization has nothing to do with tracing. Given that you also need synchronization for tracing garbage collection (including frequent stop the world pauses in most cases, albeit brief ones), I don't think this is even really an advantage of tracing at all. > - no deep datastructures, otherwise the call stack of cascading deletions will produce a stop similar to tracing GC If your program has data structures that live through several collections, refcounting can be faster than tracing GC because it only traces objects once (when they die) instead of several times. Additionally, you can defer the refcount updates in ways that avoid the need to do lots of work on deallocation, and optimize for short-lived objects, to get many of the effects of generational GC. This also has little to do with tracing (except inasmuch as a reference counter with this optimization has to "trace" new objects to make them initially live, but in some sense this work to update the reference counter for the first time is just moved from object initialization time to a later point in the program). The reason it's not usually done is that it requires precise liveness information by an ambient collector, which complicates the implementation, but "exploiting liveness information" is not the same as "being a tracing GC." > - implementations need to be clever about nested deletions when refcount reaches 0, otherwise a stack overflow might happen This is extremely trivial to avoid (if you need to) and has nothing to do with tracing. It's really more a product of user-defined destructors than anything else, which you don't need to provide in order to implement reference counting. In fact, a lot of the supposedly inevitable slowness of reference counting compared to tracing goes away when you ban nontrivial destructors (and conversely, nontrivial destructors make tracing perform much worse). > This is only relevant for naive refcount implementations, there are many optimisations, which endup turning a refcounting implementation into a tracing GC in disguise. The most optimized versions of refcounting I'm aware of get their wins from things like precise knowledge about live references and update coalescing--not tracing, except for some young object optimizations as I alluded to above which are more about satisfying the generational hypothesis (they generally have a backup tracer in order to break cycles, but if you're willing to live without that they usually don't need tracing to reclaim all memory). Many optimizations people commonly associate with tracing (e.g. cache friendliness due to compaction) are in practice only relevant for young generations most of the time; for older ones both tracing and reference counted implementations tend to benefit more from a really smart allocator with intelligent memory layout and partial reclamation. I agree that optimized versions of refcounting are difficult and the fact that you still need a backup tracer for most code discourages people from using it, as well as that tracing doesn't negate a lot of systems optimizations. But a lot of the stuff you're saying is pretty misleading: the things that make tracing efficient can mostly be applied to make reference counting efficient without "turning it into tracing," with the cost that optimized tracing and optimized reference counting both need much more invasive knowledge about the user program (and correspondingly restrict the users) compared to the less optimized versions.
- jwr 8y ago
  From the hacker folklore (AI koans, available at http://catb.org/jargon/html/koans.html http://catb.org/jargon/html/koans.html): Moon instructs a student 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...
- ridiculous_fish 8y ago
  In addition to what others have said, the choice of memory management schemes has big knock-on effects. It influences how much runtime metadata you need to retain (e.g. stack maps), it has lots of implications for the FFI, and may constrain various tricks like unions, tagged pointers, NaN boxing, etc. So narrowly comparing schemes in terms of just allocation throughput won't paint the whole picture.
freecodyx 8y ago
i did google search for "refcount meme", and found out your comment as 3rd result, so it's not that popular...
- jandrese 8y ago
  I figured he was talking about Rust, given that it is basically a refcount system but with the added constraint that the refcount can not exceed 1. It's the only language that is anywhere close to meme status that I know of.
  - richardwhiuk 8y ago
    Arc/Rcs in Rust refcount, but the language doesn't at runtime, or even really at compile time.
  - steveklabnik 8y ago
    FWIW, people make this analogy, but I think it’s quite misleading; a ref count system can make things live longer, but borrowing can’t.
- tom_ 8y ago
  If reference counting were going to help, they'd probably have switched to it already by now. I wonder if the poster just is angling for an opportunity to embark on a rant about one of Swift/Objective-C/ARC, Python, Rust, C++ - or perhaps all of them?
- JeremyBanks 8y ago
  I did a search for "freecodyx user", and found no results, so I guess you don't exist.
  - geezerjay 8y ago
    In order for a meme to exist, it needs to be popular. A person doesn't need to be popular to exist. It's like you're claiming you are famous because your mom knows who you are.
hinkley 8y ago
A lot of the early Java press about their use of GC involved decrying the state of other interpreted languages that were still stuck on reference counting, and the problem of circular references.
codr4 8y ago
"It is time to unmask the computing community as a Secret Society for the Creation and Preservation of Artificial Complexity." ~Dijkstra It's very impressive work, no doubt. And as long as no one asks me to debug anything running on top, I don't have any issues with it. At least with straight reference counting I know what's going on under the hood, that's worth a lot. Sharing pointers across threads is tricky business, I can't really see what that has to do with anything. And it's quite likely that it will run faster, simply because it's much less complex.
- DonHopkins 8y ago
  I've always thought the Monty Python Sketch about The Royal Society for Putting Things on top of Other Things was a perfect metaphor for modern "full stack" software development. https://www.youtube.com/watch?v=1f-kfRREA8M https://www.youtube.com/watch?v=1f-kfRREA8M And the Ministry of Silly Walks is the perfect metaphor for user interface design. https://www.youtube.com/watch?v=iV2ViNJFZC8 https://www.youtube.com/watch?v=iV2ViNJFZC8
  - codr4 8y ago
    A full stack is one push from overflow, I feel that sums it up pretty well :) Silly walks is a masterpiece, and people think they're joking...
frankmcsherry 8y ago
For people who want to fight about tracing vs ref-counting, please read this first, on how the two are dual and most collectors use both: http://www.cs.virginia.edu/%7Ecs415/reading/bacon-garbage.pdf http://www.cs.virginia.edu/%7Ecs415/reading/bacon-garbage.pd...

I'm glad they didn't buy into the refcount meme that's so inexplicably popular these days.

ahamez 8y ago

Could you elaborate? Why would refcount be a bad idea ? (genuine question)

M_Bakhtiari 8y ago
Load-increment-store is slow. Load-decrement-branch-if-zero is slow. And you still need a tracing collector for cycles. So it's slow and still nondeterministic.
- exikyut 8y ago
  Okay, what's better, from a generalist standpoint? I have a decent but very high-level sketched-out understanding of refcounting, but I know nothing else about what's out there, and would be curious to find out. Particularly what would work well on x86 and ARM. An odd and probably completely wrongheaded idea just came to mind: add collectible objects to a lock-free queue in one thread, collect them in another. I wonder if you could do the mark-and-sweep stage across threads too...?
  - pjmlp 8y ago
    Start by reaching out to "The Garbage Collection Handbook" that I mention in another thread.
  - jerven 8y ago
    Better, depends on tradeoff's. RefCounting misses a key feature that ZGC, C4, Shenandoah and other Java GCs do (but not e.g. GO) and that is compacting. Secondly when accessing ref counted objects concurrently ref counting needs to be thread safe. i.e. using atomics, this does have significant performance overheads. Pragmatically in high-throughput situations modern GC's perform better than simple GC. The new things in Java land is that the newest GCs have vastly reduced stop the world times (trending towards OS jitter times), while preserving compaction and without to bad throughput hits. (Even with the misfeatures of finalizers) My personal experience with Shenandoah shows that this changes the way we think about heap settings for java. i.e. just set -Xmx to 60% of machine ram and let idle collections make sure we never use more than 4% in normal days.
    - rurban 8y ago
      For me the biggest letdown of RC is dirtying an otherwise constant pristine page of memory with unneeded updates. Every little usage of that variable changes the variable because it has to update the RC. You are also forced to use two-word values instead of just one (many having even more), with cache trashing and complicated atomics. That's why usually a GC esp. a compacting one is so much faster than refcounting.
pjmlp 8y ago
Many think that refcount isn't a GC algorithm and that it is faster than GC. Well, refcounting is the basic way of implementing GC and is listed as GC algorithm in any serious CS book about GC algorithms like "The Garbage Collection Handbook". What many refer as GC is actually the GC algorithms that fall under the umbrella of tracing GC. Then refcounting is only faster than GC in very constrained scenarios: - no sharing across threads, otherwise locking is required for refcount updates - no deep datastructures, otherwise the call stack of cascading deletions will produce a stop similar to tracing GC - implementations need to be clever about nested deletions when refcount reaches 0, otherwise a stack overflow might happen - cyclic datastructures need programmer help to break cycles via weak dependencies or are just not allowed This is only relevant for naive refcount implementations, there are many optimisations, which endup turning a refcounting implementation into a tracing GC in disguise. Also just because a language uses a tracing GC algorithm, it does not prevent the existence of value types, or manual memory allocation for hot code paths, thus allowing for more productive coding, while offering the tools for memory optimisation when needed. This is not yet the case with Java, but even here it is part of the language's roadmap to fix this.
- Jweb_Guru 8y ago
  > - no sharing across threads, otherwise locking is required for refcount updates That is not true. Most atomic refcount implementations are lockfree (you do need synchronization though). This optimization has nothing to do with tracing. Given that you also need synchronization for tracing garbage collection (including frequent stop the world pauses in most cases, albeit brief ones), I don't think this is even really an advantage of tracing at all. > - no deep datastructures, otherwise the call stack of cascading deletions will produce a stop similar to tracing GC If your program has data structures that live through several collections, refcounting can be faster than tracing GC because it only traces objects once (when they die) instead of several times. Additionally, you can defer the refcount updates in ways that avoid the need to do lots of work on deallocation, and optimize for short-lived objects, to get many of the effects of generational GC. This also has little to do with tracing (except inasmuch as a reference counter with this optimization has to "trace" new objects to make them initially live, but in some sense this work to update the reference counter for the first time is just moved from object initialization time to a later point in the program). The reason it's not usually done is that it requires precise liveness information by an ambient collector, which complicates the implementation, but "exploiting liveness information" is not the same as "being a tracing GC." > - implementations need to be clever about nested deletions when refcount reaches 0, otherwise a stack overflow might happen This is extremely trivial to avoid (if you need to) and has nothing to do with tracing. It's really more a product of user-defined destructors than anything else, which you don't need to provide in order to implement reference counting. In fact, a lot of the supposedly inevitable slowness of reference counting compared to tracing goes away when you ban nontrivial destructors (and conversely, nontrivial destructors make tracing perform much worse). > This is only relevant for naive refcount implementations, there are many optimisations, which endup turning a refcounting implementation into a tracing GC in disguise. The most optimized versions of refcounting I'm aware of get their wins from things like precise knowledge about live references and update coalescing--not tracing, except for some young object optimizations as I alluded to above which are more about satisfying the generational hypothesis (they generally have a backup tracer in order to break cycles, but if you're willing to live without that they usually don't need tracing to reclaim all memory). Many optimizations people commonly associate with tracing (e.g. cache friendliness due to compaction) are in practice only relevant for young generations most of the time; for older ones both tracing and reference counted implementations tend to benefit more from a really smart allocator with intelligent memory layout and partial reclamation. I agree that optimized versions of refcounting are difficult and the fact that you still need a backup tracer for most code discourages people from using it, as well as that tracing doesn't negate a lot of systems optimizations. But a lot of the stuff you're saying is pretty misleading: the things that make tracing efficient can mostly be applied to make reference counting efficient without "turning it into tracing," with the cost that optimized tracing and optimized reference counting both need much more invasive knowledge about the user program (and correspondingly restrict the users) compared to the less optimized versions.
jwr 8y ago
From the hacker folklore (AI koans, available at http://catb.org/jargon/html/koans.html http://catb.org/jargon/html/koans.html): Moon instructs a student 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...
ridiculous_fish 8y ago
In addition to what others have said, the choice of memory management schemes has big knock-on effects. It influences how much runtime metadata you need to retain (e.g. stack maps), it has lots of implications for the FFI, and may constrain various tricks like unions, tagged pointers, NaN boxing, etc. So narrowly comparing schemes in terms of just allocation throughput won't paint the whole picture.

freecodyx 8y ago

i did google search for "refcount meme", and found out your comment as 3rd result, so it's not that popular...

jandrese 8y ago
I figured he was talking about Rust, given that it is basically a refcount system but with the added constraint that the refcount can not exceed 1. It's the only language that is anywhere close to meme status that I know of.
- richardwhiuk 8y ago
  Arc/Rcs in Rust refcount, but the language doesn't at runtime, or even really at compile time.
- steveklabnik 8y ago
  FWIW, people make this analogy, but I think it’s quite misleading; a ref count system can make things live longer, but borrowing can’t.
tom_ 8y ago
If reference counting were going to help, they'd probably have switched to it already by now. I wonder if the poster just is angling for an opportunity to embark on a rant about one of Swift/Objective-C/ARC, Python, Rust, C++ - or perhaps all of them?
JeremyBanks 8y ago
I did a search for "freecodyx user", and found no results, so I guess you don't exist.
- geezerjay 8y ago
  In order for a meme to exist, it needs to be popular. A person doesn't need to be popular to exist. It's like you're claiming you are famous because your mom knows who you are.

hinkley 8y ago

A lot of the early Java press about their use of GC involved decrying the state of other interpreted languages that were still stuck on reference counting, and the problem of circular references.

codr4 8y ago

"It is time to unmask the computing community as a Secret Society for the Creation and Preservation of Artificial Complexity." ~Dijkstra It's very impressive work, no doubt. And as long as no one asks me to debug anything running on top, I don't have any issues with it. At least with straight reference counting I know what's going on under the hood, that's worth a lot. Sharing pointers across threads is tricky business, I can't really see what that has to do with anything. And it's quite likely that it will run faster, simply because it's much less complex.

DonHopkins 8y ago
I've always thought the Monty Python Sketch about The Royal Society for Putting Things on top of Other Things was a perfect metaphor for modern "full stack" software development. https://www.youtube.com/watch?v=1f-kfRREA8M https://www.youtube.com/watch?v=1f-kfRREA8M And the Ministry of Silly Walks is the perfect metaphor for user interface design. https://www.youtube.com/watch?v=iV2ViNJFZC8 https://www.youtube.com/watch?v=iV2ViNJFZC8
- codr4 8y ago
  A full stack is one push from overflow, I feel that sums it up pretty well :) Silly walks is a masterpiece, and people think they're joking...

frankmcsherry 8y ago

For people who want to fight about tracing vs ref-counting, please read this first, on how the two are dual and most collectors use both: http://www.cs.virginia.edu/%7Ecs415/reading/bacon-garbage.pdf http://www.cs.virginia.edu/%7Ecs415/reading/bacon-garbage.pd...