title: Is gcc std::unordered_map implementation slow? If so - why?
body: <p>We are developing a highly performance critical software in C++. There we need a concurrent hash map and implemented one. So we wrote a benchmark to figure out, how much slower our concurrent hash map is compared with <code>std::unordered_map</code>.</p>
  
  <p>But, <code>std::unordered_map</code> seems to be incredibly slow... So this is our micro-benchmark (for the concurrent map we spawned a new thread to make sure that locking does not get optimized away and note that I never inser 0 because I also benchmark with <code>google::dense_hash_map</code>, which needs a null value):</p>
  
  <pre><code>boost::random::mt19937 rng;
  boost::random::uniform_int_distribution&lt;&gt; dist(std::numeric_limits&lt;uint64_t&gt;::min(), std::numeric_limits&lt;uint64_t&gt;::max());
  std::vector&lt;uint64_t&gt; vec(SIZE);
  for (int i = 0; i &lt; SIZE; ++i) {
      uint64_t val = 0;
      while (val == 0) {
          val = dist(rng);
      }
      vec[i] = val;
  }
  std::unordered_map&lt;int, long double&gt; map;
  auto begin = std::chrono::high_resolution_clock::now();
  for (int i = 0; i &lt; SIZE; ++i) {
      map[vec[i]] = 0.0;
  }
  auto end = std::chrono::high_resolution_clock::now();
  auto elapsed = std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end - begin);
  std::cout &lt;&lt; "inserts: " &lt;&lt; elapsed.count() &lt;&lt; std::endl;
  std::random_shuffle(vec.begin(), vec.end());
  begin = std::chrono::high_resolution_clock::now();
  long double val;
  for (int i = 0; i &lt; SIZE; ++i) {
      val = map[vec[i]];
  }
  end = std::chrono::high_resolution_clock::now();
  elapsed = std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end - begin);
  std::cout &lt;&lt; "get: " &lt;&lt; elapsed.count() &lt;&lt; std::endl;
  </code></pre>
  
  <p>(EDIT: the whole source code can be found here: <a href="http://pastebin.com/vPqf7eya" rel="noreferrer">http://pastebin.com/vPqf7eya</a>)</p>
  
  <p>The result for <code>std::unordered_map</code> is:</p>
  
  <pre><code>inserts: 35126
  get    : 2959
  </code></pre>
  
  <p>For <code>google::dense_map</code>:</p>
  
  <pre><code>inserts: 3653
  get    : 816
  </code></pre>
  
  <p>For our hand backed concurrent map (which does locking, although the benchmark is single threaded - but in a separate spawn thread):</p>
  
  <pre><code>inserts: 5213
  get    : 2594
  </code></pre>
  
  <p>If I compile the benchmark program without pthread support and run everything in the main thread, I get the following results for our hand backed concurrent map:</p>
  
  <pre><code>inserts: 4441
  get    : 1180
  </code></pre>
  
  <p>I compile with the following command:</p>
  
  <pre><code>g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc
  </code></pre>
  
  <p>So especially inserts on <code>std::unordered_map</code> seem to be extremely expensive - 35 seconds vs 3-5 seconds for other maps. Also the lookup time seems to be quite high.</p>
  
  <p>My question: why is this? I read another question on stackoverflow where someone asks, why <code>std::tr1::unordered_map</code> is slower than his own implementation. There the highest rated answer states, that the <code>std::tr1::unordered_map</code> needs to implement a more complicated interface. But I can not see this argument: we use a bucket approach in our concurrent_map, <code>std::unordered_map</code> uses a bucket-approach too (<code>google::dense_hash_map</code> does not, but than <code>std::unordered_map</code> should be at least as fast than our hand backed concurrency-safe version?). Apart from that I can not see anything in the interface that force a feature which makes the hash map perform badly...</p>
  
  <p>So my question: is it true that <code>std::unordered_map</code> seems to be very slow? If no: what is wrong? If yes: what is the reason for that.</p>
  
  <p>And my main question: why is inserting a value into a <code>std::unordered_map</code> so terrible expensive (even if we reserve enough space at the beginning, it does not perform much better - so rehashing seems not to be the problem)?</p>
  
  <h1>EDIT:</h1>
  
  <p>First of all: yes the presented benchmark is not flawless - this is because we played around a lot with it and it is just a hack (for example the <code>uint64</code> distribution to generate ints would in practice not be a good idea, exclude 0 in a loop is kind of stupid etc...).</p>
  
  <p>At the moment most comments explain, that I can make the unordered_map faster by preallocating enough space for it. In our application this is just not possible: we are developing a database management system and need a hash map to store some data during a transaction (for example locking information). So this map can be everything from 1 (user just makes one insert and commits) to billions of entries (if full table scans happen). It is just impossible to preallocate enough space here (and just allocate a lot in the beginning will consume too much memory).</p>
  
  <p>Furthermore, I apologize, that I did not state my question clear enough: I am not really interested in making unordered_map fast (using googles dense hash map works fine for us), I just don't really understand where this huge performance differences come from. It can not be just preallocation (even with enough preallocated memory, the dense map is an order of magnitude faster than unordered_map, our hand backed concurrent map starts with an array of size 64 - so a smaller one than unordered_map).</p>
  
  <p>So what is the reason for this bad performance of <code>std::unordered_map</code>? Or differently asked: Could one write an implementation of the <code>std::unordered_map</code> interface which is standard conform and (nearly) as fast as googles dense hash map? Or is there something in the standard that enforces the implementer to chose an inefficient way to implement it?</p>
  
  <h1>EDIT 2:</h1>
  
  <p>By profiling I see that a lot of time is used for integer divions. <code>std::unordered_map</code> uses prime numbers for the array size, while the other implementations use powers of two. Why does <code>std::unordered_map</code> use prime-numbers? To perform better if the hash is bad? For good hashes it does imho make no difference.</p>
  
  <h1>EDIT 3:</h1>
  
  <p>These are the numbers for <code>std::map</code>:</p>
  
  <pre><code>inserts: 16462
  get    : 16978
  </code></pre>
  
  <p>Sooooooo: why are inserts into a <code>std::map</code> faster than inserts into a <code>std::unordered_map</code>... I mean WAT? <code>std::map</code> has a worse locality (tree vs array), needs to make more allocations (per insert vs per rehash + plus ~1 for each collision) and, most important: has another algorithmic complexity (O(logn) vs O(1))!</p>