Search

Visual C++: std::unordered_map Destructor Performance in Debug Configuration by Timothy003

Resolved
as Fixed Help for as Fixed

6
0
Sign in
 to vote
Type: Bug
ID: 567859
Opened: 6/15/2010 9:37:39 PM
Access Restriction: Public
5
Workaround(s)
4
User(s) can reproduce this bug
std::unordered_map's destructor runs very slow in Debug configuration when there are elements in it. The following C++ program creates and destroys a map of 65,536 ints. Runtime execution takes 45 seconds in Debug configuration, while, in Release configuration, there is virtually no time taken at all.
Details (expand)

Product Language

English

Visual Studio Version

Visual Studio 2010

Operating System

Windows 7

Operating System Language

English

Steps to Reproduce

#include <utility>
#include <unordered_map>
#include <iostream>

using std::cout;
using std::endl;

int main()
{
    {
        int n = 65536;
        std::unordered_map<int, int> m(n);
        for (int i = 0; i < n; )
            m.insert(std::make_pair(i++, 0));
        cout << "destroying map..." << endl;
    }
    cout << "done" << endl;
}

Actual Results

The program takes a very long time to finish. I counted the number of cursor flashes on the console under "destroying map..."

Expected Results

The program finishes instantly.
      You can indicate your satisfaction with how Microsoft handled this issue by completing this quick 3 question survey.

 

File Attachments
0 attachments
Sign in to post a comment.
Posted by Microsoft on 2/16/2011 at 9:02 PM
Hi,

Thanks for reporting this bug. We've fixed it, and the fix will be available in VC11. I've verified that both of your repros execute quickly now:

C:\Temp>type meow.cpp
#include <iostream>
#include <ostream>
#include <unordered_map>
#include <utility>
#include <windows.h>
using namespace std;

long long counter() {
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return li.QuadPart;
}

long long frequency() {
    LARGE_INTEGER li;
    QueryPerformanceFrequency(&li);
    return li.QuadPart;
}

void print_time(const long long start, const long long finish, const char * const s) {
    cout << s << ": " << (finish - start) * 1000.0 / frequency() << " ms" << endl;
}

int main() {
    const int N = 65536;
    long long start = 0;
    long long finish = 0;

    {
        unordered_map<int, int> a(N);

        for (int i = 0; i < N; ++i) {
            a.insert(make_pair(i, 0));
        }

        start = counter();
    }

    finish = counter();

    print_time(start, finish, "Dtor A");

    {
        unordered_map<int, int> b(N);

        for (int i = 0; i < N; ++i) {
            b.insert(make_pair(i * 2, 0));
        }

        start = counter();
    }

    finish = counter();

    print_time(start, finish, "Dtor B");
}

[VC10 RTM]
C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp
meow.cpp

C:\Temp>meow
Dtor A: 43465.3 ms
Dtor B: 43455.6 ms

[VC11]
C:\Temp>cl /EHsc /nologo /W4 /MTd meow.cpp
meow.cpp

C:\Temp>meow
Dtor A: 41.5322 ms
Dtor B: 41.9409 ms

If you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer
Posted by Squeeself on 11/18/2010 at 1:26 PM
Encountered this same issue with much larger maps. Switching to Release solved it, but the clear() workaround does NOT solve it. (Not sure about the other workarounds which I didn't try).
Posted by Timothy003 on 9/9/2010 at 1:34 AM
It should be noted that the current two workarounds do not fix the problem completely. Using either of the workarounds, the sample code will still run significantly slower if you replace m.insert(std::make_pair(i++, 0)) with m.insert(std::make_pair(i++ << 1, 0)).
Posted by Microsoft on 6/16/2010 at 4:01 AM
Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)
Sign in to post a workaround.
Posted by Timothy003 on 9/12/2010 at 9:58 PM
This is a patch for the previous patch I posted. It affects the reuse of iterator objects.

--- $(VCInstallDir)include/xutility    Mon Sep 13 00:30:57 2010
+++ $(VCInstallDir)include/xutility    Mon Sep 13 00:40:07 2010
@@ -147,6 +147,7 @@
                if (_Mynextiter != 0)
                    _Mynextiter->_Mypreviter = this;
                _Parent_proxy->_Myfirstiter = this;
+                _Mypreviter = 0;
                _Myproxy = _Parent_proxy;
                }
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
Posted by Timothy003 on 9/9/2010 at 9:46 AM
Sorry, I missed a file!

--- $(VCInstallDir)include/list    Wed Sep 30 20:23:48 2009
+++ $(VCInstallDir)include/list    Thu Sep 9 10:17:39 2010
@@ -1534,8 +1534,11 @@
                    _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
                else
                    {    // orphan the iterator
-                    (*_Pnext)->_Clrcont();
-                    *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
+                    const_iterator *_Piter = *_Pnext;
+                    _Piter->_Clrcont();
+                    *_Pnext = *(const_iterator **)_Piter->_Getpnext();
+                    if (*_Pnext != 0)
+                        *(*_Pnext)->_Getpprev() = *_Piter->_Getpprev();
                    }
        }
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
Posted by Timothy003 on 9/9/2010 at 9:41 AM
Change debug iterators to be a doubly-linked list.

Unidiffs:
--- $(VCInstallDir)include/deque    Sun Nov 15 18:52:56 2009
+++ $(VCInstallDir)include/deque    Thu Sep 9 12:01:36 2010
@@ -1671,8 +1671,11 @@
                    _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
                else
                    {    // orphan the iterator
-                    (*_Pnext)->_Clrcont();
-                    *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
+                    const_iterator *_Piter = *_Pnext;
+                    _Piter->_Clrcont();
+                    *_Pnext = *(const_iterator **)_Piter->_Getpnext();
+                    if (*_Pnext != 0)
+                        *(*_Pnext)->_Getpprev() = *_Piter->_Getpprev();
                    }
        }
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */

