C++ Programming: STL Hash Container Benchmark

Introduction

This article presents a benchmark application which pits the red-black binary tree containers(map, set, etc) against hash containers. This article is not a tutorial on the data structures. For more information on how a red-black binary tree works, you can refer to this wikipedia link. For hash containers, you can read this excellent Codeguru article by Marius Bancila.

Application Screenshot

Red-black binary tree is a very fast search tree data structure: it can find any item in 4 billion items in 32 steps or less. Its O notation is O(log n) while hash container's average case is O(1) and its worst case is O(Total number of elements). The only time the hash container's time-taken-to-search is not O(1) is due to the searched item shares the same hash with other different item(s) and the hash container has to compare them one-by-one to find a exact match. For more information on the performance comparison, look at this Boost library link.

Benchmark

For the map and multimap benchmark, the key in key-value pair is a word(string) in English dictionary while the value in key-value pair is a random number. This is okay because the value is not used in the search. For the set and multiset benchmark, the element is a word(string) in English dictionary. Set is a data structure similar to map without the value pair. The multimap and multiset, unlike map and set, allows the same key/element to be insert more than once and doesn't enforce the uniqueness. The reason I use std::wstring for the key/element because hash containers has a predefined hash function written for std::wstring. If I use my own custom data types, I may have to write my own custom hash function.

For map, multimap, set and multiset insertion, I called the insert method. For multiset and multimap insertion, I insert the same item twice. For map and set search, I called the find method. For multiset and multimap search, I used equal_range method.

For the benchmark, we will benchmark STL, legacy hash container(more on this later), Visual C++ 10 unordered containers and Boost 1.44 unordered containers. Legacy hash containers which I have just mentioned, exists in the stdext namespace since Visual Studio 2003. We will benchmark them as well to see how they fare against the C++0x unordered containers. By the way, in case you are not aware, C++0x and Boost hash containers are called unordered_xxx(eg, unordered_map). The benchmark application will populate the containers before running the benchmark if it hasn't been populated but population time is not included in the benchmark results. The reason I did not benchmark the container population is that I found the population to be quite fast.

The benchmark used a random number to index into the std::vector for an item(string) to search in the above containers. You can change the random number generation seed in the benchmark application.

Map Benchmark

The benchmark are done over 5 million searches. The lower the score, the better it is.

Map Benchmark

We can see that the hash containers performs 2 times better than STL map. The timing for the hash containers are roughly the same.

MultiMap Benchmark

The benchmark are also done over 5 million searches. The lower the score, the better it is.

MultiMap Benchmark

We can see Boost unordered multimap timing is 4 times better than STL multimap.

C++ Programming: STL Hash Container Benchmark

Set Benchmark

[SetBenchmark.png]

We can see that set benchmark results is similar to the earlier map results.

MultiSet Benchmark

[MultiSetBenchmark.png]

We can see that multiset benchmark results is similar to the earlier multimap results. As we can see the hash containers consistently outperform their red-black tree equivalents, we may be tempted to use the hash containers in our code. For most cases, the hash containers is a drop-in replacement for their red-black tree equivalent but some methods may be missing and some method behaviour may change; For example, when you get their iterators, they are not ordered(unordered) unlike the red-black tree versions. You have to investigate their difference yourself.

Building Benchmark Application

Please build the application in release mode. The debug build application runs too slowly. The readers have to download Boost 1.44 and point your Visual C++ 10 include path to Boost 1.44 if you haven't had Boost library on your development machine.

Benchmark Framework

The application is a benchmark framework; Each benchmark test suite is a self-contained win32 dll. The benchmark application will load all dlls with the certain function signatures on startup. For some reasons, you want to add your own benchmark dll(for example, you want to benchmark SGI hash container) to the application folder, the benchmark application will pick it up as well. There is virtually no limit on the number of dlls you can add. Of course, the more you add, the benchmark time gets longer, and the graph's bars gets thinner. To write your own benchmark dll, just create a new win32 dll project and copy source code from any of the existing dll, you could just change the included headers to the new container headers which you want to benchmark and you may have to change the container class names as well. There you go, you have a new benchmark dll. The sequence in which the dlls are benchmarked is according to GetIndex().

  • STL dll GetIndex() returns 5.
  • Legacy Hash dll GetIndex() returns 10.
  • VC10 unordered dll GetIndex() returns 15.
  • Boost unordered dll GetIndex() returns 20.

So to insert your own dll in front of other dlls, your GetIndex() should return between 1 to 4.

Conclusion

I welcome any feedback(good or bad) as to how I am doing this benchmark correct or wrong and how I could improve it. If my benchmark is not a good representation of how the data search is used in the real-world scenario, please let me know as well. I wrote this article, not to teach but to learn from my readers who are far better programmers than me. Thank you for reading!



About the Author

Wong Shao Voon

I guess I'll write here what I does in my free time, than to write an accolade of skills which I currently possess. I believe the things I does in my free time, say more about me.

When I am not working, I like to watch Japanese anime. I am also writing some movie script, hoping to see my own movie on the big screen one day.

I like to jog because it makes me feel good, having done something meaningful in the morning before the day starts.

I also writes articles for CodeGuru; I have a few ideas to write about but never get around writing because of hectic schedule.

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • With JRebel, developers get to see their code changes immediately, fine-tune their code with incremental changes, debug, explore and deploy their code with ease (both locally and remotely), and ultimately spend more time coding instead of waiting for the dreaded application redeploy to finish. Every time a developer tests a code change it takes minutes to build and deploy the application. JRebel keeps the app server running at all times, so testing is instantaneous and interactive.

  • Ever-increasing workloads and the challenge of containing costs leave companies conflicted by the need for increased processing capacity while limiting physical expansion. Migration to HP's new generation of increased-density rack-and-blade servers can address growing demands for compute capacity while reducing costly sprawl. Sponsored by: HP and Intel® Xeon® processors Intel, the Intel logo, and Xeon Inside are trademarks of Intel Corporation in the U.S. and/or other countries. HP is the sponsor …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds