Hash table plus rapide en C# qu'en C++?

Question

Voici une curiosité que j'ai étudiée. La classe .NET Dictionary est ridiculement rapide par rapport à la STL unordered_map dans un test que je continue de faire, et je n'arrive pas à comprendre pourquoi.

(0,5 secondes contre 4 secondes sur ma machine) (.NET 3.5 SP1 par rapport à Visual Studio de STL de 2008 Express SP1)

D'autre part, si je mets en œuvre ma propre table de hachage en C# et C++ , la version C++ est environ deux fois plus rapide que la version C#, ce qui est bien parce que cela renforce mon bon sens que le code machine natif est parfois plus rapide. (J'ai dit "parfois".) Moi étant la même personne dans les deux langues, je me demande quelles astuces le codeur C# de Microsoft pouvait-il jouer que le codeur C++ de Microsoft n'était pas? J'ai du mal à imaginer comment un compilateur pourrait jouer de telles astuces tout seul, en passant par la difficulté d'optimiser ce qui devrait lui sembler être des appels de fonction arbitraires.

C'est un test simple, le stockage et la récupération des nombres entiers.

C#:

const int total = (1 << 20); 
int sum = 0; 
Dictionary<int, int> dict = new Dictionary<int, int>(); 
for(int i = 0; i < total; i++) 
{ 
    dict.Add(i, i * 7); 
} 

for(int j = 0; j < (1 << 3); j++) 
{ 
    int i = total; 
    while(i > 0) 
    { 
     i--; 
     sum += dict[i]; 
    } 
} 
Console.WriteLine(sum); 

C++:

const int total = (1 << 20); 
int sum = 0; 
std::tr1::unordered_map<int, int> dict; 
for(int i = 0; i < total; i++) 
{ 
    dict.insert(pair<int, int>(i, i * 7)); 
} 

for(int j = 0; j < (1 << 3); j++) 
{ 
    int i = total; 
    while(i > 0) 
    { 
     i--; 
     std::tr1::unordered_map<int, int>::const_iterator found = 
      dict.find(i); 
     sum += found->second; 
    } 
} 
cout << sum << endl; 

Answer 1

les deux versions ne sont pas équivalentes, vous êtes la construction d'un iterator à chaque passage de votre C++ en boucle. cela prend du temps CPU et jette vos résultats.

Answer 2

Il y aura quelques différences au niveau du code: le fait que la carte non ordonnée prenne une paire force la construction de cet objet, alors que C# pourrait être plus rapide en passant deux paramètres dans Add.

Un autre point est la mise en œuvre des tables de hachage elles-mêmes: l'implémentation de la fonction de hachage, ou la façon de gérer les collisions, entraînera des performances différentes.

Jeter dans l'alignement et la mise en cache, la convivialité JIT de certains algorithmes et comparer deux implémentations différentes dans deux langues différentes devient très difficile, et la seule chose que vous pouvez comparer est la tâche particulière à portée de main. Essayez avec moins ou plus d'éléments, ou essayez d'accéder aux éléments de façon aléatoire plutôt que séquentielle, et vous pourriez voir des résultats très différents.

Answer 3

Vous mesurez le coût de la gestion de la mémoire explicite. Plus de statistiques sont disponibles here. Ceci est relevant too. Et Chris Sells' attempt pour ajouter la finalisation déterministe à la CLR est notable.