{"id":5047,"date":"2016-11-25T20:31:31","date_gmt":"2016-11-25T20:31:31","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/associative-containers-a-simple-performance-comparison\/"},"modified":"2023-06-26T12:35:07","modified_gmt":"2023-06-26T12:35:07","slug":"associative-containers-a-simple-performance-comparison","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/associative-containers-a-simple-performance-comparison\/","title":{"rendered":"Associative Containers – A simple Performance Comparison"},"content":{"rendered":"

Before I take a deeper look insight the interface of the hash tables – officially called unordered associative containers – I will first compare the performance of the associative containers. The best candidates are std::unordered_map<\/span> and the ordered pendant std::map<\/span> because both are used most frequently.<\/p>\n

<\/p>\n

 <\/p>\n

Admittedly, the eight variations of associative containers are a little bit confusing. In addition, the name component unordered the new ones is not easy to read and write. The reason for the special names is easily explained. On the one hand, the unordered associative containers were too late for the C++98 standard. On the other hand, they were missed so severely that most architectures implemented them by themself. Therefore, simple names have already been used, and the C++ standardization committee has to use more elaborated names. But it is very nice that the names of the unordered associative containers follow a simple pattern. I presented the pattern in the post Hash tables<\/a>.<\/p>\n<\/p>\n

std::map versus std::unordered_map<\/h2>\n

For my simple performance comparison, I put a lot of arbitrary values into a std::map<\/span> and std::unorderd_map <\/span>and measured and compared their performance<\/span>.<\/span><\/span> Precisely this is done in my program.<\/span><\/p>\n

 <\/p>\n

<\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49<\/pre>\n<\/td>\n
\n
\/\/ associativeCompare.cpp<\/span>\r\n\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <map><\/span>\r\n#include <random><\/span>\r\n#include <unordered_map><\/span>\r\n\r\nstatic<\/span> const<\/span> long<\/span> long<\/span> mapSize= 10000000;\r\nstatic<\/span> const<\/span> long<\/span> long<\/span> accSize= 1000000;\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  std::map<int<\/span>,int<\/span>> myMap;\r\n  std::unordered_map<int<\/span>,int<\/span>> myHash;\r\n\r\n  for<\/span> ( long<\/span> long<\/span> i=0; i < mapSize; ++i ){\r\n    myMap[i]=i;\r\n    myHash[i]= i;\r\n  }\r\n\r\n  std::vector<int<\/span>> randValues;\r\n  randValues.reserve(accSize);\r\n\r\n  \/\/ random values<\/span>\r\n  std::random_device seed;\r\n  std::mt19937 engine(seed());\r\n  std::uniform_int_distribution<> uniformDist(0,mapSize);\r\n  for<\/span> ( long<\/span> long<\/span> i=0 ; i< accSize ; ++i) randValues.push_back(uniformDist(engine));\r\n\r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  for<\/span> ( long<\/span> long<\/span> i=0; i < accSize; ++i){\r\n    myMap[randValues[i]];\r\n  }\r\n  std::chrono::duration<double<\/span>> dur= std::chrono::system_clock::now() - start;\r\n  std::cout << \"time for std::map: \"<\/span> << dur.count() << \" seconds\"<\/span> << std::endl;\r\n\r\n  auto<\/span> start2 = std::chrono::system_clock::now();\r\n  for<\/span> ( long<\/span> long<\/span> i=0; i < accSize; ++i){\r\n    myHash[randValues[i]];\r\n  }\r\n  std::chrono::duration<double<\/span>> dur2= std::chrono::system_clock::now() - start2;\r\n  std::cout << \"time for std::unordered_map: \"<\/span> << dur2.count() << \" seconds\"<\/span> << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
I fill in lines 19 -22 a std::map<\/span> (line 20) and a std::unordered_map<\/span> (line 21) with mapSize<\/span> key\/values pairs. mapSize<\/span> is ten million. Then I create a std::vector<\/span> with one million arbitrary elements between 0 and mapSize<\/span>. The random number generator engine(seed())<\/span> (line 29) initialized by the seed creates the values. I use in line 30 the random number generator engine<\/span> in combination with the random number distribution <\/span>unformDist<\/span>: uniformDist(engine). <\/span>Of course, uniformDist <\/span>guarantees the uniform distribution of the values. Ultimately, randValues<\/span> has one million arbitrarily created elements between 0 and 10 million that are uniformly distributed. These one million elements are the keys for which I’m interested in the values from std::map<\/span> and the std::unordered_map<\/span>.<\/p>\n
How do they compare to each other?<\/p>\n
Without optimization<\/h3>\n
At first, I compile the program without optimization. I use the current Microsoft Visual 15 C++ compiler and GCC 4.8. Here are the numbers.<\/p>\n
Microsoft Visual C++ Compiler<\/h4>\n
\"windows\"<\/h3>\n
GCC Compiler<\/h4>\n
\"linux\"<\/h3>\n
The performance differences are significant. The  std::unordered_map<\/span> is about three times faster on Windows and about five times faster on Linux. I stop here with my reasoning because the executables run on different PC.<\/p>\n
Now I’m curious about the optimized versions.<\/p>\n
Maximum optimization<\/h3>\n
To compile the program with maximum optimization, I use the cl.exe compiler, the flag Ox<\/span><\/a>;<\/span> <\/span>in the case of the g++<\/span> compiler, the flag O3<\/a><\/span>. The performance differences from the non-optimized versions are very impressive.<\/p>\n
Microsoft Visual C++<\/h4>\n
By compiling with full optimization, the access time to the std::map<\/span> becomes about two times faster, and the access time to the std::unorderd_map<\/span> becomes about six times faster. Therefore, the std::unorderd_map<\/span> is 11 times faster than the std::map.<\/span><\/p>\n
\"windowsOptimizePNG\"<\/p>\n
GCC Compiler<\/h4>\n
The performance difference is not so dramatic in the case of the GCC compiler. Therefore, the optimized access with std::map<\/span> is about 20% faster, but the access time of std::unordered_map<\/span> is about six times faster.<\/p>\n
 <\/p>\n
\"linuxOptimzed\"<\/p>\n
I present them once more in a simple table to whom – like me – is lost with so many numbers.<\/p>\n
The raw numbers<\/h3>\n
For simplicity reasons, I rounded the value to 3 decimal places. The last two columns show the maximum optimized programs with (cl.exe \/Ox<\/span>) on Windows and (g++ -O3<\/span>) on Linux.<\/p>\n
\"comparisonTableEng\"<\/p>\n
What’s next?<\/h2>\n
In the post Hash tables<\/a>, I said quite imprecise that the unordered associative containers have a similar interface as the ordered associative containers. That is not true. The unordered associative containers have a more powerful interface than the ordered pendants. E.g., you can adjust the hash function or the distribution of the hash values to their buckets. As ever, the details will follow in the next post. <\/a><\/span><\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Before I take a deeper look insight the interface of the hash tables – officially called unordered associative containers – I will first compare the performance of the associative containers. The best candidates are std::unordered_map and the ordered pendant std::map because both are used most frequently.<\/p>\n","protected":false},"author":21,"featured_media":5042,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[364],"tags":[472],"class_list":["post-5047","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-embedded","tag-associative-containers"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5047","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5047"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5047\/revisions"}],"predecessor-version":[{"id":6922,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5047\/revisions\/6922"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5042"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5047"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5047"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5047"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}