Subj : Re: Lock Free -- where to start
To   : comp.programming.threads
From : David Schwartz
Date : Tue Sep 27 2005 10:13 pm


    Let me just give you my general caveat about lock free code. First, lock 
free code is generally non-portable and extremely complex. Such code can 
easily contain bugs that are extremely difficult even for experts to spot. 
The complexity is almost always unnecessary.

    But worse, in most realistic cases, lock free tremendously *reduce* 
performance. The myth is that locks are expensive. The truth is that 
*contention* is expensive. Lock free algorithms allow code that is 
contending to run in parallel. Locks allow other code to run that probably 
won't contend.

    For example, consider three threads, A, B, and C. A and B both want to 
manipulate a queue, C wants to do something else entirely. Assume two CPUs. 
With a lock, either A or B will grab the queue lock. A or B will run with C 
and both threads will run at full speed with minimal contention. With a 
lock-free queue, A can run concurrently with B. C will have to wait, while A 
and B fight over the cache lines that contain the queues and its structures.

    Well, you say, this is a carefully crafted example. What if there's 
another processor? Guess what, you're still screwed. Because A and B running 
in parallel will saturate the front side bus as they bounce the queue 
structures back and forth. C will still run at a low speed and system 
performance will likely be worse than if A ran by itself and then B ran by 
itself.

    Lock free algorithms work great in kernels and low level threading 
libraries for a variety of reasons. Portability is not that important. The 
probability that there are other things to do is lower in core code (because 
everything passes through it). But for application code, or even most 
libraries on top of threading libraries, it's a pure loss.

    DS

.