Home Dashboard Directory Help
Search

unordered_map thousand time slower than the vc++ 2010 version by badre429


Status: 

Closed
 as Fixed Help for as Fixed


1
0
Sign in
to vote
Type: Bug
ID: 689342
Opened: 9/18/2011 1:12:00 PM
Access Restriction: Public
Moderator Decision: Sent to Engineering Team for consideration
0
Workaround(s)
view
0
User(s) can reproduce this bug

Description


it tried this code in both version visual c++ 2010 and visual studio 11 developer preview
and the i was shoked by the result
vs 11 TIME = 100 * vs2010 TIME
//______________________________________________
#include<iostream>
#include<unordered_map>
#include<Windows.h>
using namespace std;

double DoubleRand()
{
    return (double(rand())*double(rand())*double(rand())+double(rand())*double(rand())*double(rand())+double(rand())*double(rand())*double(rand()))/(double(rand())*double(rand())*double(rand())+double(rand())*double(rand())*double(rand()));
}
void print(double x)
{
cout    <<x<<endl;
}

int main()
{
    int _time=GetTickCount();
    srand(_time);
    int tableLenght=1000000;
    unordered_map<double ,int> maptab;
    
    double * tab=new double[tableLenght];
    for (int i = 0; i <tableLenght ; i++)
    {
        tab[i]=DoubleRand();
    }

    for (int i = 0; i <tableLenght ; i++)
    {
        maptab[tab[i]]=i;
    }
    double somme=0;
    for (int i = 0; i < 10; i++)
    {
        for (int k = 0; k < tableLenght; k++)
        {
            somme+=maptab[tab[k]];
        }
    }
    int somme2=0;

     for (int i = 0; i < tableLenght; i++)
                {
                    somme2 += i;
                 }
    print(maptab.size());
    print(somme);
    print(somme2*10);
    print(GetTickCount()- _time );
    system("pause");
}
Details
Sign in to post a comment.
Posted by Microsoft on 11/4/2011 at 8:48 PM
Hi,

Thanks for reporting this bug. We've fixed it, and the fix will be available in VC11. Additionally, we've improved the performance of our hashes, so you should observe that unordered_map is even faster than before.

This problem was caused by the hash<float/double/long double> specializations being defined in a different subheader than the primary template for hash<T>. When you include <unordered_map> without including <functional>, the primary template is used instead of the desired specializations. While this compiles, it does something very bad (truncating floating-point to integer, causing zillions of collisions). As a workaround until you get the fix, simply include <functional> along with <unordered_map>.

The fix defines the floating-point specializations immediately below the primary template, making it impossible to trigger this kind of bug again. (Additionally, the primary template's smash-to-integer definition has been removed.)

Please note that unordered_map<double, X> is inherently problematic, because of floating-point equality issues. It's required to work by the Standard, but you should be aware of how floating-point behaves.

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 MS-Moderator07 [Feedback Moderator] on 9/18/2011 at 9:54 PM
Thanks for your feedback.

We are rerouting this issue to the appropriate group within the Visual Studio Product Team for triage and resolution. These specialized experts will follow-up with your issue.
Posted by MS-Moderator01 on 9/18/2011 at 1:41 PM
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.