C++11 Hash Containers and Debug Mode
The First Results
I ran my test program in Visual C++ Release mode, using all the standard settings for a console application. For purposes of comparison, I ran the same program using g++ 4.6.1 on the same computer, booted up under Linux. For the set of 1,000,000 tokens, the results are shown below:
| Task | VC++ 10 Release | g++ 4.6.1 -O3 |
|---|---|---|
Fill unordered_map<string> | 0.41s | .11s |
Fill unordered_map<string const *> | 0.39s | 0.14s |
Destroy unordered_map<string> | 3.17s | 0.01s |
Destroy unordered_map<string const *> | 3.24s | 0.004s |
Fill map<string> | 0.83s | .53s |
Fill map<string const *> | 0.88s | 0.66s |
Destroy map<string> | .14s | 0.01s |
Destroy map<string const *> | .07s | 0.002s |
There are a few interesting points to take away from these tests:
-
Microsoft's compiler is taking an exceptionally long time to destroy hashed containers — one order of magnitude greater than it took to create it, and two orders of magnitude greater than it takes g++ to do the same task.
It doesn't look like constructing and destroying the strings is a big factor. Both compilers have roughly the same performance with both
std::string and std::string *. Microsoft's behavior is counterintuitive, as it takes longer to construct and destroy containers using the pointer.
The GNU compiler appears to be able to run through this exercise notably faster.
The time it takes to destroy the table is a concern — having a C++ program hang for over 3 seconds to destroy a modestly large data structure is a serious concern — particularly when the same task completes in a few milliseconds with g++.
The Pathological Results
These concerns are nothing compared to what I see when running in debug mode. Setting my Visual Studio project to debug mode, then running the same test, yields the results shown here:
| Task | VC++ 10 Debug |
|---|---|
Fill unordered_map<string> | 17.41s |
Fill unordered_map<string const *> | 17.08s |
Destroy unordered_map<string> | 505.36s |
Destroy unordered_map<string const *> | 505.99s |
Fill map<string> | 13.29s |
Fill map<string const *> | 13.15s |
Destroy map<string> | 0.94s |
Destroy map<string const *> | 0.18s |
Those numbers are hard to believe. Destroying a hash table takes one millisecond when using g++. In VC++ 10, it takes almost 10 minutes!
Worse, we suddenly see that hashed containers are slower than the containers built on red-black trees. Again, this just doesn't make sense.
The big problem with these numbers is that it means the debug mode of the compiler is effectively unusable for a lot of tasks. Regardless of how much testing it does, when it is this slow, it is just not useful.
A Workaround
I didn't invest the time to try debugging Microsoft's library, so I don't really know where the time is being spent. I did try a few workarounds to speed things up, and I found one technique that helps a lot. Before including any Microsoft header files, try entering this single line in your source:
#define ITERATOR_DEBUG_LEVEL 0
With this definition in place, the delete times return to ball park of the times seen when running in release mode. Of course, you give up some debugging. I believe that an explanation of what this macro does might be found here.
In the final analysis, I think Microsoft has some serious work to do here. The performance of its hashed containers, and to a lesser extent, the pre-C++11 associative containers, needs serious examination. If the library is going to run this much slower than the competition, I need a good explanation why.
Source
HashTest.cpp
