[TheLoneWolfling]

Why do people assume that cleanup in reference counting has to be synchronous?

You can deal with deallocation chains in reference-counted systems without having arbitrarily-long pauses. You keep a stack of <pointers to items to be removed + current child index in item>. When something's reference count goes to 0, push it onto the stack, with a child index of zero. Every so often, pop the last item off of the stack, if (the child index is after the last child) {deallocate the memory}, else {decrement the reference count of the child of the object indexed by the child index, pushing that onto the stack with a child index of 0 if the child is now dead, and push it back onto the stack with an incremented child index}. You can do any/all of this in batches.

[andrewchambers]

All that extra logic sounds like its approaching garbage collector territory... The more you massage it, the closer it becomes.

[TheLoneWolfling]

To be fair: reference counting is a garbage collector.

[theseoafs]

It's well-known that you can incrementally free objects that are known to be garbage but it's not usually implemented for reference counting since it's not typically seen as a good fit because it undermines the advantages of reference counting a bit: now, objects aren't freed deterministically when they become garbage (that is objects are destroyed at unpredictable times) and you're now introducing unpredictable pauses into the language runtime to free garbage objects (short though those pauses may be). Maintaining the free stack also adds overhead. It's just not a very good fit.

[TheLoneWolfling]

You cannot have both deterministically-freeing GC and GC without arbitrarily-long pauses. That's kind of a given.

[pcwalton]

> Why do people assume that cleanup in reference counting has to be synchronous?

It doesn't, but it most real-world implementations of RC it is.