Re: Lock-free reference counting

Juha Nieminen wrote:
Jon Harrop wrote:
Juha Nieminen wrote:
Chris M. Thomasson wrote:
The GC might collect sooner wrt your example once in a blue moon.
GC can *not* collect sooner than reference counting if the same
scoping rules are used. It's just physically impossible.

No, scope and value lifetimes are completely separate concepts. In
particular, scope does not persist to run-time and, consequently, garbage
collectors are completely unaware of scope and are not limited by scope
in any way.

But garbage collectors are aware of existing references pointing to
objects. The GC can collect only when there are no such references. If a
reference is dropped, then the object could be immediately destroyed
with reference counting.

The GC does not predict anything and there is no magic: it simply scans
all live references

That's exactly my point: The references must be destroyed or changed,
ie. made "not life", in order for the object to be collectable. But if
the reference was actually reference-counted, the mere act of destroying
or changing it would destroy the object immediately.

Absolutely, yes, this is all technically correct. The problem is that
determining when a reference ceases to exist is prohibitively difficult to
do accurately in general and, consequently, a very coarse-grained solution
is often used instead, such as destructing variables only when they fall
out of scope in the source code.

This has two main advantages:

1. Counters are rarely bumped, greatly improving performance because bumping
counters is very expensive.

2. Collection is deterministic and predictable, making this approach ideal
for memory constrained systems, real-time systems and critical systems.

However, this also has two disadvantages:

1. Values are often only reachable for a fraction of their scope in
practice, so scope-based reference counting keeps values alive a lot longer
than necessary.

2. Reference counting is prone to avalanches of deallocations when entire
data structures fall out of scope. This causes long pauses which can
prohibit soft real-time.

The first disadvantage can be addressed by the programmer manually fiddling
with scopes but this is akin to manual memory management and rarely buys
you a lot in practice because scopes need to overlap in real code. The
second disadvantage can be addressed by adopting a more sophisticated
reference counting algorithm like the ones Chris has proposed but the main
implementational advantage of reference counting is simplicity so today's
language implementors typically drop reference counting and pick up an
accurate GC at this point.

Dr Jon D Harrop, Flying Frog Consultancy Ltd.