Perché la fissione del loop ha senso in questo caso?

Question

Il codice senza fissione è simile al seguente:

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 fissione:

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; 
} 

Note:

• Il collo di bottiglia è map[hash(keys[i])] che accede alla memoria in modo casuale.

• normalmente, sarebbe if(tmp[i]) res[ret++] = i; per evitare il se, sto usando ret += tmp[i].

• map[..] è sempre 0 o 1

La versione fissione è di solito molto più veloce e sto cercando di spiegare perché. La mia ipotesi migliore è che ret += map[..] introduca ancora alcune dipendenze e che impedisca l'esecuzione speculativa.

Mi piacerebbe sapere se qualcuno ha una spiegazione migliore.

Answer 1

Dai miei test, ottengo circa 2 volte la differenza di velocità tra i loop fusi e split. Questa differenza di velocità è molto costante, non importa quanto modifico il loop.

Fused: 1.096258 seconds 
Split: 0.562272 seconds 

(Fare riferimento alla parte inferiore per il codice di prova completa.)

---

Anche se non sono sicuro al 100%, ho il sospetto che questo è dovuto ad una combinazione delle due cose:

1. Saturazione del buffer di memoria di caricamento per memory disambigutation a causa di mancanze della cache da map[gethash(keys[i])].
2. Una dipendenza aggiunta nella versione del loop fuso.

È ovvio che lo map[gethash(keys[i])] causerà un errore di cache quasi ogni volta. In effetti, è probabilmente sufficiente per saturare l'intero buffer del load-store.

Ora diamo un'occhiata alla dipendenza aggiunta. Il problema è la variabile 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 variabile ret è necessario per la risoluzione degli indirizzi del negozio res[ret] = i;.

• Nel loop fuso, ret proviene da una mancanza di cache sicura.
• Nel ciclo di divisione, ret è in arrivo tmp[i] - che è molto più veloce.

Questo ritardo nella risoluzione indirizzo del caso anello fuso probabile causa res[ret] = i memorizzare intasare il buffer load-store insieme map[gethash(keys[i])].

Dal momento che il buffer di carico-store ha una dimensione fissa, ma si ha il doppio della spazzatura in esso:
si è solo in grado di sovrapporre la cache manca la metà di quello di prima. Quindi 2 rallentamenti.

---

Suppongo che se abbiamo cambiato il ciclo fusa a questo:

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; 
} 

Questo romperà la dipendenza risoluzione degli indirizzi.

^{(Si noti che non è più lo stesso, ma è solo per dimostrare la differenza di prestazioni.)}

allora otteniamo tempi simili:

Fused: 0.487477 seconds 
Split: 0.574585 seconds 

---

Ecco il test completo codice:

#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

Non penso che sia l'indicizzazione dell'array, ma la chiamata alla funzione hash() che potrebbe causare uno stallo della pipeline e impedire un ottimale riordino delle istruzioni.