On Feb 8, 2008, at 6:19 PM, Phil Endecott wrote:
If you can share the code, I'll see how it performs on my Linux systems.
Thanks Phil! Sorry for the delay. I wanted to update my test to use the latest std::syntax and rerun them again. First, here's the code: #include <date_time> #include <mutex> #include <thread> #include <iostream> typedef std::mutex Mutex; typedef std::unique_lock<Mutex> Lock; Mutex cout_mutex; unsigned random_gen(unsigned& random_next) { random_next = random_next * 1103515245 + 12345; return (random_next >> 16) & 0x7FFF; } struct Chopstick { Chopstick() : random_next_(1) {} Mutex mut_; unsigned random_next_; }; unsigned eat(unsigned i) { while (i) --i; return i; } unsigned eater(int id, Chopstick& left, Chopstick& right) { { std::lock_guard<Mutex> _(cout_mutex); std::cout << "Thread " << id << " starting\n"; } unsigned i = 10000000; unsigned u = 0; while (--i) { Lock l(left.mut_, std::defer_lock); Lock r(right.mut_, std::defer_lock); std::lock(l, r); u += eat(random_gen(left.random_next_) + random_gen(right.random_next_)); } { std::lock_guard<Mutex> _(cout_mutex); std::cout << "Thread " << id << " ending\n"; } return u; } int main() { std::system_time t1 = std::get_system_time(); Chopstick A, B, C, D, E; std::thread T1(eater, 1, std::ref(A), std::ref(B)); std::thread T2(eater, 2, std::ref(B), std::ref(C)); std::thread T3(eater, 3, std::ref(C), std::ref(D)); std::thread T4(eater, 4, std::ref(D), std::ref(E)); std::thread T5(eater, 5, std::ref(E), std::ref(A)); T1.join(); T2.join(); T3.join(); T4.join(); T5.join(); std::system_time t2 = std::get_system_time(); std::cout << " time = " << (t2-t1).count() / 1.e9 << '\n'; } If anyone sees any glaring problems with the test, please let me know, thanks. Now for results just now run. Machine: iMac 2.16 GHz Intel Core 2 Duo, OS X 10.5.1. Lock in order: template <class L1, class L2> void lock(L1& l1, L2& l2) { if (l1.mutex() < l2.mutex()) { unique_lock<L1> u1(l1); unique_lock<L2> u2(l2); u1.release(); u2.release(); } else { unique_lock<L2> u2(l2); unique_lock<L1> u1(l1); u1.release(); u2.release(); } } $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 1 ending Thread 2 ending Thread 3 ending Thread 5 ending Thread 4 ending time = 62.0437 $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 1 ending Thread 2 ending Thread 3 ending Thread 5 ending Thread 4 ending time = 145.683 $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 1 ending Thread 2 ending Thread 3 ending Thread 5 ending Thread 4 ending time = 157.347 Interesting side note: During the first run my disk backup utility kicked in. This extra competition for resources actually made the test case run faster! Try/backoff/without yield template <class L1, class L2> void lock(L1& l1, L2& l2) { while (true) { { unique_lock<L1> u1(l1); if (l2.try_lock()) { u1.release(); break; } } // std::this_thread::yield(); { unique_lock<L2> u2(l2); if (l1.try_lock()) { u2.release(); break; } } // std::this_thread::yield(); } } $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 4 ending Thread 5 ending Thread 1 ending Thread 2 ending Thread 3 ending time = 32.3726 $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 5 ending Thread 4 ending Thread 1 ending Thread 3 ending Thread 2 ending time = 29.4687 $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 5 ending Thread 1 ending Thread 4 ending Thread 3 ending Thread 2 ending time = 56.226 I have no explanation for the longer time in the third run. Try/backoff/yield template <class L1, class L2> void lock(L1& l1, L2& l2) { while (true) { { unique_lock<L1> u1(l1); if (l2.try_lock()) { u1.release(); break; } } std::this_thread::yield(); { unique_lock<L2> u2(l2); if (l1.try_lock()) { u2.release(); break; } } std::this_thread::yield(); } } $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 4 ending Thread 5 ending Thread 1 ending Thread 3 ending Thread 2 ending time = 11.216 $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 4 ending Thread 5 ending Thread 1 ending Thread 3 ending Thread 2 ending time = 10.6229 $./a.out Thread 1 starting Thread 2 starting Thread 3 starting Thread 4 starting Thread 5 starting Thread 4 ending Thread 5 ending Thread 1 ending Thread 3 ending Thread 2 ending time = 11.3284 -Howard