RE: [boost] Re: Re: Re: Re: problem with shared_ptr

From: Hurd, Matthew (hurdm_at_[hidden])
Date: 2003-11-19 18:01:52

> On Behalf Of Philippe A. Bouchard
> Sent: Thursday, 20 November 2003 8:58 AM
<snip>
> 
> >> The interesting part is to speed up existing code with minimal
> >> dependencies,
> >> knowing it cannot be faster.  I am looking forward for eventual
> > benchmarks
> >> against Hans-Boehm's garbage collectors ;)  To be honest with you,
> > working
> >> on this full-time...  I would implement my "real-time" collector to
> > get
> >> rid
> >> instantaneously of cyclic references and add atomic reference count
> >> operations immediately.
> >
> > Yep, a reference without the need for a lock would be a big win.
Not
> > sure how you would make this safe in the garbage collector though as
a
> > mark sweep could cause a pause.  Perhaps there is an optimistic
> > technique, such as a timestamp/cyclestamp, than can rollback on
> > conflict, perhaps over two phases.  I'll have to think some more
about
> > such optimism, perhaps you could use such an approach for updating
the
> > reference count with a roll-back and try again semantics...  Hmmm.
> 
> Again, there are many solutions but I personnaly believe destruction
of
> cyclic objects should be done intantaneously at the cost of some
immediate
> speed (as compared to a garbage collector).  What I was thinking of
> implied
> 1 more pointer into the smart pointer increasing its size by
sizeof(void
> *)... (sizeof(new_shared_ptr) would be == 3; sizeof(new_shifted_ptr)
== 2
> ==
> sizeof(actual_shared_ptr)).  2 counters would therefore be necessary
but
> the
> overall benefits are more important.  If there is interest I could
figure
> out something because it needs portable low-level solutions...
> 
> Emotionnal turbulence is sometimes useful as for those discussions,
not
> everybody is working full-time on advanced C++... to respond to what
Matt.
> was saying... ;)

I like your idea of the cyclically aware shared_ptr.  There are many
situations where I'd be happy to pay for it in speed and or size.

I already need one as I have a structure in one old bit of code where
components have pointers back to their parents and I get myself into a
mess...  I live with it in this case as the objects lifetime corresponds
to the process life time.  Relying on atexit irks me, though less than
revisiting code that does the job ;-)

My other goal is to find a way to implement one of the modern techniques
for lock free or wait free concurrency to try to improve on the typical
40 to 1 (sometimes 200 to 1) difference you see in locking increments
and normal increments.  When I get into the papers they inevitably use
some kind of CAS primitive which doesn't seem to buy that much for the
simple case of an increment, but I'm still reading and learning and
trying to understand the implications.

Perhaps a lock free list of references might be another alternative.
Also win32 has introduced such a list as a primitive recently...

The fundamental idea is to cook up a scheme where optimistic concurrency
is a benefit due to a likely lack of collisions.  The overhead of
failing and retrying an update is worth it if you can do two things:
avoid bus locking and have a lowish collision probability...

I've seen one paper which takes advantage of incrementing the ref count
before dealing with the reference as it is OK to have a count too high
but not one that is too low.  It has implications for GC as well.
"Lock-Free Reference Counting" , Detlefs, Martin, Moir, Steele from Sun.
Citeseer will pull it up if you're interested.  It still seems to use
CAS though :-(

Anyway I think I'm drifiting outside the domain of boost here.  So I'll
stop.

Regards,

Matt Hurd.

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments.  Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited.  Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument.  Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.