3 ms·

Ref counting doesn’t work for cyclic data structures

JoshTriplett 1y ago
It doesn't fully handle the memory management, but it handles having shared references. You can use weak references or manually break the links when you want to free something. Or you can use unsafe raw pointers, which frankly seem simpler. Either way you're going to wrap it in a data structure that encapsulates all the details.
NobodyNada 1y ago
Sure it does. Make the backreferences weak, or use a library that provides cycle detection (or even full-on tracing GC if you really want).
- pizlonator 1y ago
  That changes the semantics. It won’t work for a graph for example.
  - NobodyNada 1y ago
    Right. The comment you replied to said "Rc/Arc and some manual management" -- "some manual management" implying that you need to account for the change to semantics in the manner appropriate for your application.
    - JoshTriplett 1y ago
      (Note that I edited my comment for clarity since the original reply. My original comment just said "reference counting".)
      - pizlonator 1y ago
        The key part I agree with most in your edited comment is that unsafe raw pointers are the easiest way to deal with cycles. I think this is key. RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. In RC, you’d have to walk the graph to break cycles. That’s a rather important difference from how you’d manage a cyclic data structure in C, C++, Java, C#, or any GC’d language. In C/C++, you’d delete what you know to be dead; in Java et al it would be enough to kill the references that point at the outer edges of the dead subgraph. But you wouldn’t have to walk the subgraph to detangle the cycle. I think it really is worse than that; ie as you say, folks will just do anything but RC in that case. In Rust the safe bet would be to just shove all the nodes into an array and use indices (yuck!!!). But likely a lot of code with use raw pointers instead (also yuck). The whole thing where you reference count cyclic data structures is just too painful for sensible people
        adastra22 1y ago
        > RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. That’s exactly what weak references do.
        JoshTriplett 1y ago
        For a graph, I agree. For a tree with parent pointers, I'd absolutely use Rc, with Weak for the parent pointers.
adastra22 1y ago
Rc has downgrade and the Weak type explicitly for this purpose.
cyberax 1y ago
It works well. One easy trick is to have one reference count for the whole graph.

It doesn't fully handle the memory management, but it handles having shared references. You can use weak references or manually break the links when you want to free something. Or you can use unsafe raw pointers, which frankly seem simpler. Either way you're going to wrap it in a data structure that encapsulates all the details.

NobodyNada 1y ago

Sure it does. Make the backreferences weak, or use a library that provides cycle detection (or even full-on tracing GC if you really want).

pizlonator 1y ago
That changes the semantics. It won’t work for a graph for example.
- NobodyNada 1y ago
  Right. The comment you replied to said "Rc/Arc and some manual management" -- "some manual management" implying that you need to account for the change to semantics in the manner appropriate for your application.
  - JoshTriplett 1y ago
    (Note that I edited my comment for clarity since the original reply. My original comment just said "reference counting".)
    - pizlonator 1y ago
      The key part I agree with most in your edited comment is that unsafe raw pointers are the easiest way to deal with cycles. I think this is key. RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. In RC, you’d have to walk the graph to break cycles. That’s a rather important difference from how you’d manage a cyclic data structure in C, C++, Java, C#, or any GC’d language. In C/C++, you’d delete what you know to be dead; in Java et al it would be enough to kill the references that point at the outer edges of the dead subgraph. But you wouldn’t have to walk the subgraph to detangle the cycle. I think it really is worse than that; ie as you say, folks will just do anything but RC in that case. In Rust the safe bet would be to just shove all the nodes into an array and use indices (yuck!!!). But likely a lot of code with use raw pointers instead (also yuck). The whole thing where you reference count cyclic data structures is just too painful for sensible people
      - adastra22 1y ago
        > RC pointers don’t give you the ability to say: ok, I now know that this subset of the graph is dead because reasons so delete it. That’s exactly what weak references do.
      - JoshTriplett 1y ago
        For a graph, I agree. For a tree with parent pointers, I'd absolutely use Rc, with Weak for the parent pointers.

adastra22 1y ago

Rc has downgrade and the Weak type explicitly for this purpose.

cyberax 1y ago

It works well. One easy trick is to have one reference count for the whole graph.