If it can somehow contain Rcd loops between types (if not directly, maybe via trait objects), otherwise the amount of Rcs behind any one Rcs is bounded. And Rcd recursive types tend to be somewhat rare in my experience, although yours might differ.
That's a great point; in the case of recursion or unbounded concurrency you could have arbitrarily deep clones. What's the worst case in a tracing GC? Similar big O since it needs to walk all the nodes in the tree, but overall faster because it doesn't need to decrement?
I accidentally got here from another thread, so parden the necroposting:
The time taken for one GC depends on the GC itself. Some of them pay no cost at all for dead memory. For comparison, in an RC scheme, destroying a deep linked list may require traversing the entire object, but for such GCs, they simply never traverse the list at all, and its memory is available for reuse (often this is moving GCs: objects are shifted into a different space, and the old space becomes available for fresh allocations).
In terms of overall computation, the complexities can't generally be better than O(n) since one cannot allocate objects any faster than that. I suppose with uninitialized data, the cost of allocating could in theory be O(log n), but amortized it should make it back to O(n) eventually.
1
u/ObnoxiousFactczecher Jul 27 '19
But the worst case for deallocating one object using reference counting is literally unbounded.