Re: Threads: New Win32 Implementation

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-09-07 13:55:54

--- In boost_at_[hidden], "Bill Wade" <bill.wade_at_s...> wrote:
> > From: William Kempf [mailto:sirwillard_at_m...]
> >
> > A corner case indeed!  It's very rarely a good idea to use node 
level
> > locking here.  The granularity is much too small and will lead to
> > very poor performance.
> 
> In practice you'd lock enough nodes at once (or make node processing
> expensive enough) that the amortized cost of the locks was less 
than the
> advantage gained by allowing multiple processors to attack the 
problem.
> 
> If you have just one processor and are using MT because it is a 
good way to
> express the solution to the problem, it becomes much more likely 
that
> locking the entire list will be appropriate.

One of us isn't being clear enough.  If all that you're doing is 
traversing the list then all you're doing is reading, in which case 
the optimal solution isn't node level locking but list level read-
locking.  Even if on a multiple processor machine you could convince 
me that node locking were faster, since we're only reading here the 
race condition I mentioned is irrelevant and so the locks need not 
overlap.

Now, if you're modifying the data contained in the list the lock is 
more appropriate on the data object, not the node, and the race 
condition is again irrelevant.

Now, ir you're inserting or removing nodes, the race condition is 
important, but only very rare uses of this would benefit in speed 
from node level locking, multiple CPUs or not.  Why?   Because the 
operation is so simple that a lock won't be held long enough to cause 
any real contention, or it's complicated enough that you'll have to 
lock several nodes in order to insure you don't cause a race 
condition with other insertion/deletions that are occuring.  In this 
case, a single list level lock is usually (not always) faster.

That's why I call it a corner case.  There are some very rare 
situations in which you can eke out a little better performance.  But 
the parameters have to be just so (multiple CPUs, long transaction, 
minimal number of locks needing to be acquired to prevent race 
conditions, etc.) in order for this to be used efficiently.  It's 
going to be very rare that you've got something that fits this bill, 
let alone fits it often enough to warrant this level of optimization.

If we didn't allow for this, we'd be wrong.  But we do.  We just make 
it slightly more cumbersome to do (for the programmer, not for the 
compiler).  Non-issue, AFAIC.

Bill Kempf