Performance of hash table, why is C++ the slowest?

Ran a simple performance test on hash, it appears C++ version is the slower than both the perl version and the golang version.

• perl version took about 200 millisecond,
• C++ version took 280 millisecond.
• golang version took 56 millisecond.

On my PC with Core(TM) i7-2670QM CPU @ 2.20GHz, Ubuntu 14.04.3LTS,

Any ideas?

perl version

use Time::HiRes qw( usleep ualarm gettimeofday tv_interval nanosleep
                      clock_gettime clock_getres clock_nanosleep clock
                      stat );
sub getTS {
	my ($seconds, $microseconds) = gettimeofday;
	return $seconds + (0.0+ $microseconds)/1000000.0;
}
my %mymap;
$mymap{"U.S."} = "Washington";
$mymap{"U.K."} = "London";
$mymap{"France"} = "Paris";
$mymap{"Russia"} = "Moscow";
$mymap{"China"} = "Beijing";
$mymap{"Germany"} = "Berlin";
$mymap{"Japan"} = "Tokyo";
$mymap{"China"} = "Beijing";
$mymap{"Italy"} = "Rome";
$mymap{"Spain"} = "Madrad";
$x = "";
$start = getTS();
for ($i=0; $i<1000000; $i++) {
	$x = $mymap{"China"};
}
printf "took %f sec\n", getTS() - $start;

C++ version

#include <iostream>
#include <string>
#include <unordered_map>
#include <sys/time.h>

double getTS() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec/1000000.0;
}
using namespace std;
int main () {
  std::unordered_map<std::string,std::string> mymap;

  // populating container:
	mymap["U.S."] = "Washington";
	mymap["U.K."] = "London";
	mymap["France"] = "Paris";
	mymap["Russia"] = "Moscow";
	mymap["China"] = "Beijing";
	mymap["Germany"] = "Berlin";
	mymap["Japan"] = "Tokyo";
	mymap["China"] = "Beijing";
	mymap["Italy"] = "Rome";
	mymap["Spain"] = "Madrad";	

  double start = getTS();
  string x;
  for (int i=0; i<1000000; i++) {
	  mymap["China"];
  }
  printf("took %f sec\n", getTS() - start);
  return 0;
}

Golang version

package main

import "fmt"
import "time"

func main() {
	var x string
	mymap := make(map[string]string)
	mymap["U.S."] = "Washington";
	mymap["U.K."] = "London";
	mymap["France"] = "Paris";
	mymap["Russia"] = "Moscow";
	mymap["China"] = "Beijing";
	mymap["Germany"] = "Berlin";
	mymap["Japan"] = "Tokyo";
	mymap["China"] = "Beijing";
	mymap["Italy"] = "Rome";
	mymap["Spain"] = "Madrad";
	t0 := time.Now()
	sum := 1
	for sum < 1000000 {
		x = mymap["China"]
		sum += 1
	}
	t1 := time.Now()
    fmt.Printf("The call took %v to run.\n", t1.Sub(t0))
	fmt.Println(x)
}

Update 1

To improve C++ version, changed x = mymap["China"]; to mymap["China"];, but there is very little difference in performance.

Update 2

I got the original result when compiling without any optimization: g++ -std=c++11 unorderedMap.cc. With "-O2" optimization, it cost only about half the time (150ms)

Update 3

To remove the possible char* to string constructor call, I created a string constant. The time comes down to about 220ms (no optimization in compiling). Thanks to the suggestion from @neil-kirk, with optimization, (-O2 flag), the time is about 80ms.

  double start = getTS();
  string x = "China";
  for (int i=0; i<1000000; i++) {
      mymap[x];
  }

Update 4

Thanks to @steffen-ullrich who pointed out there is a syntax error for perl version. I Changed it. The performance number is about 150ms.

Update 5

It appears the number of executed instructions matters. Using command valgrind --tool=cachegrind <cmd>

For Go version

$ valgrind --tool=cachegrind  ./te1
==2103== Cachegrind, a cache and branch-prediction profiler
==2103== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al.
==2103== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2103== Command: ./te1
==2103== 
--2103-- warning: L3 cache found, using its data for the LL simulation.
The call took 1.647099s to run.
Beijing
==2103== 
==2103== I   refs:      255,763,381
==2103== I1  misses:          3,709
==2103== LLi misses:          2,743
==2103== I1  miss rate:        0.00%
==2103== LLi miss rate:        0.00%
==2103== 
==2103== D   refs:      109,437,132  (77,838,331 rd   + 31,598,801 wr)
==2103== D1  misses:        352,474  (   254,714 rd   +     97,760 wr)
==2103== LLd misses:        149,260  (    96,250 rd   +     53,010 wr)
==2103== D1  miss rate:         0.3% (       0.3%     +        0.3%  )
==2103== LLd miss rate:         0.1% (       0.1%     +        0.1%  )
==2103== 
==2103== LL refs:           356,183  (   258,423 rd   +     97,760 wr)
==2103== LL misses:         152,003  (    98,993 rd   +     53,010 wr)
==2103== LL miss rate:          0.0% (       0.0%     +        0.1%  )

