Subj : Re: STL Containers w/ Virtually Zero-Overhead Lock-Free Reads...
To   : (Usenet)
From : Chris Thomasson
Date : Fri Sep 23 2005 07:21 pm

>> I could be missing something important, but it seems to me that if you
>> want to "actually apply some algorithms to it" then a lock-free
>> container is of little use,

Not true.




>> since you get synchronization at the wrong
>> level of granularity.  You'd need algorithm-level synchronization,
>> rather than container-level synchronization, in that case.

I believe you might be misunderstanding what I mean by virtually
zero-overhead lock-free reads. User-defined algorithms are not restricted
from using their own form(s) of mutual exclusion to protect
“critical-sequences” of operations that are required to be executed
atomically:


Thread_A {
   user_app::mutex::t_guard lock( m_lock );
   sort( v.begin(), v.end() );
}

Thread_B {
   user_app::mutex::t_guard lock( m_lock );
   v.push_back(5);
}


This is perfectly fine; a well built generic lock-free read container doesn’t
need to rely on internally defined forms of mutual exclusion in order to
provide "read-only access" that doesn't use any nasty atomic operations
and/or StoreLoad style memory barriers...




> Suppose we had lock-free vectors.  Now one thread calls
> sort(v.begin(), v.end()) while another calls v.push_back(5).

These would be considered writes.


> What does either thread see?

It depends on which thread executes first; remember writes are mutually
excluded.




> 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.

This is completely compatible with virtually zero-overhead lock-free reads.
Many existing application defined algorithms that decided to use STL
containers in multithreaded environments use mutexs to protect everything
anyway; therefore they are already compatible with the requirements of the
highly flexible lock-free algorithm I am using. Application defined
algorithm can literately pick and choose exactly which if their "read-only
operations" can be executed without a lock. For instance, a thread that
makes frequent read-only const_iteration's over a shared collection would be
a great candidate to "lock-free-ize"...

:)



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

.