Re: [boost] [proposal] Atomically Thread-SafeReferenceCountingAlgorithm...

From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-10-20 18:36:50

Chris Thomasson wrote:

> I think my scheme could possibly be more efficient because all of the
> pointer-ops are 100% lock-free, and most of the reference counts are
> 100% lock-free... Humm... I would have to see a sketch of the
> algorithm you have in mind Peter...

Basically... using copy/replace on a shared_ptr would make it behave 
atomically ('global') and using the other ops would make it non-atomic 
('local'/semi-local).

shared_ptr copy() const

    take read (rw)spinlock for pointer to count
    make a copy of *this
    release spinlock
    return copy

void replace( shared_ptr const & rhs )

    take write (rw)spinlock for pointer to count
    *this = rhs
    release spinlock

As I understand your scheme, you take a spinlock in your equivalent of the 
copy operation (in atomic_add_load_strong). However you are able to avoid 
the write lock in the replace operation by deferring it until the refcount 
reaches zero, something like (best guess):

void replace( ptr const & rhs )

    atomic_decrement( this->count ) // #1

    if reached 0

        take write lock // #2
        re-check for zero
        if true, invoke destructor
        else ???, someone sneaked a 'copy' between #1 and #2

    swap this and rhs

except I don't see the "re-check for zero" part in your assembly, so I might 
be missing something; how do you protect against that scenario?

I can't easily do that for shared_ptr since its swap is not atomic 
(shared_ptr is double-wide) but it could be possible... but I'm not sure 
whether it's worth it, since in a typical application the copy ops will 
outnumber the replace ops, so avoiding only the write lock may not be that 
important.