Home Dashboard Directory Help
Search

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


Status: 

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)
view
4
User(s) can reproduce this bug

Description

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
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.