¿Tabla hash más rápida en C# que en C++?

Question

Aquí hay una curiosidad que he estado investigando. La clase de diccionario .NET se comporta de forma ridículamente rápida en comparación con el mapa desordenado STL en una prueba que sigo ejecutando, y no puedo entender por qué.

(0,5 segundos frente a 4 segundos en mi máquina) (.NET 3.5 SP1 frente a Visual Studio STL de 2008 Express SP1)

Por otro lado, si puedo implementar mi propia tabla hash en C# y C++ , la versión de C++ es aproximadamente dos veces más rápida que la de C#, lo cual está bien porque refuerza mi sentido común de que el código máquina nativo es a veces más rápido. (Ver. Dije "a veces".) Siendo la misma persona en ambos idiomas, me pregunto qué trucos fue capaz de jugar el codificador C# de Microsoft que el codificador C++ de Microsoft no. Tengo problemas para imaginar cómo un compilador podría jugar esos trucos por sí mismo, pasando por el problema de optimizar lo que deberían ser llamadas a funciones arbitrarias.

Es una prueba sencilla, almacenamiento y recuperación de enteros.

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

las dos versiones no son equivalentes, su están construyendo un iterador en cada pasada de su C++ mientras bucle. eso lleva tiempo de CPU y arroja tus resultados.

Answer 2

Habrá algunas diferencias en el nivel del código: el hecho de que el mapa desordenado tome un par fuerza la construcción de dicho objeto, cuando C# podría ser más rápido al pasar dos parámetros en Agregar.

Otro punto es la implementación de los propios hashtables: la implementación de la función hash o la forma de manejar las colisiones provocarán diferentes patrones de rendimiento.

El alineamiento y el almacenamiento en caché, la compatibilidad con JIT de algunos algoritmos y la comparación de dos implementaciones diferentes en dos idiomas diferentes se vuelve muy difícil, y lo único que se puede comparar es la tarea en cuestión. Pruebe con menos elementos o más, o intente acceder a los elementos al azar en lugar de hacerlo en secuencia, y es posible que vea resultados muy diferentes.

Answer 3

Está midiendo el costo de la administración de memoria explícita. Más estadísticas están disponibles here. Esto es relevant too. Y Chris Sells' attempt para agregar la finalización determinística al CLR es notable.