Mirror of forum.nim-lang.org

13754 :: A try to collect cycles with ARC

• eagledot (orginal) [2026-02-28T17:44:59+01:00] view original

  Last few days i have been trying to make ARC (hooks) collect cycles. Based on the observation that cycles lead to a redundant increment in reference-count, which prevent release/deallocation of resources with naive reference-counting. So for each "copy" hook, we detect if a new "Edge" will lead to a cycle, if yes, we increment the "cycle" counter, rather the "Ref" counter. This means we will always be able to trigger release of resources based on the scope-based reference counting. (but in some rare cases it could lead to pre-emptive deallocation).

  
  type
      ManagedPointer*[T] = object
          # Shared information/memory
          memory*:ptr T
          ref_counter*:ptr int
          cycle_counter*:ptr int
          
          # per instance information.
          isCycle*:bool
          tId*:TypeId    # runtime Type information
  Run

  All ref-graph topology changes happen during destroy and copy , hence making it possible to use a single-lock and should work across threads ! I think its possible to model various types of recursive data-structures, and it works because for most of such data-structures it is enough to just look at a single neigbour to detect if a cycle would occur. (which makes cycle-detection fast enough)

  In rare-cases like this:

  
  
  type
    Test = object
       a:int
       self:ManagedPointer[Test]
       self2:ManagedPointer[Test]
  
  
  var x = initMangedPointer[Test]()
  var y = initManagedPointer[Test]()
  
  x.self = y
  y.self = x   # a cycle.
  
  # at some point..
  
  var z = initManagedPointer[Test]()
  y.self2 = z  # at this point z is also reachable by `x` (techically), but even `x` may not be aware of this
  
  `=destroy`(z)  # z goes out of scope.
  `=destroy`(y)  # y goes out of scope  (this will free the object pointed to by z)
  
  x.self.self2.a           # error. ( recursive manual access)
  Run

  In above case recursive manual access as x.self.self2.a generates an error, and is only possible if user itself is keeping track of such complex relationships. Such situations will be difficult to model anyway with a predictable latency, but i think could still be tracked and user could be informed. (we can even defer the deallocation for such cases and just deallocate at the end of programme).

  I am very new to garbage-collection literature, and has only worked on it for last few days, its possible i made a blunder . Just putting it here for feedback!

---

• Araq (orginal) [2026-02-28T18:00:55+01:00] view original

  That's a very old idea and it suffers from the fact that every pointer assignment can trigger an O(n) traversal, easily O(n²) complexity when you build up a list!

  Trial deletion avoids this at the cost of not freeing cyclic garbage immediately, but delayed. And the costs are amortized which is good. (Yes, really! Been there, done that...)

---

• eagledot (orginal) [2026-02-28T18:45:56+01:00] view original

  Hey @araq, thanks for inputs, i am still to understand trial-deletion better.

  I agree with your traversal costs, but it won't be O(N) every time and would depend on the data-structure. For example for double-linked lists it would be constant, as previous neightbour would just be enough to detect a cycle. Still it also depend on how fast actual cycle-detection is, if it is <10 milliseconds for 100k nodes (that is for each assignment a N length cycle is created, worst-case), it may still be practical . But yeah may be i need more number to be sure!

---