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

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • Stories about devastating cyberattacks are plaguing the news. Why? The DNS protocol is easy to exploit. See your network the way hackers do—as an easy target. Learn how you can effectively secure your DNS infrastructure today.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds