title: How to improve std::set_intersection performance in C++?
body: <p>During experimenting with std::set in C++ and set() in Python I faced performance issue that I can't explain. Set intersection in C++ at least 3 times slower than in Python.</p>
  
  <p>So could anybody point me at optimization that could be done to C++ code and/or explain how Python do this so much faster?</p>
  
  <p>I expect that both of them use similar algorithm with O(n) complexity while set is ordered. But probably Python do some optimizations so it reach smaller coefficient.</p>
  
  <p>set_bench.cc</p>
  
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt;
  #include &lt;set&gt;
  #include &lt;algorithm&gt;
  #include &lt;iterator&gt;
  #include &lt;chrono&gt;
  #include &lt;functional&gt;
  #include &lt;thread&gt;
  
  void elapsed(std::function&lt;void()&gt; f, const std::string&amp; s)
  {
      auto start = std::chrono::steady_clock::now();
      f();
      std::chrono::duration&lt;double&gt; elapsed = std::chrono::steady_clock::now() - start;
      std::cout &lt;&lt; s &lt;&lt; " " &lt;&lt; elapsed.count() &lt;&lt; " seconds" &lt;&lt; std::endl;
  }
  
  template &lt;typename T&gt;
  void fill_set(std::set&lt;T&gt;&amp; s, T start, T end, T step)
  {
      for (T i = start; i &lt; end; i += step) {
          s.emplace(i);
      }
  }
  
  template &lt;typename T&gt;
  void intersect(const std::set&lt;T&gt;&amp; s1, const std::set&lt;T&gt;&amp; s2, std::set&lt;T&gt;&amp; result)
  {
      std::set_intersection(s1.begin(), s1.end(),
                              s2.begin(), s2.end(),
                              std::inserter(result, result.begin()));
  }
  
  int main()
  {
      std::set&lt;int64_t&gt; s1;
      std::set&lt;int64_t&gt; s2;
      std::set&lt;int64_t&gt; s3;
  
      elapsed(std::bind(fill_set&lt;int64_t&gt;, std::ref(s1), 8, 1000*1000*100, 13), "fill s1 took");
      elapsed(std::bind(fill_set&lt;int64_t&gt;, std::ref(s2), 0, 1000*1000*100, 7), "fill s2 took");
  
      std::cout &lt;&lt; "s1 length = " &lt;&lt; s1.size() &lt;&lt; ", s2 length = " &lt;&lt; s2.size() &lt;&lt; std::endl;
  
      elapsed(std::bind(intersect&lt;int64_t&gt;, std::ref(s1), std::ref(s2), std::ref(s3)), "intersect s1 and s2 took");
  
      std::cout &lt;&lt; "s3 length = " &lt;&lt; s3.size() &lt;&lt; std::endl;
  
      // sleep to let check memory consumption
      // while (true) std::this_thread::sleep_for(std::chrono::milliseconds(1000));
  }
  </code></pre>
  
  <p>set_bench.py</p>
  
  <pre class="lang-py prettyprint-override"><code>#!/usr/bin/env python3
  
  import time
  
  def elapsed(f, s):
      start = time.monotonic()
      f()
      elapsed = time.monotonic() - start
      print(f'{s} {elapsed} seconds')
  
  def fill_set(s, start, end, step=1):
      for i in range(start, end, step):
          s.add(i)
  
  def intersect(s1, s2, result):
      result.update(s1 &amp; s2)
  
  s1 = set()
  s2 = set()
  
  elapsed(lambda : fill_set(s1, 8, 1000*1000*100, 13), 'fill s1 took')
  elapsed(lambda : fill_set(s2, 0, 1000*1000*100, 7), 'fill s2 took')
  
  print(f's1 length = {len(s1)}, s2 length = {len(s2)}')
  
  
  s3 = set()
  
  elapsed(lambda: intersect(s1, s2, s3), 'intersect s1 and s2 took')
  
  print(f's3 length = {len(s3)}')
  
  # sleep to let check memory consumption
  # while True: time.sleep(1)
  </code></pre>
  
  <p>Here is results of running this programs in next environment:</p>
  
  <ul>
  <li>clang version 7.0.1</li>
  <li>gcc 8.2.0</li>
  <li>Python 3.7.2</li>
  <li>i7-7700 CPU @ 3.60GHz</li>
  </ul>
  
  <pre><code>$ clang -lstdc++ -O0 set_bench.cc -o set_bench &amp;&amp; ./set_bench
  fill s1 took 5.38646 seconds
  fill s2 took 10.5762 seconds
  s1 length = 7692308, s2 length = 14285715
  intersect s1 and s2 took 1.48387 seconds
  s3 length = 1098901
  </code></pre>
  
  <pre><code>$ clang -lstdc++ -O1 set_bench.cc -o set_bench &amp;&amp; ./set_bench
  fill s1 took 3.31435 seconds
  fill s2 took 6.41415 seconds
  s1 length = 7692308, s2 length = 14285715
  intersect s1 and s2 took 1.01276 seconds
  s3 length = 1098901
  </code></pre>
  
  <pre><code>$ clang -lstdc++ -O2 set_bench.cc -o set_bench &amp;&amp; ./set_bench
  fill s1 took 1.90269 seconds
  fill s2 took 3.85651 seconds
  s1 length = 7692308, s2 length = 14285715
  intersect s1 and s2 took 0.512727 seconds
  s3 length = 1098901
  </code></pre>
  
  <pre><code>$ clang -lstdc++ -O3 set_bench.cc -o set_bench &amp;&amp; ./set_bench
  fill s1 took 1.92473 seconds
  fill s2 took 3.72621 seconds
  s1 length = 7692308, s2 length = 14285715
  intersect s1 and s2 took 0.523683 seconds
  s3 length = 1098901
  </code></pre>
  
  <pre><code>$ gcc -lstdc++ -O3 set_bench.cc -o set_bench &amp;&amp; time ./set_bench
  fill s1 took 1.72481 seconds
  fill s2 took 3.3846 seconds
  s1 length = 7692308, s2 length = 14285715
  intersect s1 and s2 took 0.516702 seconds
  s3 length = 1098901
  </code></pre>
  
  <pre><code>$ python3.7 ./set_bench.py 
  fill s1 took 0.9404696229612455 seconds
  fill s2 took 1.082577683031559 seconds
  s1 length = 7692308, s2 length = 14285715
  intersect s1 and s2 took 0.17995300807524472 seconds
  s3 length = 1098901
  </code></pre>
  
  <p>As you can see results are equal so I assume both programs do the same calculations.</p>
  
  <p>By the way - RSS for C++ program is 1084896 kB and for Python - 1590400 kB.</p>