Subj : Re: recursive mutexes
To   : comp.programming.threads
From : David Butenhof
Date : Thu May 19 2005 03:07 am

Uenal Mutlu wrote:
> "Markus Elfring" wrote
> 
>>>And IMO they are also slower than a method which uses locking, even
>>>if this might sound counter-intuitive.
>>
>>Would you like to show benchmarks for such differences in execution speed?
>>(Other papers contain statistics that show the opposite runtime behaviour.)
> 
> This assumption is by the fact that you need to put more code to check.
> That is: more code must be executed;  even just two or three if statements
> can mean too much compared to a classical mutex method using atomic counter.

Nobody who knows anything at all about the implementation of a blocking 
mutex could possibly make a statement like this. It is just too 
incredibly naive for words.

A basic lock-free operation, for example, is an atomic add. Even a 
spinlock, at the absolute minimum, has an equivalent lock free 
synchronization sequence at its heart. That's what a spinlock is. Yet 
even a spinlock has MORE context than that. And it blocks, whereas the 
atomic add doesn't. A spinlock is the tiniest core of a functional 
blocking mutex, with prioritized (that is, SORTED) wait queues and other 
context. A recursive mutex is a blocking mutex with yet more state (it's 
irrelevant in this context that the additional state is small).

And yet... all of this is "less complicated" than an atomic add? Do tell.

Indeed, state of the art lock-free is way beyond atomic add, though it 
all stems from the same principles. And while all of it adds to the raw 
unthreaded queue or tree algorithms, the important goal here (the part 
we're all by now pretty sure you don't understand) is that the 
algorithms can now run CONCURRENTLY, and they can SCALE way beyond the 
simplistic serialization imposed by implementing the same algorithm 
under a mutex. This would be true, and an enormous advantage, (in 
properly designed code!), even if the lock-free overhead DID exceed the 
overhead of a mutex. But in most practical cases it really doesn't... a 
robust mutex is a fairly complicated beast. Oh yes... and a completely 
SERIALIZED beast, as well.

-- 
Dave Butenhof, David.Butenhof@hp.com
HP Utility Pricing software, POSIX thread consultant
Manageability Solutions Lab (MSL), Hewlett-Packard Company
110 Spit Brook Road, ZK2/3-Q18, Nashua, NH 03062

.