Lock vs. Mutex

here’s a quick brainteaser for you. suppose you really want to find all the prime numbers in a certain range, and store them in a list<uint> . and also suppose that you want to parallelize that calculation to make it as quick as possible. you then need to synchronize access to the list so that it’s not corrupted by add operations performed in multiple threads. would it be better to use a c# lock (clr monitor) or a windows mutex to protect the list of primes?

parallel.for(2, 400000, n => 
{ 
    if (isprime((uint)n)) 
    { 
        mutex.waitone(); //or maybe lock(something) would be better? 
        primes.add((uint)n); 
        mutex.releasemutex(); 
    } 
});

it turns out the answer depends on the number of processors you have. if you limit the parallelization to only a single processor, the mutex version takes “only” 2x longer to run on my machine. however, when i let the loop parallelize across 2 processors, the mutex version becomes 90x slower (!!!). finally, when parallelized across 4 processors, the mutex version grinds to a complete halt and runs 200x slower than the other version. in fact, the more i parallelize, the worse the performance of the mutex-based version becomes.

this is not very surprising considering that the mutex introduces a strong bottleneck and requires a system call to acquire and release. in fact, even if the mutex is free, it takes a system call to acquire and release it. but this seems also true of the lock keyword; how can it be so fast?

in fact, if you use the visual studio concurrency visualizer, you can see an interesting phenomenon. here are the application’s threads in the mutex-based version – the reddish pink is time spent doing synchronization, the green is when the threads are actually running:

here’s what it looks like zoomed in to a tiny segment of less than 10 milliseconds:

and here are the threads in the lock-based version (note that the bottom two threads complete their part of the work very quickly, so the synchronization you see towards the end is simply thread pool worker threads waiting for work, and not synchronization induced by our algorithm):

it is clearly evident that the lock-based version introduces almost no synchronization. how can that be? after all, there must be at least some contention over the lock, even though it might be faster to acquire?

it turns out (and this is partially documented elsewhere ) that the clr monitor tries spinning for several hundred cycles before issuing a true wait on a kernel event handle. because the time we spend inside the lock is very short, it’s always the case that the lock is released before the waiter gives up on the spinning (busy waiting). this is why we don’t see any synchronization, and, as a corollary, don’t incur any kernel transitions and expensive context switches.

although this example is overly pessimistic, it illustrates well that you should take care to choose the synchronization mechanism that does exactly what you need and not more; specifically, if you don’t need the extra abilities of the mutex (such as cross-process synchronization), you should stick with the simpler lock.

i am posting short links and updates on twitter as well as on this blog. you can follow me: @goldshtn