Std :: install fast and slow, what's going on?

Question

I came across the strange behavior of std :: set.

Here is the code:

#include <cstdio> #include <windows.h> #include <stdlib.h> #include <vector> #include <set> using namespace std; int main(int argc, char *argv[]) { set<int> b[100]; for (int o=0; o<10; o++) { int tt = GetTickCount(); for (int i=0; i<5000000; i++) { b[o].insert(i); } tt = GetTickCount() - tt; b[o].clear(); printf("%d\n", tt); } return 0; } 

I am running on Windows XP.

Here's the interesting part: this first print time is about 3,500 ms, and all the rest is over 9,000 ms! Why is this happening?

Oh, and this only happens in the release version (-O2 optimization).

This does not happen on Linux (after changing the code to compile there).

One more thing: when I run it when profiling using Intel VTune, it always takes about 3000 ms, which is why it should be so.

UPDATE: Here is some new code:

 #include <cstdio> #include <windows.h> #include <stdlib.h> int main(int argc, char *argv[]) { const int count = 10000000; int **a = new int*[count]; for (int o=0; o<10; o++) { int ttt = GetTickCount(); for (int i=0; i<count; i++) { a[i] = new int; *a[i] = i; } int ttt2 = GetTickCount(); for (int i=0; i<count; i++) { int r1 = rand() * 10000 + rand(); int r2 = rand() * 10000 + rand(); r1 = r1%count; r2 = r2%count; int *e = a[r1]; a[r1] = a[r2]; a[r2] = e; } int ttt3 = GetTickCount(); for (int i=0; i<count; i++) { delete a[i]; } int ttt4 = GetTickCount(); printf("%d %d\n", ttt2-ttt, ttt4-ttt3); } return 0; } 

This is the same problem. What happens, I select a lot of small objects and then delete them randomly - so it looks like it looks in std :: set. Therefore, this is a Windows memory management issue. He can not cope with a large number of small allotments and deletions.

Answer 1

I can’t explain exactly why this is happening, but I can offer a solution. I was able to reproduce this on my PC when I run release build under the debugger (using F5 ). When I run the assembly from the command line or using Ctrl-F5 , I do not get this behavior.

This has something to do with the debug heap, which is enabled by default when launched under the debugger. Described in detail here. To prevent this from happening,

• Run from the command line or using Ctrl-F5 (Debug → Start Without Debugging).
• Go to Project -> Properties -> Debugging -> Environment and add _NO_DEBUG_HEAP=1 .

If I had to guess, I would say that this has something to do with implementing memory allocation tracking in the Windows / VS runtime. Perhaps some internal lists populate and redistribute or something else on these lines.

Answer 2

I think std::set is implemented as a binary search tree. Since you increment I by 1 each time you essentially create an adversarial (worst case) script for this type of data structure (a tree rebalance is required for almost every insertion).

In addition, it is 50 million inserts, so some time is expected, although I would not think that it will be 5 ms.

In addition, I will make your “clear” after you print your time, as I don’t see the reason why you will compare both insert and delete elements.