prestazioni di spezzarsi un loop in due cicli

Question

Good Day,

Si supponga di avere un semplice ciclo for come qui di seguito ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
    //statement 2 
} 

Si supponga che la dichiarazione dichiarazione 1 e 2 erano O (1). Oltre al piccolo overhead di "avviare" un altro ciclo, si potrebbe abbattere quello per il loop in due cicli (non annidati, ma sequenziali) altrettanto veloci? Per esempio ...

for(int i=0;i<10;i++) 
{ 
    //statement 1 
} 
for(int i=0;i<10;i++) 
{ 
    //statement 2 
} 

Perché faccio una domanda così sciocca è che ho un sistema di rilevamento delle collisioni (CDS) che deve scorrere tutti gli oggetti. Voglio "compartimenti stagni" la funzionalità del mio sistema CDS così posso semplicemente chiamare

cds.update(objectlist); 

invece di dover rompere il mio sistema cd up. (Non preoccuparti troppo della mia implementazione del CDS ... Penso di sapere cosa sto facendo, semplicemente non so come spiegarlo, quello che ho davvero bisogno di sapere è se prendo un enorme successo in termini di prestazioni per il looping attraverso tutti miei oggetti nuovamente.

Answer 1

Dipende dalla vostra applicazione.

possibili svantaggi (di frazionamento):

• i dati non rientra nella cache dei dati L1, quindi si carica una volta per il primo ciclo e ricaricarlo per il secondo ciclo

possibili guadagni (di frazionamento):

• vostro loop cont ains molte variabili, la suddivisione aiuta a ridurre la pressione di registro/stack e l'ottimizzatore lo trasforma in un codice macchina migliore
• le funzioni si utilizza cestino la cache di istruzioni L1 in modo che la cache viene caricata su ogni iterazione, mentre dividendo si gestisce in caricarlo una volta (solo) alla prima iterazione di ogni ciclo

Questi elenchi non sono certamente completo, ma già si può senso che c'è una tensione tra codice e dati. Quindi è difficile per noi prendere un'ipotesi educata/selvaggia quando non conosciamo nessuno dei due.

In dubbio: profilo. Utilizzare callgrind, controllare i caching mancati in ogni caso, controllare il numero di istruzioni eseguite. Misura il tempo trascorso.

Answer 2

quanto riguarda il big-o complessità è interessato, questo non fa differenza se 1 loop è O (n), allora lo è la soluzione 2 loop.
come per quanto riguarda la micro-ottimizzazione, è difficile dire che il costo di un ciclo è piuttosto piccolo, non sappiamo quale sia il costo di accesso ai tuoi oggetti (se sono in un vettore, allora dovrebbe essere anche piuttosto piccolo) ma c'è molto da considerare per dare una risposta utile

Answer 3

Hai ragione nel notare che ci sarà un sovraccarico delle prestazioni creando un secondo ciclo. Pertanto, non può essere "ugualmente veloce"; come questo overhead, mentre piccolo, è ancora in testa.

Non cercherò di parlare in modo intelligente di come dovrebbero essere costruiti i sistemi di collisione, ma se stai cercando di ottimizzare le prestazioni è meglio evitare di costruire strutture di controllo inutili se riesci a gestirle senza tirarti i capelli.

Ricorda che l'ottimizzazione prematura è una delle cose peggiori che puoi fare. Preoccupati dell'ottimizzazione quando hai un problema di prestazioni, secondo me.

Answer 4

In termini di complessità algoritmica, la suddivisione dei loop non fa differenza.

In termini di suddivisione prestazioni reali i passanti potrebbero migliorare le prestazioni, peggiorare le prestazioni o non fa differenza - dipende dal sistema operativo, hardware e - ovviamente - quello statement 1 e statement 2 sono.

Answer 5

Con due anelli si pagheranno per:

• aumentato le dimensioni del codice generato
• 2x come molti ramo predice
• seconda che il layout dei dati della dichiarazione 1 e 2 sono si potrebbe essere ricaricando i dati nella cache.

L'ultimo punto potrebbe avere un impatto enorme in entrambe le direzioni. Dovresti misurare come con qualsiasi ottimizzazione perf.

Answer 6

Come notato, la complessità rimane.

Ma nel mondo reale, è impossibile per noi prevedere quale versione è più veloce. I seguenti sono i fattori che giocano un ruolo, quelle enormi:

• caching dei dati
• istruzioni di caching
• esecuzione speculativa
• Branch previsione
• obiettivo Branch tampona
• Numero di registri disponibili sulla CPU
• Dimensioni cache

(nota: sopra tutti loro, c'è la spada di Damocle di errata interpretazione; tutti sono wikipedizable e googlable)

Soprattutto l'ultimo fattore rende talvolta impossibile compilare l'unico codice vero per il codice le cui prestazioni si basano su dimensioni della cache specifiche. Alcune applicazioni girano più velocemente sulla CPU con enormi cache, mentre funzionano più lentamente su piccole cache, e per alcune altre applicazioni sarà il contrario.

Solutions:

• Lasciate che il vostro compilatore fare il lavoro del ciclo di trasformazione. I moderni g ++ sono abbastanza buoni in quella disciplina. Un'altra disciplina che g ++ è brava è la vettorizzazione automatica. Siate consapevoli del fatto che i compilatori conoscono meglio l'architettura del computer di quasi tutte le persone.
• Spedire file binari diversi e un dispatcher.
• Usa cache-oblivious data structures/layouts and algorithms che si adattano alla cache di destinazione.

È sempre una buona idea cercare software che si adatti all'obiettivo, idealmente senza sacrificare la qualità del codice. E prima di eseguire l'ottimizzazione manuale, microscopica o macroscopica, misurare le piste del mondo reale, quindi e solo allora ottimizzare.

Letteratura: * Agner Fog's Guides * Intel's Guides