title: Why is std::unordered_map slow, and can I use it more effectively to alleviate that?
body: <p>I’ve recently found out an odd thing. It seems that calculating Collatz sequence lengths with <a href="http://melpon.org/wandbox/permlink/xpx3rSzV6thjfz1q" rel="noreferrer">no caching at all</a> is over 2 times <em>faster</em> than <a href="http://melpon.org/wandbox/permlink/Omhqamehs2P6y7Or" rel="noreferrer">using <code>std::unordered_map</code> to cache all elements</a>.</p>
  
  <p>Note I did take hints from question <a href="https://stackoverflow.com/questions/11614106/is-gcc-stdunordered-map-implementation-slow-if-so-why">Is gcc std::unordered_map implementation slow? If so - why?</a> and I tried to used that knowledge to make <code>std::unordered_map</code> perform as well as I could (I used g++ 4.6, it did perform better than recent versions of g++, and I tried to specify a sound initial bucket count, I made it exactly equal to the maximum number of elements the map must hold).</p>
  
  <p>In comparision, <a href="http://melpon.org/wandbox/permlink/9YayIIQmPm8I1Hmm" rel="noreferrer">using <code>std::vector</code> to cache a few elements</a> was almost 17 times faster than no caching at all and almost 40 times faster than using <code>std::unordered_map</code>.</p>
  
  <p>Am I doing something wrong or is this container THAT slow and why? Can it be made performing faster? Or maybe hashmaps are inherently ineffective and should be avoided whenever possible in high-performance code?</p>
  
  <p>The problematic benchmark is:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;unordered_map&gt;
  #include &lt;cstdint&gt;
  #include &lt;ctime&gt;
  
  std::uint_fast16_t getCollatzLength(std::uint_fast64_t val) {
      static std::unordered_map &lt;std::uint_fast64_t, std::uint_fast16_t&gt; cache ({{1,1}}, 2168611);
  
      if(cache.count(val) == 0) {
          if(val%2 == 0)
              cache[val] = getCollatzLength(val/2) + 1;
          else
              cache[val] = getCollatzLength(3*val+1) + 1;
      }
  
      return cache[val];
  }
  
  int main()
  {
      std::clock_t tStart = std::clock();
  
      std::uint_fast16_t largest = 0;
      for(int i = 1; i &lt;= 999999; ++i) {
          auto cmax = getCollatzLength(i);
          if(cmax &gt; largest)
              largest = cmax;
      }
      std::cout &lt;&lt; largest &lt;&lt; '\n';
  
      std::cout &lt;&lt; "Time taken: " &lt;&lt; (double)(std::clock() - tStart)/CLOCKS_PER_SEC &lt;&lt; '\n';
  }
  </code></pre>
  
  <p>It outputs: <code>Time taken: 0.761717</code></p>
  
  <p>Whereas a benchmark with no caching at all:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;unordered_map&gt;
  #include &lt;cstdint&gt;
  #include &lt;ctime&gt;
  
  std::uint_fast16_t getCollatzLength(std::uint_fast64_t val) {
      std::uint_fast16_t length = 1;
      while(val != 1) {
          if(val%2 == 0)
              val /= 2;
          else
              val = 3*val + 1;
          ++length;
      }
      return length;
  }
  
  int main()
  {
      std::clock_t tStart = std::clock();
  
      std::uint_fast16_t largest = 0;
      for(int i = 1; i &lt;= 999999; ++i) {
          auto cmax = getCollatzLength(i);
          if(cmax &gt; largest)
              largest = cmax;
      }
      std::cout &lt;&lt; largest &lt;&lt; '\n';
  
      std::cout &lt;&lt; "Time taken: " &lt;&lt; (double)(std::clock() - tStart)/CLOCKS_PER_SEC &lt;&lt; '\n';
  }
  </code></pre>
  
  <p>Outputs <code>Time taken: 0.324586</code></p>