For C++ optimized version (no optimization flag)

$ valgrind --tool=cachegrind ./a.out
==2180== Cachegrind, a cache and branch-prediction profiler
==2180== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al.
==2180== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2180== Command: ./a.out
==2180== 
--2180-- warning: L3 cache found, using its data for the LL simulation.
took 64.657681 sec
==2180== 
==2180== I   refs:      5,281,474,482
==2180== I1  misses:            1,710
==2180== LLi misses:            1,651
==2180== I1  miss rate:          0.00%
==2180== LLi miss rate:          0.00%
==2180== 
==2180== D   refs:      3,170,495,683  (1,840,363,429 rd   + 1,330,132,254 wr)
==2180== D1  misses:           12,055  (       10,374 rd   +         1,681 wr)
==2180== LLd misses:            7,383  (        6,132 rd   +         1,251 wr)
==2180== D1  miss rate:           0.0% (          0.0%     +           0.0%  )
==2180== LLd miss rate:           0.0% (          0.0%     +           0.0%  )
==2180== 
==2180== LL refs:              13,765  (       12,084 rd   +         1,681 wr)
==2180== LL misses:             9,034  (        7,783 rd   +         1,251 wr)
==2180== LL miss rate:            0.0% (          0.0%     +           0.0%  )

For C++ optimized version

$ valgrind --tool=cachegrind ./a.out
==2157== Cachegrind, a cache and branch-prediction profiler
==2157== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al.
==2157== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2157== Command: ./a.out
==2157== 
--2157-- warning: L3 cache found, using its data for the LL simulation.
took 9.419447 sec
==2157== 
==2157== I   refs:      1,451,459,660
==2157== I1  misses:            1,599
==2157== LLi misses:            1,549
==2157== I1  miss rate:          0.00%
==2157== LLi miss rate:          0.00%
==2157== 
==2157== D   refs:        430,486,197  (340,358,108 rd   + 90,128,089 wr)
==2157== D1  misses:           12,008  (     10,337 rd   +      1,671 wr)
==2157== LLd misses:            7,372  (      6,120 rd   +      1,252 wr)
==2157== D1  miss rate:           0.0% (        0.0%     +        0.0%  )
==2157== LLd miss rate:           0.0% (        0.0%     +        0.0%  )
==2157== 
==2157== LL refs:              13,607  (     11,936 rd   +      1,671 wr)
==2157== LL misses:             8,921  (      7,669 rd   +      1,252 wr)
==2157== LL miss rate:            0.0% (        0.0%     +        0.0%  )

From your Perl code (before your attempts to fix it):

> @mymap = ();
> $mymap["U.S."] = "Washington";
> $mymap["U.K."] = "London";

This is not a map but an array. The syntax for hash maps is:

  %mymap;
  $mymap{"U.S."} = ....

Thus what you effectively do is to create an array and not a hash map and access the element 0 all the time.
Please, use use strict; and use warnings; all the time with Perl and even a simple syntax check with warnings would have shown you the problem:

perl -cw x.pl
Argument "U.S." isn't numeric in array element at x.pl line 9.
Argument "U.K." isn't numeric in array element at x.pl line 10.

Apart from that the main part of the benchmark effectively does nothing useful (assign a variable and never use it) and some compilers can detect it and simply optimize it away.

If you would check the code generated by your Perl program you would see:

$ perl -MO=Deparse x.pl
@mymap = ();
$mymap[0] = 'Washington';
$mymap[0] = 'London';
...
for ($i = 0; $i < 1000000; ++$i) {
    $x = $mymap[0];
}

That is it detects the problem at compile time and replaces it with an access to array index 0.

Thus whenever do benchmarks you need to:

• Check that your program actually does what it is supposed to.
• Check that the compiler does not optimize things away and does not execute stuff at compile time where other languages will do it at run time. Any kind of statements with no or predictable results are prone to such optimization.
• Verify that you actually measure what you intend to measure and not something else. Even small changes to the program can affect the run time because there is a memory allocation needed were not was before etc and these changes might not be related to what you intend to measure. In your benchmark you measure the access to the same hash element again and again without any access to other elements in between. This is an activity which can play very nice with processor caches but probably does not reflect real world use.

And, using a simple timer is not a realistic benchmark. There are other processes on the system, there is the scheduler, there is cache trashing... and with today's CPU it highly depends on the load on the system because maybe the CPU will run one benchmark in a lower power mode than the other benchmarks, i.e. with a different CPU clock. For example multiple runs of the same "benchmark" vary in the measured time between 100ms and 150ms on my system.

Benchmarks are lies and micro benchmarks like yours doubly so.

I've modified your example a little bit to get some details about the structure of the hash table:

