¿Por qué la fisión del lazo tiene sentido en este caso?

Question

El código sin la fisión se ve así:

int check(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[hash(keys[i])] 
    } 
    return ret; 
} 

Con la fisión:

int check(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     tmp[i] = map[hash(keys[i])]; 
    } 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += tmp[i]; 
    } 
    return ret; 
} 

Notas:

• El cuello de botella es map[hash(keys[i])] que accede a la memoria al azar.

• normalmente, sería if(tmp[i]) res[ret++] = i; para evitar el si, estoy usando ret += tmp[i].

• map[..] siempre es 0 ó 1

La versión de fisión es por lo general mucho más rápido y estoy tratando de explicar por qué. Mi mejor suposición es que ret += map[..] todavía presenta cierta dependencia y eso evita la ejecución especulativa.

Me gustaría saber si alguien tiene una mejor explicación.

Answer 1

Según mis pruebas, obtengo aproximadamente una diferencia de velocidad de 2x entre los bucles fusionados y divididos. Esta diferencia de velocidad es muy constante, sin importar cómo modifique el ciclo.

Fused: 1.096258 seconds 
Split: 0.562272 seconds 

(Consulte la parte inferior para el código de prueba completa.)

---

Aunque no estoy 100% seguro, sospecho que esto se debe a una combinación de dos cosas:

1. Saturación del almacenamiento intermedio de carga-almacén para memory disambigutation debido a fallas de caché de map[gethash(keys[i])].
2. Una dependencia añadida en la versión de bucle fusionado.

Es obvio que map[gethash(keys[i])] dará como resultado una falta de caché casi siempre. De hecho, probablemente sea suficiente para saturar todo el buffer de la tienda de carga.

Ahora veamos la dependencia agregada. La cuestión es la variable ret:

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 

La variable ret es necesaria para la resolución de direcciones del almacén res[ret] = i;.

• En el bucle fusionado, ret viene de un caché seguro.
• En el bucle dividido, ret viene tmp[i] - que es mucho más rápido.

Este retraso en la resolución de la dirección de la caja de bucle fusionado causas probables res[ret] = i para almacenar a obstruir el tampón de carga-tienda junto con map[gethash(keys[i])].

Dado que el búfer de la tienda de carga tiene un tamaño fijo, pero tiene el doble de basura en él:
Solo puede superponer la caché falta la mitad que antes. Por lo tanto, 2 veces más lento.

---

Supongamos que si cambiamos el bucle fusionado a esto:

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[i] = i; // Change "res" to "i" 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 

Esto romperá la dependencia de resolución de direcciones.

^{(Tenga en cuenta que no es la misma de antes, pero es sólo para demostrar la diferencia de rendimiento.)}

A continuación, obtener tiempos similares:

Fused: 0.487477 seconds 
Split: 0.574585 seconds 

---

Aquí está la prueba completa código:

#define SIZE 67108864 

unsigned gethash(int key){ 
    return key & (SIZE - 1); 
} 

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 
int check_split(int * res, char * map, int n, int * keys, int *tmp){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     tmp[i] = map[gethash(keys[i])]; 
    } 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += tmp[i]; 
    } 
    return ret; 
} 


int main() 
{ 
    char *map = (char*)calloc(SIZE,sizeof(char)); 
    int *keys = (int*)calloc(SIZE,sizeof(int)); 
    int *res = (int*)calloc(SIZE,sizeof(int)); 
    int *tmp = (int*)calloc(SIZE,sizeof(int)); 
    if (map == NULL || keys == NULL || res == NULL || tmp == NULL){ 
     printf("Memory allocation failed.\n"); 
     system("pause"); 
     return 1; 
    } 

    // Generate Random Data 
    for (int i = 0; i < SIZE; i++){ 
     keys[i] = (rand() & 0xff) | ((rand() & 0xff) << 16); 
    } 

    printf("Start...\n"); 

    double start = omp_get_wtime(); 
    int ret; 

    ret = check_fused(res,map,SIZE,keys); 
// ret = check_split(res,map,SIZE,keys,tmp); 

    double end = omp_get_wtime(); 

    printf("ret = %d",ret); 
    printf("\n\nseconds = %f\n",end - start); 

    system("pause"); 
} 

Answer 2

No creo que sea la indexación de la matriz, sino la llamada a la función hash() que puede causar una interrupción de la tubería y evitar un reordenamiento de instrucciones óptimo.