¿Qué hay de malo con el uso de la asociatividad por los comstackdores?

A veces, la asociatividad puede utilizarse para perder dependencias de datos y me llamó la atención lo mucho que puede ayudar. Me sorprendió bastante descubrir que casi puedo obtener un factor de aceleración de 4 desenrollando manualmente un bucle trivial, tanto en Java (comstackción 1.7.0_51-b13) como en C (gcc 4.4.3).

Entonces, o estoy haciendo algo bastante estúpido o los comstackdores ignoran una poderosa herramienta. Empecé con

int a = 0; for (int i=0; i<N; ++i) a = M1 * a + t[i]; 

que calcula algo cercano a String.hashCode() (establece M1=31 y usa un char[] ). El cálculo es bastante trivial y para t.length=1000 toma aproximadamente 1.2 microsegundos en mi i5-2400 @ 3.10GHz (tanto en Java como en C).

Observe que cada dos pasos a se multiplica por M2 = M1*M1 y agrega algo. Esto lleva a esta pieza de código

 int a = 0; for (int i=0; i<N; i+=2) { a = M2 * a + (M1 * t[i] + t[i+1]); // <-- note the parentheses! } if (i < len) a = M1 * a + t[i]; // Handle odd length. 

Esto es exactamente el doble de rápido que el primer fragmento. Extrañamente, omitiendo el paréntesis se come el 20% de la aceleración. Curiosamente, esto puede repetirse y se puede lograr un factor de 3.8.

A diferencia de java, gcc -O3 elige no desenrollar el bucle. Es una elección sabia ya que no ayudaría de todos modos (como se -funroll-all-loops ).

Entonces mi pregunta 1 es: ¿Qué impide tal optimización?

Google no funcionaba, solo obtenía “matrices asociativas” y “operadores asociativos”.

Actualizar

He pulido mi punto de referencia un poco y puedo proporcionar algunos resultados ahora. No hay aceleración más allá de desenrollar 4 veces, probablemente debido a la multiplicación y la sum de 4 ciclos juntos.

Actualización 2

Como Java ya desenrolla el bucle, todo el trabajo duro está hecho. Lo que obtenemos es algo así como

 ...pre-loop for (int i=0; i<N; i+=2) { a2 = M1 * a + t[i]; a = M1 * a2 + t[i+1]; } ...post-loop 

donde la parte interesante puede ser reescrita como

  a = M1 * ((M1 * a) + t[i]) + t[i+1]; // latency 2mul + 2add 

Esto revela que hay 2 multiplicaciones y 2 adiciones, todas ellas para ser ejecutadas secuencialmente, por lo que necesitan 8 ciclos en una CPU x86 moderna. Todo lo que necesitamos ahora es algunas matemáticas de la escuela primaria (que trabajan para int s incluso en caso de desbordamiento o lo que sea, pero no aplicable al punto flotante).

  a = ((M1 * (M1 * a)) + (M1 * t[i])) + t[i+1]; // latency 2mul + 2add 

Hasta ahora no hemos ganado nada, pero nos permite doblar las constantes

  a = ((M2 * a) + (M1 * t[i])) + t[i+1]; // latency 1mul + 2add 

y gana aún más reagrupando la sum

  a = (M2 * a) + ((M1 * t[i]) + t[i+1]); // latency 1mul + 1add 

Así es como entiendo sus dos casos: en el primer caso, tiene un ciclo que toma N pasos; en el segundo caso fusionó manualmente dos repeticiones consecutivas del primer caso en uno, por lo que solo necesita hacer N / 2 pasos en el segundo caso. Tu segundo caso se ejecuta más rápido y te preguntas por qué el tonto comstackdor no pudo hacerlo automáticamente.

No hay nada que evite que el comstackdor realice dicha optimización. Pero tenga en cuenta que esta reescritura del bucle original conduce a un tamaño ejecutable mayor : tiene más instrucciones dentro del bucle for y el adicional if después del bucle.
Si N = 1 o N = 3, es probable que el bucle original sea más rápido (menos bifurcación y mejor almacenamiento en memoria caché / captación previa / predicción de bifurcación). Hizo las cosas más rápido en su caso, pero puede hacer las cosas más lentas en otros casos. No es claro si vale la pena hacer esta optimización y puede ser altamente no trivial implementar tal optimización en un comstackdor .

Por cierto, lo que has hecho es muy similar a la vectorización de bucle, pero en tu caso, hiciste el paso paralelo manualmente y enchufaste el resultado. La charla confidencial del comstackdor de Eric Brumer le dará una idea de por qué reescribir bucles en general es complicado y cuáles son los inconvenientes / inconvenientes que existen (mayor tamaño del ejecutable, potencialmente más lento en algunos casos). Así que los escritores de comstackdores son muy conscientes de esta posibilidad de optimización y están trabajando activamente en ello, pero en general no es trivial y puede hacer que las cosas sean más lentas.


Por favor, intenta algo para mí:

 int a = 0; for (int i=0; i 

asumiendo M1=31 . En principio, el comstackdor debe ser lo suficientemente inteligente como para reescribir 31*a en (a< <5)-a pero tengo curiosidad si realmente lo hace.