5 ms·

> With reference counting there are no pauses How are you reclaiming cycles with no pauses?

by chrisseaton 5y ago

ncmncm 5y ago
I have had no occasion in the past three decades to make cycles. It smacks of poor discipline, or poor design.
- deathanatos 5y ago
  While I also haven't ever had a cycle in my decades as an engineer, it doesn't really answer the parent's question about pauses w.r.t. ref counting. Ref counting, in the general, isn't free. (Also, in the sense of releasing a cycle, that would be pretty quick, since a typical RC implementation is just going to leak it. Its where a large graph resource graph is successfully ref-counted to 0 that can cause a pause, theoretically, although that's another case I've not seen.)
  - ncmncm 5y ago
    The usual method is to have strategically placed "weak" references.
    - deathanatos 5y ago
      … yes (and I know), but that has nothing to do with the point being made here, which is about the compute time required to manage the memory.
- chrisseaton 5y ago
  Well good for you I guess - but that’s not a general solution for language implementation as it’s not sound for a language like Python. Which is why in practice most RCs include tracing. And the reverse as well - most tracers include a degree of RC. That’s the pragmatic solution in practice.
  - kragen 5y ago
    I think tracing GC was added to CPython after about 15 years, so I guess RC was a general enough solution for it for quite a while. Even today CPython refuses to collect cycles with finalizers. Smalltalk also only used RC from 01971 to the early 01980s. I think Perl still only does RC. Swift apparently also only does RC. People programming in those languages just design their programs to not create cycles, or include a weak reference in the cycle somewhere, like for Observer kinds of things. I'm not a fan of RC, myself. It's space-hungry, it creates unnecessary write traffic, it's unreliable (when you can have cycles), and it's slow. But there are lots of "not sound" and "not general" but "pragmatic" language implementations out there using it, without tracing. In practice, even.
    - ncmncm 5y ago
      Pervasive RC is the most costly GC. But it is fine where not pervasive, and even some places where it is. RC is about the last thing you would worry about slowing down your Python program. I RC'd a thing in a program, five years back. The program had a linked list in it. Increments and decrements happened on a scale of minutes. I did not agonize over it.
      - kragen 5y ago
        I mostly agree, except that I do think reference counting is a significant part of CPython's runtime slowness. Maybe 10%.
    - kragen 5y ago
      Confirmed, Perl still only does reference counting. No cycle collector.
- anamax 5y ago
  Cycles can happen in lots of ways. For example, heap allocated closures for functions with non-local references create a cycle when a pointer to the closure is stored in a non-local environment.
  - ncmncm 5y ago
    Yes, it is and has always been easy to make cycles. My point is that it is almost always about equally easy not to make cycles, if you are paying any attention.
    - ahtihn 5y ago
      The fact that you have to pay attention makes it significantly harder. You have to be aware that cycles can cause issues and you have to think about the impact of cycles on whatever you're doing.
      - ncmncm 5y ago
        So you say. But that does not match my experience. It has always been wholly trivial to know where the "weak references" go.
    - Ygg2 5y ago
      Using enough transition proves that difficulty of not making cycle is going to increase very, very fast.
