Quando, se mai, lo svolgimento del ciclo è ancora utile?

Question

Ho cercato di ottimizzare un codice estremamente critico per le prestazioni (un algoritmo di ordinamento rapido che viene chiamato milioni e milioni di volte all'interno di una simulazione di monte carlo) per lo srotolamento del ciclo. Ecco il ciclo interno che sto cercando di accelerare:

// Search for elements to swap. 
while(myArray[++index1] < pivot) {} 
while(pivot < myArray[--index2]) {} 

ho cercato srotolando a qualcosa di simile:

while(true) { 
    if(myArray[++index1] < pivot) break; 
    if(myArray[++index1] < pivot) break; 
    // More unrolling 
} 


while(true) { 
    if(pivot < myArray[--index2]) break; 
    if(pivot < myArray[--index2]) break; 
    // More unrolling 
} 

questo ha fatto assolutamente nessuna differenza quindi l'ho cambiato di nuovo alla forma più leggibile. Ho avuto esperienze simili altre volte ho provato a srotolare il ciclo. Data la qualità dei predittori di ramo sull'hardware moderno, quando, se mai, lo srotolamento del ciclo è ancora un'ottimizzazione utile?

Answer 1

Lo srotolamento del loop ha senso se è possibile interrompere le catene di dipendenza. Ciò dà a una CPU fuori scala o super-scalare la possibilità di pianificare le cose meglio e quindi correre più velocemente.

Un semplice esempio:

for (int i=0; i<n; i++) 
{ 
    sum += data[i]; 
} 

Qui la catena di dipendenza degli argomenti è molto breve. Se ottieni uno stallo perché hai una cache-miss sull'array di dati, la CPU non può fare altro che aspettare.

D'altra parte di questo codice:

for (int i=0; i<n; i+=4) 
{ 
    sum1 += data[i+0]; 
    sum2 += data[i+1]; 
    sum3 += data[i+2]; 
    sum4 += data[i+3]; 
} 
sum = sum1 + sum2 + sum3 + sum4; 

potrebbe correre più veloce. Se ricevi un errore di cache o un altro stallo in un calcolo ci sono ancora tre altre catene di dipendenze che non dipendono dallo stallo. Una CPU guasta può eseguirle.

Answer 2

Questi non farebbero alcuna differenza perché stai facendo lo stesso numero di confronti. Ecco un esempio migliore. Invece di:

for (int i=0; i<200; i++) { 
    doStuff(); 
} 

scrittura:

for (int i=0; i<50; i++) { 
    doStuff(); 
    doStuff(); 
    doStuff(); 
    doStuff(); 
} 

Anche allora quasi certamente non avrà importanza, ma ora si sta facendo 50 confronti, invece di 200 (immaginate il confronto è più complesso).

Manuale Lo svolgimento del ciclo in generale è in gran parte un artefatto della storia. È un'altra delle crescenti liste di cose che un buon compilatore farà per te quando è importante. Ad esempio, la maggior parte delle persone non si preoccupa di scrivere x << 1 o x += x anziché x *= 2. Devi solo scrivere x *= 2 e il compilatore lo ottimizzerà per te in base a ciò che è meglio.

Fondamentalmente c'è sempre meno bisogno di indovinare il compilatore.

Answer 3

Lo srotolamento del loop dipende interamente dalla dimensione del problema. Dipende interamente dal fatto che l'algoritmo è in grado di ridurre le dimensioni in gruppi di lavoro più piccoli. Quello che hai fatto sopra non sembra così. Non sono sicuro che una simulazione di monte carlo possa essere srotolata.

I buoni scenari per lo srotolamento del loop farebbero ruotare un'immagine. Dal momento che è possibile ruotare gruppi di lavoro separati. Per farlo funzionare dovresti ridurre il numero di iterazioni.

Answer 4

Indipendentemente dalla previsione del ramo sull'hardware moderno, la maggior parte dei compilatori eseguono comunque lo srotolamento del ciclo.

Vale la pena scoprire quante ottimizzazioni fa il compilatore per te.

Ho trovato Felix von Leitner's presentation molto illuminante sull'argomento. Ti raccomando di leggerlo. Riepilogo: I compilatori moderni sono MOLTO intelligenti, quindi le ottimizzazioni manuali non sono quasi mai efficaci.

Answer 5

Lo srotolamento del ciclo è ancora utile se ci sono molte variabili locali sia dentro che con il ciclo. Riutilizzare quei registri più invece di salvarne uno per l'indice del ciclo.

Nell'esempio, si utilizza una piccola quantità di variabili locali, senza sovrascrivere i registri.

Il confronto (all'estremità del loop) è anche uno svantaggio principale se il confronto è pesante (cioè non- test istruzione), soprattutto se dipende da una funzione esterna.

Lo srotolamento del loop aiuta ad aumentare la consapevolezza della CPU anche per la previsione dei rami, ma questi si verificano comunque.

Answer 6

Per quanto mi risulta, i compilatori moderni già srotolare loop se del caso - un esempio è gcc, se superato i flag di ottimizzazione che il manuale dice lo farà:

Srotolare loop il cui numero di iterazioni può essere determinato al momento della compilazione o dopo l'accesso al ciclo .

Quindi, in pratica è probabile che il compilatore faccia i casi banali per voi. Sta a te quindi assicurarti che il maggior numero possibile dei tuoi loop sia facile per il compilatore per determinare quante iterazioni saranno necessarie.

Answer 7

Lo srotolamento del loop, sia che si svolga manualmente lo srotolamento o lo srotolamento del compilatore, può essere spesso controproducente, in particolare con le CPU x86 più recenti (Core 2, Core i7). Bottom line: confronta il tuo codice con e senza ciclo di svolgimento su qualsiasi CPU hai intenzione di implementare questo codice.

Answer 8

Provare senza saperlo non è il modo per farlo.
Questo tipo richiede un'alta percentuale del tempo complessivo?

Lo svolgimento di tutti gli arresti del ciclo riduce l'overhead del ciclo di incremento/decremento, confronto per la condizione di arresto e salto. Se ciò che stai facendo nel ciclo richiede più cicli di istruzioni rispetto al sovraccarico del loop stesso, non vedrai molti miglioramenti percentuali.

Here's an example of how to get maximum performance.

Answer 9

Loop svolgimento può essere utile nei casi specifici. L'unico guadagno non è saltare alcuni test!

Può ad esempio consentire la sostituzione scalare, l'inserimento efficiente del precaricamento del software ... Sareste sorpresi in realtà quanto possa essere utile (potete ottenere facilmente il 10% di accelerazione sulla maggior parte dei cicli anche con -O3) srotolando in modo aggressivo.

Come è stato detto prima, dipende molto dal ciclo e il compilatore e l'esperimento sono necessari. È difficile stabilire una regola (o l'euristica del compilatore per lo srotolamento sarebbe perfetta)