Why did I do six concurrency tutorials without mentioning mutexes? I think people resort to explicit locking much too early. In this installment I compare two implementations side by side and the results might be surprising. One is moving data between threads (the new C++11 move semantics), the other is using a shared monitor. Whatever the overheads of copying or locking are, they are drowned by the work the threads are doing; and locking is much more error-prone (especially if you try to optimize it).
Follow @BartoszMilewski
(You can also follow me on Google+, if you search for Bartosz Milewski.)
October 24, 2011
C++11 Concurrency Tutorial: 7. Mutex, Lock, and Monitor
Posted by Bartosz Milewski under C++, Concurrency, Multicore, Multithreading, Parallelism, Programming, Tutorial[21] Comments
Bartosz Milewski's Programming Cafe 
October 24, 2011 at 11:24 am
[…] Why did I do six concurrency tutorials without mentioning mutexes? I think people resort to explicit locking much too early. In this installment I compare two implementations side by side and the results might be surprising. One is moving data between threads (the new C++11 move semantics), the other is using a shared monitor. Whatever […] Read the whole article […]
October 24, 2011 at 12:25 pm
Why did you not move result from listDir1(…) function? It could return std::move(result) instead of return result.
October 24, 2011 at 3:08 pm
When a function returns a result, the result will no longer be accessible by this function. That’s why the compiler automatically turns the return value into an rvalue reference and calls the move constructor, if one is provided. The move semantics seems to work almost magically. That’s why it’s so useful.
Interestingly enough, in the past, C++ compiler would often do copy elision anyway, as part of return value optimization. This optimization is now guaranteed for objects that have move semantics.
November 9, 2011 at 1:58 pm
Hi Bartosz,
regarding “The move semantics seems to work almost magically”, you might be interested in stepping through this code in debugger:
void putFile( std::string&& file )
{
…
_result.files.push_back(file);
}
I believe you might be in for a surprise 😉
Petr
November 10, 2011 at 5:32 pm
I think I changed this code at some point (look at the source code for tutorial 7) to std::move the string ‘file’ explicitly. Otherwise, as you have discovered, a copy is made during push_back. This is because ‘file’ is still potentially accessible after push_back so its disappearance would be surprising. std::string has both, move and copy constructors, so the compiler correctly picked the copy one. Fortunately there is reason behind magic 😉
February 12, 2012 at 9:25 am
I enjoy watching these videos. Thanks. One remark: it would have been worth using two std::mutex rather than one in class ResultMonitor:
* one for guarding access to _result.dirs
* one for guarding access to _result.files
So that one thread accessing _result.dirs does not block another thread accessing _result.files and vice versa.
February 12, 2012 at 4:28 pm
You are correct. I just didn’t want to complicate things for the sake of exposition.
June 30, 2012 at 8:12 pm
Hi, Bartosz!
I used Java for writing parallel program before. After watching your video tutorial, I am ready to give c++ a try. By the way, you tutorial is not just about concurrency but also the new C++11.
I wanted to write a thread safe random number generator. The following is my implementation. However, the testing shows that this implementation is problematic. I have no idea about where the problem is since I have synchronized every public method. If it does not take much of time, could you shed some light on what caused the problem please?
[edit: the code is in the next comment]
June 30, 2012 at 8:13 pm
For reasons I’m not sure about, the libraries I included did not show up in the above code.
July 1, 2012 at 12:03 pm
Ben, you have to enclose code between <pre> and </pre> tags and replace all less than signs with ampersand-lt-semicolon:
<July 1, 2012 at 12:58 pm
Hi, Bartosz!
I followed your concurrency tutorial. The mutex works well to protect shared resources, but then I came with the following problem. I tried to write a thread safe random number generator, but the testing showed that it is problematic. I synchronized every public method of the class, so I really have no idea what caused the problem. By the way, I used the g++ compiler.
/** * There is a problem with the synchronized version of Mersenne Twister engine, * but I have no idea where the problem comes from. * It seems that I have synchronized every method. **/ #include<iostream> #include<vector> #include<algorithm> #include<thread> #include<future> #include<mutex> #include<random> using namespace std; class smt{ private: mt19937_64 rng; mutex _mutex; public: uint_fast64_t min(){ lock_guard<mutex> lck(_mutex); return mt19937_64::min(); } uint_fast64_t max(){ lock_guard<mutex> lck(_mutex); return mt19937_64::max(); } void seed(uint_fast64_t value){ lock_guard<mutex> lck(_mutex); rng.seed(value); } uint_fast64_t operator()(){ lock_guard<mutex> lck(_mutex); return rng(); } }; static smt srng1; static smt srng2; static mt19937_64 rng3; static negative_binomial_distribution<int> nb(4,0.3); int rnb(){ return nb(srng1); } vector<int> par_rng(int size){ vector<std::future<int>> futures; vector<int> numbers; for(int i=0; i<size; ++i){ futures.push_back(async(std::launch::async,&rnb)); } for(auto & f:futures){ numbers.push_back(move(f.get())); } return numbers; } vector<int> ser_rng2(int size){ vector<int> numbers; for(int i=0; i<size; ++i){ //numbers.push_back(move(nb(rng))); numbers.push_back(nb(srng2)); } return numbers; } vector<int> ser_rng(int size){ vector<int> numbers; for(int i=0; i<size; ++i){ //numbers.push_back(move(nb(rng))); numbers.push_back(nb(rng3)); } return numbers; } template<typename T> void print_vector(vector<T> v){ for(auto& n:v){ cout<<n<<" "; } cout<<"\n"; } template<typename T> bool is_identical(vector<T>& v1, std::vector<T>& v2){ for(int i=v1.size()-1; i>=0; --i){ if(v1[i]!=v2[i]){ return false; } } return true; } int main(){ int size = 100; int seed; cout<<"Please type in a seed:\n"; cin>>seed; srng1.seed(seed); srng2.seed(seed); rng3.seed(seed); auto ns1 = ser_rng(size); sort(begin(ns1),end(ns1)); auto ns2 = ser_rng2(size); sort(ns2.begin(),ns2.end()); auto ns3 = par_rng(size); sort(ns3.begin(),ns3.end()); cout<<"1 vs 2: "<<is_identical(ns1,ns2)<<"\n"; cout<<"1 vs 3: "<<is_identical(ns1,ns3)<<"\n"; cout<<"2 vs 3: "<<is_identical(ns2,ns3)<<"\n"; }July 1, 2012 at 1:01 pm
It’s hard to answer your question since you didn’t specify what error you are seeing. Some random number generators use thread local storage for their state — in that case you’d have to seed it separately in each thread. Those generators are usually thread-safe by themselves.
July 1, 2012 at 1:31 pm
From what I know, the Mersenne Twister engine in the c++11 stand library is not thread safe. The error was that the “smt” class (I wrote) is not thread safe though I synchronized every public method using mutex. I sorted the output of “smt” RNG and compared it with the output of serial RNG, and they are different!
July 1, 2012 at 1:34 pm
Why don’t you write a different test. Generate just a few numbers (say, 4) using the three methods and print them out without sorting.
July 1, 2012 at 2:25 pm
The reason that I sorted the outputs is because the sequence generated by the parallel algorithm is non-deterministic. The sequences of random numbers generated might be of the same set but in different order. If the two sequences of random numbers are different sets, then surly the parallel algorithm is problematic.
July 1, 2012 at 2:29 pm
By inspection, your implementation looks thread-safe. I’m pretty sure the problem is in the engine — it’s probably using a thread-local variable to store the state. Your code looks like it’s accessing the same RNG from many threads, but in reality the data inside the RNG is duplicated in each thread. The one in the main thread is seeded by you, but the others start with a default seed.
July 1, 2012 at 2:48 pm
Bartosz,
I also implemented the thread safe random random generator in another way. The following is the code. The testing shows that it seems to work well. If thread local variables caused the problem in my last example, would it be the same here?
#include<algorithm> #include<iostream> #include<vector> #include<thread> #include<future> #include<mutex> #include<random> template<typename T> bool is_identical(std::vector<T> v1, std::vector<T> v2){ int size = v1.size(); for(int i = size - 1; i>=0; --i){ if(v1[i]!=v2[i]){ return false; } } return true; } static std::mt19937_64 rng1; static std::mt19937_64 rng2; static std::negative_binomial_distribution<int> n(4,0.3); static std::mutex mutex; int rnb(){ std::lock_guard<std::mutex> lck(mutex); return n(rng2); } std::vector<int> par_rng(int size){ std::vector<int> numbers; std::vector<std::future<int>> futures; for(int i=0; i<size; ++i){ futures.push_back(std::move( std::async(std::launch::async,&rnb))); } for(auto& f:futures){ numbers.push_back(f.get()); } return numbers; } std::vector<int> ser_rng(int size){ std::vector<int> numbers; for(int i=0; i<size; ++i){ numbers.push_back(n(rng1)); } return numbers; } template<typename T> void print_vector(std::vector<T> v){ for(auto& e:v){ std::cout<<e<<" "; } std::cout<<"\n"; } int main(){ int size = 100; int seed; std::cout<<"Please type in a seed:\n"; std::cin>>seed; rng1.seed(seed); auto ns_ser = ser_rng(size); std::sort(std::begin(ns_ser),std::end(ns_ser)); //print_vector(ns_ser); rng2.seed(seed); auto ns_par = par_rng(size); std::sort(std::begin(ns_par),std::end(ns_par)); //print_vector(ns_par); std::cout<<is_identical(ns_ser, ns_par)<<"\n"; }July 1, 2012 at 3:32 pm
Oh, I see. This just shows that negative_binomial_distribution is not thread safe. I don’t know how it’s implemented, but it could be calling the underlying engine more than once per single call.
July 1, 2012 at 5:13 pm
Bartosz,
Excellent! Your guess is right. An object of negative_binomial_distribution calls the underlying engine more than once per single call. This explains why the outputs of serial and parallel algorithm are different. However, this does not mean that the negative_binomial_distribution is not thread safe. As long as the underlying random number generator (RNG) is thread safe, different calls of an object of the negative_binomial_distribution use non-overlapping segments of a output sequence of the RNG. This can be verified by examining the distribution of the generated sequence using parallel algorithm. In this case, it is not necessary for the outputs of serial and parallel algorithms to be the same set.
Thanks a lot for your patient and warm reply! It is fun studying C++ following your tutorials!
November 12, 2014 at 9:36 am
In this video, you showed most of the source code but without the implementation of listDir2. So I finished by myself like following:
void listDir2(path && dir, MonitorResult & result) { for (directory_iterator it(dir); it != directory_iterator(); ++it) { if (it->is_directory()) result.putDir(std::move(it->path())); else result.putFile(it->path().leaf()); } }but there is a problem here of
result.putDir(std::move(it->path())); it->path()function returns aconst & path, and the parameter of putDir is rValue. I cannot change theconst &to rValue bystd::move. How can I solve this problem? And also can I find the source code of you concurrency tutorial somewhere? Thanks, your tutorial helps me a lot!November 12, 2014 at 10:21 am
If you look closely at the video, I am not moving it->path(), just passing it by value — exactly because it’s an rvalue.
This video was recorded a long time ago and I don’t have the source code any more. Sorry!