- titzer 5y ago
  In my work, I regularly end up with cyclic data structures, e.g. the SSA IRs in several compilers I have worked on have oodles of cycles. And interpreters run user programs, which create cycles. I don't think this is a particularly fruitful line of discussion to strongly claim that cycles can just be avoided, or worse, that you're an idiot for having them. It's needlessly inflammatory.
  - ncmncm 5y ago
    I think your SSA cycles can be trivially reclaimed by arena means, no? Point is just that people get used to whatever they were directed to do for their CS class assignments, and get to thinking it is natural, and even unavoidable. That something somebody is used to not thinking about is not actually necessary can be a novel and fruitful idea. The cheapest GC is always no GC at all.
    - titzer 5y ago
      I've worked on 5 different SSA compilers. C1, C1X, Crankshaft, TurboFan, and Virgil. C1X and Virgil are written in safe, garbage-collected languages, while C1, Crankshaft, and TurboFan are all C++ and use arena allocators. Of these, in my totally subjective opinion, the two written in GC'd languages are a heck of a lot more productive to write in--like 10x as productive. They still run really fast, too. In fact, C1X was faster than C1, and Virgil is in the same ballpark or even better, though they do very significantly different analyses and optimizations in their pipeline. Crankshaft might have the edge on C1X in some respects, but I never did a direct comparison. TurboFan is by far the most incredibly intricate piece of software of my life and I'm convinced could not be written with ownership, acyclicity, or manual memory management without one or two suicides and a bugtail of security vulnerabilities decades long. I would have either walked out or have been forced to resign in disgrace for failing to deliver a workable product by making the call to prioritize memory management efficiency (by presumably using optimal malloc/free everywhere) over literally every other priority when building a piece of software--correctness, maintainability, team retention, extensibility, security, etc. It wouldn't have been the V8 way after all, because it was designed with regions quite extensively because even back then, because most VMs have long realized it is a waste of time to try to do anything more complicated and regions are basically el-cheapo GC for C++. > The cheapest GC is always no GC at all. I kind of chuckle here because the Virgil compiler proves you manifestly right and wrong simultaneously; it's a fully GC'd, semi-functional language with a self-hosted compiler written entirely in the language. Incidentally, in a careful style that doesn't allocate a whole lot or create a lot of garbage. It chooses efficient, C-like data structures for IRs and doesn't waste a lot of time on Java-like armored classes because I am sick of wasting my life on that. It bootstraps in less than 200MB of memory, compiling the entire compiler at full optimization in a single whole program compilation. Because I made the dumbest, simplest Cheney moving GC, without even generations, it doesn't even have a write barrier. But because it only allocates 200MB, when bootstrapping it doesn't even GC once. It's basically a giant, single region that is thrown away at process exit, and the mutator doesn't pay the cost of a single write barrier. (And the funny thing is, GC wouldn't even find that much garbage, because only about half of the heap does actually die, primarily because it's mostly IR that is always reachable--it's a whole program compiler, after all). It's basically your mythical perfect GC just because it has enough memory and I am damn well in my rights to spend it as I have.

> With reference counting there are no pauses How are you reclaiming cycles with no pauses?

ncmncm 5y ago

I have had no occasion in the past three decades to make cycles. It smacks of poor discipline, or poor design.

deathanatos 5y ago
While I also haven't ever had a cycle in my decades as an engineer, it doesn't really answer the parent's question about pauses w.r.t. ref counting. Ref counting, in the general, isn't free. (Also, in the sense of releasing a cycle, that would be pretty quick, since a typical RC implementation is just going to leak it. Its where a large graph resource graph is successfully ref-counted to 0 that can cause a pause, theoretically, although that's another case I've not seen.)
- ncmncm 5y ago
  The usual method is to have strategically placed "weak" references.
  - deathanatos 5y ago
    … yes (and I know), but that has nothing to do with the point being made here, which is about the compute time required to manage the memory.
chrisseaton 5y ago
Well good for you I guess - but that’s not a general solution for language implementation as it’s not sound for a language like Python. Which is why in practice most RCs include tracing. And the reverse as well - most tracers include a degree of RC. That’s the pragmatic solution in practice.
- kragen 5y ago
  I think tracing GC was added to CPython after about 15 years, so I guess RC was a general enough solution for it for quite a while. Even today CPython refuses to collect cycles with finalizers. Smalltalk also only used RC from 01971 to the early 01980s. I think Perl still only does RC. Swift apparently also only does RC. People programming in those languages just design their programs to not create cycles, or include a weak reference in the cycle somewhere, like for Observer kinds of things. I'm not a fan of RC, myself. It's space-hungry, it creates unnecessary write traffic, it's unreliable (when you can have cycles), and it's slow. But there are lots of "not sound" and "not general" but "pragmatic" language implementations out there using it, without tracing. In practice, even.
  - ncmncm 5y ago
    Pervasive RC is the most costly GC. But it is fine where not pervasive, and even some places where it is. RC is about the last thing you would worry about slowing down your Python program. I RC'd a thing in a program, five years back. The program had a linked list in it. Increments and decrements happened on a scale of minutes. I did not agonize over it.
    - kragen 5y ago
      I mostly agree, except that I do think reference counting is a significant part of CPython's runtime slowness. Maybe 10%.
  - kragen 5y ago
    Confirmed, Perl still only does reference counting. No cycle collector.
anamax 5y ago
Cycles can happen in lots of ways. For example, heap allocated closures for functions with non-local references create a cycle when a pointer to the closure is stored in a non-local environment.
- ncmncm 5y ago
  Yes, it is and has always been easy to make cycles. My point is that it is almost always about equally easy not to make cycles, if you are paying any attention.
  - ahtihn 5y ago
    The fact that you have to pay attention makes it significantly harder. You have to be aware that cycles can cause issues and you have to think about the impact of cycles on whatever you're doing.
    - ncmncm 5y ago
      So you say. But that does not match my experience. It has always been wholly trivial to know where the "weak references" go.
  - Ygg2 5y ago
    Using enough transition proves that difficulty of not making cycle is going to increase very, very fast.
titzer 5y ago
In my work, I regularly end up with cyclic data structures, e.g. the SSA IRs in several compilers I have worked on have oodles of cycles. And interpreters run user programs, which create cycles. I don't think this is a particularly fruitful line of discussion to strongly claim that cycles can just be avoided, or worse, that you're an idiot for having them. It's needlessly inflammatory.
- ncmncm 5y ago
  I think your SSA cycles can be trivially reclaimed by arena means, no? Point is just that people get used to whatever they were directed to do for their CS class assignments, and get to thinking it is natural, and even unavoidable. That something somebody is used to not thinking about is not actually necessary can be a novel and fruitful idea. The cheapest GC is always no GC at all.
  - titzer 5y ago
    I've worked on 5 different SSA compilers. C1, C1X, Crankshaft, TurboFan, and Virgil. C1X and Virgil are written in safe, garbage-collected languages, while C1, Crankshaft, and TurboFan are all C++ and use arena allocators. Of these, in my totally subjective opinion, the two written in GC'd languages are a heck of a lot more productive to write in--like 10x as productive. They still run really fast, too. In fact, C1X was faster than C1, and Virgil is in the same ballpark or even better, though they do very significantly different analyses and optimizations in their pipeline. Crankshaft might have the edge on C1X in some respects, but I never did a direct comparison. TurboFan is by far the most incredibly intricate piece of software of my life and I'm convinced could not be written with ownership, acyclicity, or manual memory management without one or two suicides and a bugtail of security vulnerabilities decades long. I would have either walked out or have been forced to resign in disgrace for failing to deliver a workable product by making the call to prioritize memory management efficiency (by presumably using optimal malloc/free everywhere) over literally every other priority when building a piece of software--correctness, maintainability, team retention, extensibility, security, etc. It wouldn't have been the V8 way after all, because it was designed with regions quite extensively because even back then, because most VMs have long realized it is a waste of time to try to do anything more complicated and regions are basically el-cheapo GC for C++. > The cheapest GC is always no GC at all. I kind of chuckle here because the Virgil compiler proves you manifestly right and wrong simultaneously; it's a fully GC'd, semi-functional language with a self-hosted compiler written entirely in the language. Incidentally, in a careful style that doesn't allocate a whole lot or create a lot of garbage. It chooses efficient, C-like data structures for IRs and doesn't waste a lot of time on Java-like armored classes because I am sick of wasting my life on that. It bootstraps in less than 200MB of memory, compiling the entire compiler at full optimization in a single whole program compilation. Because I made the dumbest, simplest Cheney moving GC, without even generations, it doesn't even have a write barrier. But because it only allocates 200MB, when bootstrapping it doesn't even GC once. It's basically a giant, single region that is thrown away at process exit, and the mutator doesn't pay the cost of a single write barrier. (And the funny thing is, GC wouldn't even find that much garbage, because only about half of the heap does actually die, primarily because it's mostly IR that is always reachable--it's a whole program compiler, after all). It's basically your mythical perfect GC just because it has enough memory and I am damn well in my rights to spend it as I have.