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

Status : 

  Fixed<br /><br />
		This item has been fixed in the current or upcoming version of this product.<br /><br />
		A more detailed explanation for the resolution of this particular item may have been provided in the comments section.


1
0
Sign in
to vote
ID 689342 Comments
Status Closed Workarounds
Type Bug Repros 0
Opened 9/18/2011 1:12:00 PM
Access Restriction Public
Moderator Decision Sent to Engineering Team for consideration

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");
}
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)