[boost] Re: Boost.Threads: Do we need all those mutexes?

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2004-07-09 20:30:45

On Jul 9, 2004, at 7:10 PM, Glen Knowles wrote:

>> From: Howard Hinnant [mailto:hinnant_at_[hidden]]
>> My intention with the read/write lock stuff was simply that
>> these guys needed to at least support try locks.  That is
>> needed so that you can do assign-like locking between two objects:
>>
>> {
>> lock_both<write_lock, read_lock> l(a.mut(), b.mut());
>> a = b;
>> }
>>
>> Without try locks, lock_both can't be made to work without risking
>> deadlock.
>
> Lock_both can be made to work with try locks? Either you have a way to
> deterministicly set the order you lock the mutexes or you have 
> problems. You
> can avoid deadlocking with try lock, but you will fail to get the pair 
> of
> locks in cases were you would have gotten it by waiting. I suppose you 
> could
> just keep try-locking both ways until you get it, but that's not good 
> for
> performance. :)

Well actually keep try-locking both ways is what I've been doing.  I'd 
agree with you that in a heavily contested context, performance could 
theoretically suffer arbitrarily badly.

> One solution to this problem would be mutex::operator<

<nod>  I just implemented lock_both::lock two ways:  Once just keep 
try-locking both ways, and once locking in the order of the addresses 
of the locks (with only two locks in the test, this was a safe 
operator<).  My test looks like:

#include <iostream>
#include <fstream>
#include <numeric>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include <stddef.h>
#include <msl_thread>

template <class F>
float
test(F f)
{
     std::vector<float> t;
     int i;
     for (i = 0; i < 10; ++i)
         t.push_back(f());
     while (i < 10 && std::accumulate(t.begin(), t.end(), 0.0) < 1.0)
     {
         t.push_back(f());
         ++i;
     }
     std::sort(t.begin(), t.end());
     return (float)(std::accumulate(t.begin(), 
t.end()-(ptrdiff_t)(t.size()/10), 0.0) / (t.size()-(t.size()/10)));
}

Metrowerks::try_mutex m1;
Metrowerks::try_mutex m2;

void
foo()
{
     for (int i = 0; i < 10000; ++i)
     {
         typedef Metrowerks::try_mutex::scoped_try_lock Lock;
         Lock l1(m1, false);
         Lock l2(m2, false);
         Metrowerks::lock_both<Lock, Lock> l(l1, l2);
     }
}

float
time_lock_both()
{
     clock_t t = clock();
     Metrowerks::thread t1(&foo);
     Metrowerks::thread t2(&foo);
     t1.join();
     t2.join();
     t = clock() - t;
     return (float)(t/(double)CLOCKS_PER_SEC);
}

int main()
{
     std::cout << test(time_lock_both) << '\n';
}

That is, I send two threads to do nothing but fight for getting the two 
locks atomically for 10000 times each.  This is running on top of Mac 
OS X Posix threads (BSD subsystem) using Metrowerks CodeWarrior Pro 
9.2, all opts on for speed.  The templated test function runs the test 
repeatedly, at least 10 times, and maybe more until it spends at least 
1 second testing.  Then it throws out the slowest 10% of the runs and 
averages the fastest 90%.  This seems to give fairly consistent timing 
results for me, though there is still some variation.

I ran the test with lock_both::lock implemented both ways.

With keep try-locking both ways until you get it:

G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.321111
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.366667
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.325556

With decide which to lock first based on address:

G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.315556
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.314444
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.33

As a sanity check I reran the test in a non-contested mode (but I 
wouldn't expect major differences in this mode):

float
time_lock_both()
{
     clock_t t = clock();
     Metrowerks::thread t1(&foo);
     t1.join();
     Metrowerks::thread t2(&foo);
     t2.join();
     t = clock() - t;
     return (float)(t/(double)CLOCKS_PER_SEC);
}

With keep try-locking both ways until you get it:

G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.0233333
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.0222222
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.0211111

With decide which to lock first based on address:

G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.0211111
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.0222222
G4:~/Documents/Development/JunkMac hinnant$ ./helloworld
0.0233333

<shrug>  I agree with you that performance is a potential problem with 
the try-lock technique, at least in a heavily contested context.  But 
I'm having trouble measuring a difference in testing.  And in practice 
I had imagined that pairs of locks would not be so heavily contested as 
in the test I've shown.  If they were, the associated data should be 
grouped into a single lock (for performance reasons).

Ordering based on mutex is also a good solution for a single lock_both, 
but somewhat problematic when you start combining lock_both's for 3 or 
more mutexes.  It isn't an insurmountable problem, but I'm currently 
having trouble working up the motivation to solve it.  However perhaps 
there's other tests I should run to get properly motivated.

-Howard