title: Why is the C++ thread/future overhead so big
body: <p>I have a worker routine (code below), which is running slower when I run it in a separate thread. As far as I can tell, the worker code and data is completely independent of other threads. All the worker does is to append nodes to a tree. The goal is having multiple workers growing trees in parallel.</p>
  
  <p><strong>Can someone help me understand why there is (significant) overhead when running the worker in a separate thread?</strong></p>
  
  <p><strong>Edit</strong>:
  Initially I was testing WorkerFuture twice, I corrected that and I now get the same (better) performance in the no thread and defer async cases, and considerable overhead when an extra thread is involved.</p>
  
  <p>The command to compile (linux): g++ -std=c++11 main.cpp -o main -O3 -pthread</p>
  
  <p>Here is the output (time in milliseconds):</p>
  
  <pre><code>Thread     : 4000001 size in 1861 ms
  Async      : 4000001 size in 1836 ms
  Defer async: 4000001 size in 1423 ms
  No thread  : 4000001 size in 1455 ms
  </code></pre>
  
  <p>Code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;random&gt;
  #include &lt;chrono&gt;
  #include &lt;thread&gt;
  #include &lt;future&gt;
  
  struct Data
  {
      int data;
  };
  
  struct Tree
  {
      Data data;
      long long total;
      std::vector&lt;Tree *&gt; children;
  
      long long Size()
      {
          long long size = 1;
          for (auto c : children)
              size += c-&gt;Size();
          return size;
      }
  
      ~Tree()
      {
          for (auto c : children)
              delete c;
      }
  };
  
  int
  GetRandom(long long size)
  {
      static long long counter = 0;
      return counter++ % size;
  }
  
  void
  Worker_(Tree *root)
  {
      std::vector&lt;Tree *&gt; nodes = {root};
      Tree *it = root;
      while (!it-&gt;children.empty())
      {
          it = it-&gt;children[GetRandom(it-&gt;children.size())];
          nodes.push_back(it);
      }
      for (int i = 0; i &lt; 100; ++i)
          nodes.back()-&gt;children.push_back(new Tree{{10}, 1, {}});
      for (auto t : nodes)
          ++t-&gt;total;
  }
  
  long long
  Worker(long long iterations)
  {
      Tree root = {};
      for (long long i = 0; i &lt; iterations; ++i)
          Worker_(&amp;root);
      return root.Size();
  }
  
  void ThreadFn(long long iterations, long long &amp;result)
  {
      result = Worker(iterations);
  }
  
  long long
  WorkerThread(long long iterations)
  {
      long long result = 0;
      std::thread t(ThreadFn, iterations, std::ref(result));
      t.join();
      return result;
  }
  
  long long
  WorkerFuture(long long iterations)
  {
      std::future&lt;long long&gt; f = std::async(std::launch::async, [iterations] {
          return Worker(iterations);
      });
  
      return f.get();
  }
  
  long long
  WorkerFutureSameThread(long long iterations)
  {
      std::future&lt;long long&gt; f = std::async(std::launch::deferred, [iterations] {
          return Worker(iterations);
      });
  
      return f.get();
  }
  
  int main()
  {
      long long iterations = 40000;
  
      auto t1 = std::chrono::high_resolution_clock::now();
      auto total = WorkerThread(iterations);
      auto t2 = std::chrono::high_resolution_clock::now();
      std::cout &lt;&lt; "Thread     : " &lt;&lt; total &lt;&lt; " size in " &lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(t2 - t1).count() &lt;&lt; " ms\n";
  
      t1 = std::chrono::high_resolution_clock::now();
      total = WorkerFuture(iterations);
      t2 = std::chrono::high_resolution_clock::now();
      std::cout &lt;&lt; "Async      : " &lt;&lt; total &lt;&lt; " size in " &lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(t2 - t1).count() &lt;&lt; " ms\n";
  
      t1 = std::chrono::high_resolution_clock::now();
      total = WorkerFutureSameThread(iterations);
      t2 = std::chrono::high_resolution_clock::now();
      std::cout &lt;&lt; "Defer async: " &lt;&lt; total &lt;&lt; " size in " &lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(t2 - t1).count() &lt;&lt; " ms\n";
  
      t1 = std::chrono::high_resolution_clock::now();
      total = Worker(iterations);
      t2 = std::chrono::high_resolution_clock::now();
      std::cout &lt;&lt; "No thread  : " &lt;&lt; total &lt;&lt; " size in " &lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(t2 - t1).count() &lt;&lt; " ms\n";
  }
  </code></pre>