title: Parallel reads from STL containers
body: <p>It is safe to read a STL container from multiple parallel threads.  However, the performance is terrible.  Why?</p>
  
  <p>I create a small object that stores some data in a multiset.  This makes the constructors fairly expensive ( about 5 usecs on my machine. )  I store hundreds of thousands of the small objects in a large multiset.  Processing these objects is an independent business, so I split the work between threads running on a multi-core machine.  Each thread reads the objects it needs from the large multiset, and processes them.</p>
  
  <p>The problem is that the reading from the big multiset does not proceed in parallel.  It looks like the reads in one thread block the reads in the other.</p>
  
  <p>The code below is the simplest I can make it and still show the problem.  First it creates a large multiset containing 100,000 small objects each containing its own empty multiset.  Then it calls the multiset copy constructor twice in series, then twice again in parallel.</p>
  
  <p>A profiling tool shows that the serial copy constructors take about 0.23 secs, whereas the parallel ones take twice as long.  Somehow the parallel copies are interfering with each other.</p>
  
  <pre><code>// a trivial class with a significant ctor and ability to populate an associative container
  class cTest
  {
      multiset&lt;int&gt; mine;
      int id;
  public:
      cTest( int i ) : id( i ) {}
      bool operator&lt;(const cTest&amp; o) const { return  id &lt; o.id;  }
  };
  // add 100,000 objects to multiset
  void Populate( multiset&lt;cTest&gt;&amp; m )
  {
      for( int k = 0; k &lt; 100000; k++ )
      {
          m.insert(cTest(k));
      }
  }
  // copy construct multiset, called from mainline
  void Copy( const multiset&lt;cTest&gt;&amp; m )
  {
      cRavenProfile profile("copy_main");
      multiset&lt;cTest&gt; copy( m );
  }
  // copy construct multiset, called from thread
  void Copy2( const multiset&lt;cTest&gt;&amp; m )
  {
      cRavenProfile profile("copy_thread");
      multiset&lt;cTest&gt; copy( m );
  }
  int _tmain(int argc, _TCHAR* argv[])
  {
      cRavenProfile profile("test");
      profile.Start();
  
      multiset&lt;cTest&gt; master;
  
      Populate( master );
  
      // two calls to copy ctor from mainline
      Copy( master );
      Copy( master );
  
      // call copy ctor in parrallel
      boost::thread* pt1 = new boost::thread( boost::bind( Copy2, master ));
      boost::thread* pt2 = new boost::thread( boost::bind( Copy2, master ));
  
      pt1-&gt;join();
      pt2-&gt;join();
  
      // display profiler results
      cRavenProfile print_profile;
  
      return 0;
  }
  </code></pre>
  
  <p>Here is the output</p>
  
  <pre><code>            Scope   Calls       Mean (secs)     Total
        copy_thread        2      0.472498        0.944997
          copy_main        2      0.233529        0.467058
  </code></pre>