title: Very slow mutex in LLVM/OpenMP
body: <p>I wrote code to test the performance of openmp on win (Win7 x64, Corei7 3.4HGz) and on Mac (10.12.3 Core i7 2.7 HGz).</p>
  
  <ol>
  <li>In xcode I made a console application setting the compiled default. I use LLVM 3.7 and OpenMP 5 (in opm.h i searched define KMP_VERSION_MAJOR=5, define KMP_VERSION_MINOR=0 and KMP_VERSION_BUILD = 20150701, libiopm5) on macos 10.12.3 (CPU - Corei7 2700GHz)</li>
  <li>For win I use VS2010 Sp1. Additional I set c/C++ -> Optimization -> Optimization = Maximize Speed (O2), c/C++ -> Optimization ->Favor Soze Or Speed = Favor Fast code (Ot). </li>
  </ol>
  
  <p>If I run the application in a single thread, the time difference corresponds to the frequency ratio of processors (approximately). But if you run 4 threads, the difference becomes tangible: win program be faster then mac program in ~70 times.</p>
  
  <pre><code>#include &lt;cmath&gt;
  #include &lt;mutex&gt;
  #include &lt;cstdint&gt;
  #include &lt;cstdio&gt;
  #include &lt;iostream&gt;
  #include &lt;omp.h&gt;
  #include &lt;boost/chrono/chrono.hpp&gt;
  
  static double ActionWithNumber(double number)
  {
      double sum = 0.0f;
      for (std::uint32_t i = 0; i &lt; 50; i++)
      {
          double coeff = sqrt(pow(std::abs(number), 0.1));
          double res = number*(1.0-coeff)*number*(1.0-coeff) * 3.0;
          sum += sqrt(res);
      }
      return sum;
  }
  
  static double TestOpenMP(void)
  {
      const std::uint32_t len = 4000000;
      double *a;
      double *b;
      double *c;
      double sum = 0.0;
  
      std::mutex _mutex;
      a = new double[len];
      b = new double[len];
      c = new double[len];
  
      for (std::uint32_t i = 0; i &lt; len; i++)
      {
          c[i] = 0.0;
          a[i] = sin((double)i);
          b[i] = cos((double)i);
      }
      boost::chrono::time_point&lt;boost::chrono::system_clock&gt; start, end;
      start = boost::chrono::system_clock::now();
      double k = 2.0;
      omp_set_num_threads(4);
  #pragma omp parallel for 
      for (int i = 0; i &lt; len; i++)
      {
          c[i] = k*a[i] + b[i] + k;
          if (c[i] &gt; 0.0)
          {
              c[i] += ActionWithNumber(c[i]);
          }
          else
          {
              c[i] -= ActionWithNumber(c[i]);
          }
          std::lock_guard&lt;std::mutex&gt; scoped(_mutex);
          sum += c[i];
      }
      end = boost::chrono::system_clock::now();
      boost::chrono::duration&lt;double&gt; elapsed_time = end - start;
      double sum2 = 0.0;
      for (std::uint32_t i = 0; i &lt; len; i++)
      {
          sum2 += c[i];
          c[i] /= sum2;
      }
      if (std::abs(sum - sum2) &gt; 0.01) printf("Incorrect result.\n");
      delete[] a;
      delete[] b;
      delete[] c;
      return elapsed_time.count();
  }
  
  int main()
  {
  
      double sum = 0.0;
      const std::uint32_t steps = 5;
      for (std::uint32_t i = 0; i &lt; steps; i++)
      {
          sum += TestOpenMP();
      }
      sum /= (double)steps;
      std::cout &lt;&lt; "Elapsed time = " &lt;&lt;  sum;
      return 0;
  }
  </code></pre>
  
  <p>I specifically use a mutex here to compare the performance of openmp on the "mac" and "win". On the "Win" function returns the time of 0.39 seconds. On the "Mac" function returns the time of 25 seconds, i.e. 70 times slower. </p>
  
  <p>What is the cause of this difference?</p>
  
  <p>First of all, thank for edit my post (i use translater to write text). 
  In the real app, I update the values in a huge matrix (20000х20000) in random order. Each thread determines the new value and writes it in a particular cell. I create a mutex for each row, since in most cases different threads write to different rows. But apparently in cases when 2 threads write in one row and there is a long lock. At the moment I can't divide the rows in different threads, since the order of records is determined by the FEM elements. 
  So just to put a critical section in there comes out, as it will block writes to the entire matrix.</p>
  
  <p>I wrote code like in real application. </p>
  
  <pre><code>static double ActionWithNumber(double number)
  {
      const unsigned int steps = 5000;
      double sum = 0.0f;
      for (u32 i = 0; i &lt; steps; i++)
      {
          double coeff = sqrt(pow(abs(number), 0.1));
          double res = number*(1.0-coeff)*number*(1.0-coeff) * 3.0;
          sum += sqrt(res);
      }
      sum /= (double)steps;
      return sum;
  }
  
  static double RealAppTest(void)
  {
      const unsigned int elementsNum = 10000;
      double* matrix;
      unsigned int* elements;
      boost::mutex* mutexes;
  
      elements = new unsigned int[elementsNum*3];
      matrix = new double[elementsNum*elementsNum];
      mutexes = new boost::mutex[elementsNum];
      for (unsigned int i = 0; i &lt; elementsNum; i++)
          for (unsigned int j = 0; j &lt; elementsNum; j++)
              matrix[i*elementsNum + j] = (double)(rand() % 100);
      for (unsigned int i = 0; i &lt; elementsNum; i++) //build FEM element like Triangle
      {
          elements[3*i] = rand()%(elementsNum-1);
          elements[3*i+1] = rand()%(elementsNum-1);
          elements[3*i+2] = rand()%(elementsNum-1);
      }
      boost::chrono::time_point&lt;boost::chrono::system_clock&gt; start, end;
      start = boost::chrono::system_clock::now();
      omp_set_num_threads(4);
  #pragma omp parallel for
      for (int i = 0; i &lt; elementsNum; i++)
      {
          unsigned int* elems = &amp;elements[3*i];
          for (unsigned int j = 0; j &lt; 3; j++)
          {
              //in here set mutex for  row with index = elems[j];
              boost::lock_guard&lt;boost::mutex&gt; lockup(mutexes[i]);
              double res = 0.0;
              for (unsigned int k = 0; k &lt; 3; k++)
              {
                  res += ActionWithNumber(matrix[elems[j]*elementsNum + elems[k]]);
              }
              for (unsigned int k = 0; k &lt; 3; k++)
              {
                  matrix[elems[j]*elementsNum + elems[k]] = res;
              }
          }
      }
      end = boost::chrono::system_clock::now();
      boost::chrono::duration&lt;double&gt; elapsed_time = end - start;
  
      delete[] elements;
      delete[] matrix;
      delete[] mutexes;
      return elapsed_time.count();
  }
  
  int main()
  {
      double sum = 0.0;
      const u32 steps = 5;
      for (u32 i = 0; i &lt; steps; i++)
      {
          sum += RealAppTest();
      }
      sum /= (double)steps;
      std::cout&lt;&lt;"Elapsed time = " &lt;&lt;  sum;
      return 0; 
  }
  </code></pre>