[gclist] ref-counting performance cost

[Boehm, Hans]

> -----Original Message-----
> From: Bob Kerns [mailto:Bob.Kerns@brightware.com]
> Perhaps your technique has relevance to non-traditional GC 
> environments,
> such as distributed GC, or other non-flat memory models, 
> where the cost
> tradeoffs are distinctly different?
Or embedded systems, where the space overhead of a tracing collector may not
be acceptable?

It seems to me that whether or not an improved reference counting algorithm
is interesting depends entirely on the characteristics of the algorithm.  If
you can reclaim cycles immediately without increasing the cost of pointer
assignments by more than a constant factor over a traditional reference
counter, I would find that astonishing, and almost certainly worthy of
publication, probably even as a purely theoretical result.  (In fact, I
would expect that to be provably impossible, though I don't recall such a
proof.  So the real question becomes what you lose in the process.)
> 
> Anyway, as to your last point: this technique is not exactly 
> rare. It's
> often later optimized with a reference count (to avoid the copy) and
> copy-on-write (to preserve the un-shared semantics).
Unfortunately, this brings back memories of the C++ "string" class, in my
opinion a low point of the C++ standard.

The C++ string class ("basic_string" really) went this route.  Then the
standards committee determined that the existing reference counted
copy-on-write implementations actually didn't satisfy any reasonable
specifications, and there was no way to fix the implementations.  So they
attempted to legitimize them. (See 21.3, paragraphs 5 and 6.)  The result is
just about incomprehensible.  (If s is a string, the expression s[0] ==
s[1], the most natural way to compare the first two characters, still
appears to be illegal in some contexts, though not others.  Last I looked at
it more thoroughly, I convinced myself that the spec is also wrong, and the
traditional reference counted implementations are still broken.  But I
wouldn't bet on that one way or the other.)

Things get much worse if you add in threads ...

The SGI implementation ended up going back to deep copy (for "string", not
"rope").  I'm unconvinced that any other implementation of the string
interface is usable in the presence of threads.

The bottom line is:  If you choose to go here, tread VERY carefully.

Hans