title: Why will for-loop with multithreading not have as great performance as with single-thread?
body: <p>I believed it was better to process simple and heavy works (ex. matrix-calculation) with multi-threading than with single-thread, so I tested the following code : </p>
  
  <pre><code>int main()
  {
      constexpr int N = 100000;
  
      std::random_device rd;
      std::mt19937 mt(rd());
      std::uniform_real_distribution&lt;double&gt; ini(0.0, 10.0);
  
      // single-thread
      {
          std::vector&lt;int&gt; vec(N);
          for(int i = 0; i &lt; N; ++i)
          {
              vec[i] = ini(mt);
          }
  
          auto start = std::chrono::system_clock::now();
  
          for(int i = 0; i &lt; N; ++i)
          {
              vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
          }
  
          auto end = std::chrono::system_clock::now();
          auto dur = std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end - start).count();
          std::cout &lt;&lt; "single : " &lt;&lt; dur &lt;&lt; " ms."&lt;&lt; std::endl;
      }
  
      // multi-threading (Th is the number of threads)
      for(int Th : {1, 2, 4, 8, 16})
      {
          std::vector&lt;int&gt; vec(N);
          for(int i = 0; i &lt; N; ++i)
          {
              vec[i] = ini(mt);
          }
  
          auto start = std::chrono::system_clock::now();
  
          std::vector&lt;std::future&lt;void&gt;&gt; fut(Th);
          for(int t = 0; t &lt; Th; ++t)
          {
              fut[t] = std::async(std::launch::async, [t, &amp;vec, &amp;N, &amp;Th]{
                  for(int i = t*N / Th; i &lt; (t + 1)*N / Th; ++i)
                  {
                      vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
                  }
              });
          }
          for(int t = 0; t &lt; Th; ++t)
          {
              fut[t].get();
          }
  
          auto end = std::chrono::system_clock::now();
          auto dur = std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end - start).count();
          std::cout &lt;&lt; "Th = " &lt;&lt; Th &lt;&lt; " : " &lt;&lt; dur &lt;&lt; " ms." &lt;&lt; std::endl;
      }
  
      return 0;
  }
  </code></pre>
  
  <p>The execution environment :</p>
  
  <pre><code>OS : Windows 10 64-bit
  Build-system : Visual Studio Community 2015
  CPU : Core i5 4210U
  </code></pre>
  
  <p>When building this program in the <strong>Debug</strong> mode, the result was as I expected :</p>
  
  <pre><code>single : 146 ms.
  Th = 1 : 140 ms.
  Th = 2 : 71 ms.
  Th = 4 : 64 ms.
  Th = 8 : 61 ms.
  Th = 16 : 68 ms.
  </code></pre>
  
  <p>This says that the code not using std::async justly has same performance as one using one-thread and when using 4 or 8 threads I can get great performance.</p>
  
  <p>However, when in the <strong>Release</strong> mode, I got a different result (N : 100000 -> 100000000) :</p>
  
  <pre><code>single : 54 ms.
  Th = 1 : 443 ms.
  Th = 2 : 285 ms.
  Th = 4 : 205 ms.
  Th = 8 : 206 ms.
  Th = 16 : 221 ms.
  </code></pre>
  
  <p>I'm wondering this result. Just for the latter half codes, multi-threading just has better performance than single. But the fastest one is the first half codes, which do not use std::async. I know the fact that optimization and overhead around multithreading has much effect on the performance. However,</p>
  
  <ul>
  <li>The process is just calculation of the vector, so what can be optimized not in the multi-thread codes but in the single-thread codes?</li>
  <li>This program contains nothing about mutex or atomic etc, and data conflict might not occur. I think overheads around multithreading would be relatively small.</li>
  <li>CPU utilization in the codes not using std::async is smaller than in the multi-threading codes. Is it efficient to use the large part of CPU?</li>
  </ul>
  
  <hr>
  
  <p><strong><em>Update</em></strong> : I tried to research about vectorization. I enabled <code>/Qvec-report:1</code> options and got the fact:</p>
  
  <pre><code>//vectorized (when N is large)
  for(int i = 0; i &lt; N; ++i)
  {
      vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
  }
  
  //not vectorized
  auto lambda = [&amp;vec, &amp;N]{
      for(int i = 0; i &lt; N; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  };
  lambda();
  
  //not vectorized
  std::vector&lt;std::future&lt;void&gt;&gt; fut(Th);
  for(int t = 0; t &lt; Th; ++t)
  {
      fut[t] = std::async(std::launch::async, [t, &amp;vec, &amp;N, Th]{
          for(int i = t*N / Th; i &lt; (t + 1)*N / Th; ++i)
          {
              vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
          }
      });
  }
  </code></pre>
  
  <p>and run time :</p>
  
  <pre><code>single (with vectorization) : 47 ms.
  single (without vectorization)  : 70 ms.
  </code></pre>
  
  <p>It was sure that for-loop was not vectorized in multi-threaded version. However, the version needs much time also due to any other reasons.</p>
  
  <hr>
  
  <p><strong><em>Update 2</em></strong> : I rewrote for-loop in the lambda (Type A to Type B) :</p>
  
  <pre><code>//Type A (the previous one)
  fut[t] = std::async(std::launch::async, [t, &amp;vec, &amp;N, Th]{
      for(int i = t*N / Th; i &lt; (t + 1)*N / Th; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  });
  
  //Type B (the new one)
  fut[t] = std::async(std::launch::async, [t, &amp;vec, &amp;N, Th]{
      int nb = t * N / Th;
      int ne = (t + 1) * N / Th;
      for(int i = nb; i &lt; ne; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  });
  </code></pre>
  
  <p>Type B worked well. The result :</p>
  
  <pre><code>single (vectorized) : 44 ms.
  single (invectorized) : 77 ms.
  --
  Th = 1 (Type A) : 435 ms.
  Th = 2 (Type A) : 278 ms.
  Th = 4 (Type A) : 219 ms.
  Th = 8 (Type A) : 212 ms.
  --
  Th = 1 (Type B) : 112 ms.
  Th = 2 (Type B) : 74 ms.
  Th = 4 (Type B) : 60 ms.
  Th = 8 (Type B) : 61 ms.
  </code></pre>
  
  <p>The result of Type B is understandable (multi-threaded codes would run faster than single-threaded invectorized codes, and not as fast as vectorized codes). On the other hand, Type A seems to be equivalent to Type B (just using temporary variables) but these show the different performance. The two-types can be considered to generete different assembly codes.</p>
  
  <hr>
  
  <p><strong><em>Update 3</em></strong> : I might find a factor which slowed down the multi-threaded for-loop. It is division in the condition of <code>for</code>. This is single-threaded test : </p>
  
  <pre><code>//ver 1 (ordinary)
  fut[t] = std::async(std::launch::async, [&amp;vec, &amp;N]{
      for(int i = 0; i &lt; N; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  });
  
  //ver 2 (introducing a futile variable Q)
  int Q = 1;
  fut[t] = std::async(std::launch::async, [&amp;vec, &amp;N, Q]{
      for(int i = 0; i &lt; N / Q; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  });
  
  //ver 3 (using a temporary variable)
  int Q = 1;
  fut[t] = std::async(std::launch::async, [&amp;vec, &amp;N, Q]{
      int end = N / Q;
      for(int i = 0; i &lt; end; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  });
  
  //ver 4 (using a raw value)
  fut[t] = std::async(std::launch::async, [&amp;vec]{
      for(int i = 0; i &lt; 100000000; ++i)
      {
          vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
      }
  });
  </code></pre>
  
  <p>And running time :</p>
  
  <pre><code>ver 1 : 132 ms.
  ver 2 : 391 ms.
  ver 3 : 47 ms.
  ver 4 : 43 ms.
  </code></pre>
  
  <p><em>ver 3 &amp; 4</em> were well optimazed, and <em>ver 1</em> was not as much because I think the compiler could not catch N as invariable although N was <code>constexpr</code>. I think <em>ver 2</em> was very slow because of the same reason. The compiler didn't understand that N and Q wouldn't vary. So the condition <code>i &lt; N / Q</code> would need heavy assembly codes, which slowed down the for-loop.</p>