#include <iostream>
#include <string>
#include <unordered_map>
#include <sys/time.h>
#include <chrono>
using namespace std;
int main()
{
std::unordered_map<std::string, std::string> mymap;
// populating container:
mymap["U.S."] = "Washington";
mymap["U.K."] = "London";
mymap["France"] = "Paris";
mymap["Russia"] = "Moscow";
mymap["China"] = "Beijing";
mymap["Germany"] = "Berlin";
mymap["Japan"] = "Tokyo";
mymap["China"] = "Beijing";
mymap["Italy"] = "Rome";
mymap["Spain"] = "Madrad";
std::hash<std::string> h;
for ( auto const& i : mymap )
{
printf( "hash(%s) = %ud\n", i.first.c_str(), h( i.first ) );
}
for ( int i = 0; i != mymap.bucket_count(); ++i )
{
auto const bucketsize = mymap.bucket_size( i );
if ( 0 != bucketsize )
{
printf( "size of bucket %d = %d\n", i, bucketsize );
}
}
auto const start = std::chrono::steady_clock::now();
string const x = "China";
std::string res;
for ( int i = 0; i < 1000000; i++ )
{
mymap.find( x );
}
auto const elapsed = std::chrono::steady_clock::now() - start;
printf( "%s\n", res );
printf( "took %d ms\n",
std::chrono::duration_cast<std::chrono::milliseconds>( elapsed ).count() );
return 0;
}

Running this on my system, I get a runtime of ~68ms with the following output:

hash(Japan) = 3611029618d
hash(Spain) = 749986602d
hash(China) = 3154384700d
hash(U.S.) = 2546447179d
hash(Italy) = 2246786301d
hash(Germany) = 2319993784d
hash(U.K.) = 2699630607d
hash(France) = 3266727934d
hash(Russia) = 3992029278d
size of bucket 0 = 0
size of bucket 1 = 0
size of bucket 2 = 1
size of bucket 3 = 1
size of bucket 4 = 1
size of bucket 5 = 0
size of bucket 6 = 1
size of bucket 7 = 0
size of bucket 8 = 0
size of bucket 9 = 2
size of bucket 10 = 3

It turns out that the hash table is not well optimized and contains some collisions. Further printing the elements in the bucket shows that Spain and China are in bucket 9. The bucket is probably a linked list with nodes distributed in memory, explaining the performance drop.

If you choose another hash table size such that there are no collisions, you can get a speedup. I tested it with adding mymap.rehash(1001) and got I speedup of 20-30% to something between 44-52ms.

Now, another point would be computation of the hash values for "China". The function is executed in each iteration. We can make this go away when we switch to constant plain C strings:

#include <iostream>
#include <string>
#include <unordered_map>
#include <sys/time.h>
#include <chrono>
static auto constexpr us = "U.S.";
static auto constexpr uk = "U.K.";
static auto constexpr fr = "France";
static auto constexpr ru = "Russia";
static auto constexpr cn = "China";
static auto constexpr ge = "Germany";
static auto constexpr jp = "Japan";
static auto constexpr it = "Italy";
static auto constexpr sp = "Spain";
using namespace std;
int main()
{
std::unordered_map<const char*, std::string> mymap;
// populating container:
mymap[us] = "Washington";
mymap[uk] = "London";
mymap[fr] = "Paris";
mymap[ru] = "Moscow";
mymap[cn] = "Beijing";
mymap[ge] = "Berlin";
mymap[jp] = "Tokyo";
mymap[it] = "Rome";
mymap[sp] = "Madrad";
string const x = "China";
char const* res = nullptr;
auto const start = std::chrono::steady_clock::now();
for ( int i = 0; i < 1000000; i++ )
{
res = mymap[cn].c_str();
}
auto const elapsed = std::chrono::steady_clock::now() - start;
printf( "%s\n", res );
printf( "took %d ms\n",
std::chrono::duration_cast<std::chrono::milliseconds>( elapsed ).count() );
return 0;
}

On my machine, this reduces the runtime by 50% to ~20ms. The difference is that instead of computing the hash value from the string contents, it now just transforms the address into a hash value which is much faster because it just returns the address value as a size_t. We also do not need to rehash because there are no collisions for the bucket with cn.

This just shows that for this particular use case Go hash map implementation is optimized very well.

mymap["China"] calls mapaccess1_faststr that is specifically optimized for string keys. Particularly for small one-bucket maps the hash code is not even calculated for short (less than 32 bytes) strings.

This is a guess:

unordered_map<string, string>::operator[] requires a string argument. You are providing a char*. Without optimisations on, the C++ version is likely calling the std::string(char*) constructor a million times in order to turn "China" into a std::string. Go's language spec likely makes "string literals" of the same type as string, so no constructors need to be called.

With optimisations on, the string constructor will get hoisted out of the loop and you won't see the same problem. Or quite possibly no code will be generated except the two system calls to get the time and the system call to print the difference, because ultimately it all has no effect.

To confirm that, you'd have to actually look at what assembly is being generated. That'll be a compiler option. See this question for the flags required for GCC.