¿Por qué el rendimiento de estas multiplicaciones de matriz es tan diferente?

Question

Escribí dos clases de matriz en Java solo para comparar el rendimiento de sus multiplicaciones de matriz. Una clase (Mat1) almacena un miembro double[][] A donde la fila i de la matriz es A[i]. La otra clase (Mat2) almacena A y T donde T es la transposición de A.

Digamos que tenemos una matriz cuadrada M y queremos el producto de M.mult(M). Llame al producto P.

Cuando M es un ejemplo Mat1 el algoritmo utilizado fue el sencillo uno:

P[i][j] += M.A[i][k] * M.A[k][j] 
    for k in range(0, M.A.length) 

En el caso en que M es un mat2 utilicé:

P[i][j] += M.A[i][k] * M.T[j][k] 

que es el mismo algoritmo porque T[j][k]==A[k][j] . En las matrices de 1000x1000, el segundo algoritmo tarda aproximadamente 1,2 segundos en mi máquina, mientras que el primero tarda al menos 25 segundos. Esperaba que el segundo fuera más rápido, pero no por mucho. La pregunta es, ¿por qué es esto mucho más rápido?

Mi única suposición es que la segunda hace un mejor uso de las memorias caché de la CPU, ya que los datos se extraen en cachés en fragmentos de más de 1 palabra, y el segundo algoritmo se beneficia atravesando solo filas, mientras que la primera ignora los datos se extrajeron en las memorias caché yendo de inmediato a la fila siguiente (que es ~ 1000 palabras en la memoria, porque las matrices se almacenan en orden principal de fila), ninguno de los datos está almacenado en caché.

Le pregunté a alguien y pensó que era debido a los patrones de acceso a la memoria más amigables (es decir, que la segunda versión daría como resultado menos fallas suaves TLB). No pensé en esto en absoluto, pero puedo ver cómo resulta en menos fallas TLB.

Entonces, ¿cuál es? ¿O hay alguna otra razón para la diferencia de rendimiento?

Answer 1

Esto debido a la localidad de sus datos.

En RAM una matriz, aunque bidimensional desde su punto de vista, por supuesto se almacena como una matriz contigua de bytes. La única diferencia con una matriz 1D es que la compensación se calcula interpolando ambos índices que usa.

Esto significa que si accede al elemento en la posición x,y se calculará x*row_length + y y esta será la compensación utilizada para hacer referencia al elemento en la posición especificada.

Lo que ocurre es que una gran matriz no se almacena en una página de memoria (así es como el SO administra la RAM, dividiéndola en fragmentos) por lo que tiene que cargar dentro de la memoria caché de la CPU la página correcta Intenta acceder a un elemento que no está presente.

Mientras haga su multiplicación contigua no crea ningún problema, ya que utiliza principalmente todos los coeficientes de una página y luego pasa al siguiente, pero si invierte los índices, lo que sucede es que cada elemento puede estar en una página de memoria diferente, así que cada vez que necesite pedirle a RAM una página diferente, esto casi por cada multiplicación que haga, esta es la razón por la cual la diferencia es muy clara.

(I bastante simplificado toda la explicación, es sólo para darle la idea básica en torno a este problema)

En cualquier caso, no creo que esto es causado por la JVM por sí mismo. Tal vez se relaciona con la forma en que su sistema operativo gestiona la memoria del proceso de Java.

Answer 2

Las hipótesis de caché y TLB son razonables, pero me gustaría ver el código completo de su punto de referencia ... no solo los fragmentos de pseudo-código.

Otra posibilidad es que la diferencia de rendimiento se deba a que su aplicación utiliza un 50% más de memoria para las matrices de datos en la versión con la transposición. Si el tamaño del almacenamiento dinámico de su JVM es pequeño, es posible que esto esté causando que el GC se ejecute con demasiada frecuencia. Esto bien podría ser el resultado de usar el tamaño de almacenamiento dinámico predeterminado. (Tres lotes de 1000 x 1000 x 8 bytes son ~ 24Mb)

Intente establecer los tamaños de almacenamiento máximo inicial y máximo en (digamos) el doble del tamaño máximo actual. Si eso no hace diferencia, entonces este no es un problema simple de tamaño de pila.

Answer 3

Es fácil adivinar que el problema podría ser una localidad, y tal vez sí, pero aún así es una suposición.

No es necesario adivinar. Dos técnicas podrían darle la respuesta: pasos individuales y pausas aleatorias.

Si pasa un solo paso por el código lento, es posible que descubra que está haciendo muchas cosas que nunca soñó. Tal como, usted pregunta? Pruébalo y descúbrelo. Lo que debería ver en al hacerlo, en el nivel del lenguaje de máquina, es atravesar eficientemente el bucle interno sin perder movimiento.

Si en realidad está recorriendo el bucle interno sin movimiento inútil, la pausa aleatoria le dará información. Como el lento tarda 20 veces más que el rápido, eso implica que el 95% del tiempo hace algo que no tiene que hacer. Entonces mira lo que es Cada vez que lo detenga, existe una probabilidad del 95% de que vea qué es eso y por qué.

Si en la lentitud, las instrucciones que está ejecutando aparecen tan eficaces como la rápida, entonces la ubicación de la memoria caché es una suposición razonable de por qué es lenta. Estoy seguro de que, una vez que haya eliminado cualquier otra tontería que pueda estar sucediendo, esa localidad de memoria dominará.

Answer 4

Usted puede tratar de comparar el rendimiento entre JDK6 y OpenJDK7, dada esta set of results ...