[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

food for thought re: string representations ["Boehm, Hans" <address@hidd

From: Michael Livshin
Subject: food for thought re: string representations ["Boehm, Hans" <address@hidden>] RE: Re: [gclist] ref-counting performance cost
Date: 11 Oct 2000 20:45:36 +0200
User-agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (20 Minutes to Nikko)

just caught this on the GC mailing list.  look for the comments on the 
C++ string class near the end.

--- Begin Message --- Subject: RE: Re: [gclist] ref-counting performance cost Date: Wed, 11 Oct 2000 09:53:39 -0700
> -----Original Message-----
> From: Bob Kerns [mailto:address@hidden
> 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.


--- End Message ---

SIGTHTBABW: a signal sent from Unix to its programmers at random
intervals to make them remember that There Has To Be A Better Way.
                -- Erik Naggum

reply via email to

[Prev in Thread] Current Thread [Next in Thread]