Subj : Re: STL Containers w/ Virtually Zero-Overhead Lock-Free Reads...
To   : (Usenet)
From : Joe Seigh
Date : Fri Sep 23 2005 11:27 am

David Abrahams wrote:
> We could make vector::push_back lock-free at a complexity cost (O(N)
> instead of amortized O(1)), and then vectors could *almost* be used as
> queues.  But you still don't have the right interface to remove
> elements from such a queue because you need to get the element value
> and remove it in one operation.  Even if we solve that, vectors are
> general-purpose containers; it's not possible to make sensible
> semantic guarantees for arbitrary combinations of operations.

I have done a linked list implementation where the find operation
could be done lock-free and just the remove operation used a
conventional lock (and the iterator value without redoing the
lookup).  Don't worry.  It was just an experiment.
> 
> Suppose we had lock-free vectors.  Now one thread calls
> sort(v.begin(), v.end()) while another calls v.push_back(5).  What
> does either thread see?  It seems to me that even if it's possible to
> come up with coherent semantics for this case (which in itself is
> debatable), it's impossible to come up with _useful_ semantics.
> If containers are to be shared across threads, their state will almost
> always be just a small piece of some larger invariant, in which case
> you'll need to synchronize or "lock-free-ize" at a different level.
> 
> And once you start handing out forward/bidirectional/random-access
> iterators, references, and pointers into a data structure, the
> implementor of the data structure loses _all_ control over the kind of
> atomicity you need when removing elements from queues.  So, this
> doesn't look like a subtle problem to me, not at all.
> 
It's not.  And it's an easy to avoid problem.   Just don't create
lock-free containers.  You don't really need them.  Not that I
think anyone is going to listen to me here.  They'll go ahead and
do it anyhow and they won't wait for it to be done "properly".
You need to convince them to wait until (if ever) C++ supports doing
it properly.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software. 

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

.