These programs take a long time to close after a "return"; on the main ()

Question

This is the code that I mean:

#include <iostream> #include <map> using namespace std; static unsigned long collatzLength(unsigned long n) { static std::map<unsigned long,int> collatzMap; int mapResult = collatzMap[n]; if (mapResult != 0) return mapResult; if (n == 1) { return 1; } else { collatzMap[n] = 1 + collatzLength(n%2==0?n/2:3*n+1); return collatzMap[n]; } } int main() { int maxIndex = 1; unsigned int max = 1; for (int i=1; i<1000000; i++) { //cout<<i<<endl; unsigned long count = collatzLength(i); if (count > max) { maxIndex = i; max = count; } } cout<<maxIndex<<endl; getchar(); cout<<"Returning..."<<endl; return maxIndex; } 

When I compile and run this program (using the settings of Visual Studio 2012 and Release build), it closes after the program displays "Return ..."

in 10 seconds (on my computer)

Why is this?

Note. I know that this program is poorly written and that I probably should not use "static" on collatzLength or use a cache for this function, but I am not interested in how to make this code better. I just wonder why there is so much to close.

Answer 1

Go to the project settings in the initial project, section "Debugging". Enter _NO_DEBUG_HEAP=1 in the Environment section. You need to do this even in Release mode.

Answer 2

It takes so much time because collatzMap is static , so it will only be freed after the program exits and contains a lot of data, so it will take a little time to free (the size is just over 2 million, and because of how the map works, for each of they have at least one pointer that needs to be freed).

However, on Dev-C ++, it takes less than a second to exit. I think Visual Studio is not doing a good job.

Answer 3

Destroying std::map is very slow in Visual Studio, especially for Debug collections. The slowdown should already disappear using unordered_map .

The VS map implementation creates a red-black tree for storing data, which means that you will need to allocate many tree nodes to store all your data. The limiting factor during destruction is the time required for the tree to pass and de-distribute all nodes. With unordered_map traversing is usually much easier, since distributed buckets are usually no longer scattered like red-black tree nodes (your mileage may vary).

Answer 4

I just tried on my machine with VS 2012 build. To close the program, it does not take more than 2 seconds after the "Return"

Answer 5

When starting VS in debug mode, there are many error checking flags (for example, checking boundaries, viewing memory, etc.). Since you create a lot of data recursively on a static map, it scans the memory before it is released to make sure that nothing has been corrupted. When you switch to the Release build, it should be almost instantaneous.

Upon further verification, you basically allocate almost 1 million pairs ( unsigned long , int ) in the static part of memory. This actually means that ~ 8 MB of data must be freed before the application can complete the close (and since map does not need to be contiguous, it must iterate over all 1 million pairs to remove each of them). Other implementations may slightly optimize memory usage by reserving chunks of space (if he reserved enough space for 100 pairs, this would reduce the freeing process by 2 orders of magnitude).

All that was said, asking why a bad code behaves badly, is similar to how you get wet when you jump into the pool.