--- $(VCInstallDir)include/forward_list    Wed Sep 30 20:23:48 2009
+++ $(VCInstallDir)include/forward_list    Thu Sep 9 12:01:33 2010
@@ -1340,8 +1340,11 @@
                    _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
                else
                    {    // orphan the iterator
-                    (*_Pnext)->_Clrcont();
-                    *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
+                    const_iterator *_Piter = *_Pnext;
+                    _Piter->_Clrcont();
+                    *_Pnext = *(const_iterator **)_Piter->_Getpnext();
+                    if (*_Pnext != 0)
+                        *(*_Pnext)->_Getpprev() = *_Piter->_Getpprev();
                    }
        }
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */

--- $(VCInstallDir)include/vector    Sun Nov 15 18:52:56 2009
+++ $(VCInstallDir)include/vector    Thu Sep 9 10:17:43 2010
@@ -1443,8 +1443,11 @@
                    _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
                else
                    {    // orphan the iterator
-                    (*_Pnext)->_Clrcont();
-                    *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
+                    const_iterator *_Piter = *_Pnext;
+                    _Piter->_Clrcont();
+                    *_Pnext = *(const_iterator **)_Piter->_Getpnext();
+                    if (*_Pnext != 0)
+                        *(*_Pnext)->_Getpprev() = *_Piter->_Getpprev();
                    }
        }

@@ -2593,8 +2596,11 @@
                    _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
                else
                    {    // orphan the iterator
-                    (*_Pnext)->_Clrcont();
-                    *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
+                    const_iterator *_Piter = *_Pnext;
+                    _Piter->_Clrcont();
+                    *_Pnext = *(const_iterator **)_Piter->_Getpnext();
+                    if (*_Pnext != 0)
+                        *(*_Pnext)->_Getpprev() = *_Piter->_Getpprev();
                    }
                }
        }

--- $(VCInstallDir)include/xtree    Sun Nov 15 18:52:56 2009
+++ $(VCInstallDir)include/xtree    Thu Sep 9 12:01:27 2010
@@ -1855,8 +1855,11 @@
                    _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
                else
                    {    // orphan the iterator
-                    (*_Pnext)->_Clrcont();
-                    *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
+                    const_iterator *_Piter = *_Pnext;
+                    _Piter->_Clrcont();
+                    *_Pnext = *(const_iterator **)_Piter->_Getpnext();
+                    if (*_Pnext != 0)
+                        *(*_Pnext)->_Getpprev() = *_Piter->_Getpprev();
                    }
        }
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */

--- $(VCInstallDir)include/xutility    Sun Nov 15 18:52:56 2009
+++ $(VCInstallDir)include/xutility    Thu Sep 9 10:17:43 2010
@@ -107,12 +107,12 @@
    {    // store links to container proxy, next iterator
public:
    _Iterator_base12()
-        : _Myproxy(0), _Mynextiter(0)
+        : _Myproxy(0), _Mynextiter(0), _Mypreviter(0)
        {    // construct orphaned iterator
        }

    _Iterator_base12(const _Iterator_base12& _Right)
-        : _Myproxy(0), _Mynextiter(0)
+        : _Myproxy(0), _Mynextiter(0), _Mypreviter(0)
        {    // copy an iterator
        *this = _Right;
        }
@@ -144,6 +144,8 @@
                _Lockit _Lock(_LOCK_DEBUG);
                _Orphan_me();
                _Mynextiter = _Parent_proxy->_Myfirstiter;
+                if (_Mynextiter != 0)
+                    _Mynextiter->_Mypreviter = this;
                _Parent_proxy->_Myfirstiter = this;
                _Myproxy = _Parent_proxy;
                }
@@ -168,18 +170,23 @@
        return (&_Mynextiter);
        }

+    _Iterator_base12 **_Getpprev()
+        {    // get address of remaining iterator chain
+        return (&_Mypreviter);
+        }
+
    void _Orphan_me()
        {    // cut ties with parent
#if _ITERATOR_DEBUG_LEVEL == 2
        if (_Myproxy != 0)
            {    // adopted, remove self from list
-            _Iterator_base12 **_Pnext = &_Myproxy->_Myfirstiter;
-            while (*_Pnext != 0 && *_Pnext != this)
-                _Pnext = &(*_Pnext)->_Mynextiter;
-
-            if (*_Pnext == 0)
+            _Iterator_base12 **_Pnext =
+                _Mypreviter != 0 ? &_Mypreviter->_Mynextiter : &_Myproxy->_Myfirstiter;
+            if (*_Pnext != this)
                _DEBUG_ERROR("ITERATOR LIST CORRUPTED!");
            *_Pnext = _Mynextiter;
+            if (_Mynextiter != 0)
+                _Mynextiter->_Mypreviter = _Mypreviter;
            _Myproxy = 0;
            }
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
@@ -187,6 +194,7 @@

    _Container_proxy *_Myproxy;
    _Iterator_base12 *_Mynextiter;
+    _Iterator_base12 *_Mypreviter;
    };

        // MEMBER FUNCTIONS FOR _Container_base12
Posted by Timothy003 on 9/8/2010 at 12:52 AM
Modify file $(VCInstallDir)include\xhash. At line 313:

    ~_Hash()
        {    // destroy hash table
+        _List.clear();
        }

    _Myt& operator=(const _Myt& _Right)
Posted by Timothy003 on 6/15/2010 at 9:38 PM
Clear the map before it is destroyed.
© 2013 Microsoft Corporation. All rights reserved. Microsoft Connect Terms of Use | Trademarks | Privacy Statement