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.
http://www.ffconsultancy.com/?u
.



Relevant Pages

  • Re: vbs output to txt file
    ... the reference count to that object will be decremented. ... As does going out of scope:) ... You are religiously setting objects to nothing and not ... and so am seriously lacking in both scripting expertise ...
    (microsoft.public.scripting.wsh)
  • Re: Lock-free reference counting
    ... The scope of t is the entire function foo, ... The reference's lifetime is considerably shorter than ... The only way for it to collect it is if no reference is ... Bindings are introduced by various language constructs. ...
    (comp.programming)
  • Re: Lock-free reference counting
    ... GC cannot collect sooner than reference counting if the exact same ... A GC is completely oblivious to scope because scope only exists at the ... All that matters to the GC is whether or not the running program is still ... Reference counting keeps the value around until the reference is explicitly ...
    (comp.programming)
  • Re: Article of interest: Python pros/cons for the enterprise
    ... create a less flexible Python feature that achieves the ... you can create a temporary object whose reference count will become ... especially in a complex multi-statement scope. ... If you can then request that arbitrary actions be taken automatically when those events happen, you can pair up resource acquisitions and releases very easily. ...
    (comp.lang.python)
  • Re: Lock-free reference counting
    ... GC cannot collect sooner than reference counting if the exact same ... A GC is completely oblivious to scope because scope only exists at the ... Reference counting keeps the value around until the reference is explicitly ... pointer keep the object alive if it's changed to point somewhere else ...
    (comp.programming)