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.
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.
std::map versus std::unordered_map
For my simple performance comparison, I put a lot of arbitrary values into a std::map and std::unorderd_map and measured and compared their performance. Precisely this is done in my program.
I fill in lines 19 -22 a std::map (line 20) and a std::unordered_map (line 21) with mapSize key/values pairs. mapSize is ten million. Then I create a std::vector with one million arbitrary elements between 0 and mapSize. The random number generator engine(seed()) (line 29) initialized by the seed creates the values. I use in line 30 the random number generator engine in combination with the random number distribution unformDist: uniformDist(engine). Of course, uniformDist guarantees the uniform distribution of the values. Ultimately, randValues 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 and the std::unordered_map.
How do they compare to each other?
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.
Microsoft Visual C++ Compiler
The performance differences are significant. The std::unordered_map 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.
Now I’m curious about the optimized versions.
To compile the program with maximum optimization, I use the cl.exe compiler, the flag Ox; in the case of the g++ compiler, the flag O3. The performance differences from the non-optimized versions are very impressive.
Microsoft Visual C++
By compiling with full optimization, the access time to the std::map becomes about two times faster, and the access time to the std::unorderd_map becomes about six times faster. Therefore, the std::unorderd_map is 11 times faster than the std::map.
The performance difference is not so dramatic in the case of the GCC compiler. Therefore, the optimized access with std::map is about 20% faster, but the access time of std::unordered_map is about six times faster.
I present them once more in a simple table to whom – like me – is lost with so many numbers.
The raw numbers
For simplicity reasons, I rounded the value to 3 decimal places. The last two columns show the maximum optimized programs with (cl.exe /Ox) on Windows and (g++ -O3) on Linux.
In the post Hash tables, 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.
Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, and Marco Parri Empoli.
Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.
|My special thanks to Embarcadero|
|My special thanks to PVS-Studio|
|My special thanks to Tipi.build|
|My special thanks to Take Up Code|
I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.
- Embedded Programmierung mit modernem C++ 12.12.2023 – 14.12.2023 (Präsenzschulung, Termingarantie)
Standard Seminars (English/German)
Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.
- C++ – The Core Language
- C++ – The Standard Library
- C++ – Compact
- C++11 and C++14
- Concurrency with Modern C++
- Design Pattern and Architectural Pattern with C++
- Embedded Programming with Modern C++
- Generic Programming (Templates) with C++
- Clean Code with Modern C++
- Phone: +49 7472 917441
- Mobil:: +49 176 5506 5086
- Mail: schulung@ModernesCpp.de
- German Seminar Page: www.ModernesCpp.de
- Mentoring Page: www.ModernesCpp.org
Modernes C++ Mentoring,