¿Por qué la multiplicación de matrices en .NET es tan lenta?

Question

No entiendo muy bien qué hace que la multiplicación de matrices en C# /. NET (e incluso Java) sea tan lenta.

Eche un vistazo a este índice de referencia ( source): Intentando encontrar un punto de referencia actualizado.

Java vs C# vs C++ breakdown http://img411.imageshack.us/img411/9324/perf.gif

número entero C# 's y el doble de rendimiento es maldita cerca de C++ compilado con MSVC++. 87% más rápido para el doble y 99% más rápido para el entero de 32 bits. Bastante malditamente bueno, diría. Pero luego mira la multiplicación de la matriz. La brecha se amplía a C# siendo aproximadamente el 19% más rápido. Esta es una gran discrepancia que no entiendo. La multiplicación de matrices es solo un montón de matemáticas simples. ¿Cómo se está poniendo tan lento? ¿No debería ser más o menos tan rápido como un número equivalente de operaciones simples de punto flotante o entero?

Esto es especialmente preocupante con los juegos y con XNA, donde el rendimiento de matrices y vectores es crítico para cosas como los motores de física. Hace algún tiempo, Mono agregó soporte para las instrucciones SIMD a través de algunas clases ingeniosas de vectores y matrices. Se cierra la brecha y hace Mono más rápido que el C++ escrito a mano, aunque no tan rápido como C++ con SIMD. (source)

Matrix multiplication comparison http://img237.imageshack.us/img237/2788/resultse.png

lo que está pasando aquí?

Editar: Mirando más de cerca, he leído mal el segundo gráfico. C# parece bastante cerca. ¿El primer punto de referencia solo está haciendo algo terriblemente incorrecto? Lo siento, me perdí el número de versión en el primer punto de referencia. Lo agarré como una referencia práctica para el "álgebra lineal C# es lento" que siempre he escuchado. Trataré de buscar otro.

Answer 1

Con matrices grandes como esta, la memoria caché de la CPU se convierte en el factor limitante. Lo que es hiperimportante es cómo se almacena la matriz. Y el código de referencia es comparar manzanas y naranjas. El código C++ utiliza matrices irregulares, el código C# usa matrices bidimensionales.

Reescribiendo el código C# para usar matrices dentadas también duplicó su velocidad. Reescribir el código de multiplicación de la matriz para evitar que la verificación del límite del índice de la matriz no pareciera tener sentido, nadie usaría un código como este para problemas reales.

Answer 2

Claramente, el autor de la evaluación comparativa no entendió la diferencia entre las matrices irregulares y multidimensionales en C#. Realmente no era una comparación de manzanas a manzanas. Cuando cambié el código para usar matrices irregulares en lugar de matrices multidimensionales para que funcione de una manera más similar a Java, entonces el código C# termina ejecutando el doble de rápido ... haciéndolo más rápido que Java (aunque apenas y eso es probablemente Estadísticamente insignificante). En C# las matrices multidimensionales son más lentas porque hay un trabajo extra involucrado en encontrar la ranura de la matriz y porque la verificación de límites de la matriz no se puede eliminar para ellas ... todavía.

Consulte este question para un análisis más profundo de por qué las matrices multidimensionales son más lentas que las matrices irregulares.

Consulte este blog para obtener más información sobre la comprobación de límites de matriz. El artículo específicamente advierte contra el uso de matrices multidimensionales para la multiplicación de matrices.

Answer 3

He aquí un punto de referencia actualizado tratar con multiplcation matriz (y algunos puntos de referencia utilizando la nueva Biblioteca paralelo de tareas):

Parallel Matrix Multiplication with the Task Parallel Library (TPL)

El artículo entra en diferentes métodos, y explica por qué las matrices multidimensionales son una mala elección:

La manera más fácil de hacer matriz multiplicación es con una matriz multidimensional .NET con i, j, k ordenación en los bucles . Los problemas son dobles. Primero, el i, j.k que ordena accede a la memoria de una manera agitada causando que los datos en ubicaciones variadas sean extraídos. En segundo lugar, está usando una matriz multidimensional . Sí, la matriz multidimensional .NET es conveniente, pero es muy lenta.

Answer 4

para explicar el origen de la idea de que las operaciones de la matriz de XNA son lentos:

En primer lugar está el gotcha-nivel principiante: operator* de XNA La clase Matrix hará varias copias. Esto es más lento de lo que cabría esperar del código C++ equivalente.

(Por supuesto, si se utiliza Matrix.Multiply(), entonces puede pasar por referencia.)

La segunda razón es que el .NET Compact Framework utilizado por XNA en la Xbox 360 no tiene acceso al hardware VMX (SIMD) que está disponible para juegos C++ nativos.

Es por eso que sigues oyendo que es lento, al menos. Como puede ver en los puntos de referencia que publicó, en realidad no es tan "lento" cuando compara manzanas con manzanas.