Efficienza su una piattaforma a 64 bit: puntatore vs indicizzazione di array a 32 bit

Question

In una delle sue note chiave, Andrei Alexandrescu, suggerisce che, su una piattaforma a 64 bit, l'utilizzo dell'indicizzazione di array a 32 bit sia più veloce rispetto all'utilizzo del puntatore raw:

Pagina 16: http://www.slideshare.net/andreialexandrescu1/three-optimization-tips-for-c-15708507

Sul suo account di Facebook, è più preciso e dice: "Preferisco serie indicizzazione ai puntatori (questo sembra invertire ogni dieci anni)".

Ho provato molte cose per trovare una differenza, ma non sono riuscito a creare alcun programma che mostri questa differenza. Conoscendo Andrei, non sarei sorpreso che la differenza non sia superiore a qualche percento, ma sarei felice se qualcuno trovasse un simile esempio.

Ecco un test che ho fatto. Scelgo n = 5000, abbastanza grande da ottenere un timing decente e abbastanza piccolo da far sì che tutto si adatti alla cache L1. I loop alcune volte in modo che la frequenza della CPU aumenti.

#include <iostream> 
#include <chrono> 

int main(int argc, const char* argv[]) { 
    const int n{5000}; 
    int* p{new int[n]}; 

    // Warm up the cache 
    for (int i{0}; i < n; i++) { 
    p[i] += 1; 
    } 

    for (int j{0}; j < 5; j++) { 
    { 
     auto start_pointer = std::chrono::high_resolution_clock::now(); 
     for (int* q{p}; q != p + n; ++q) { 
     ++(*q); 
     } 
     auto end_pointer = std::chrono::high_resolution_clock::now(); 
     auto time_pointer = std::chrono::duration_cast<std::chrono::nanoseconds>(
           end_pointer - start_pointer) 
           .count(); 
     std::cout << " Pointer: " << time_pointer << std::endl; 
    } 

    { 
     auto start_pointer = std::chrono::high_resolution_clock::now(); 
     for (int* q{p}; q != p + n; ++q) { 
     ++(*q); 
     } 
     auto end_pointer = std::chrono::high_resolution_clock::now(); 
     auto time_pointer = std::chrono::duration_cast<std::chrono::nanoseconds>(
           end_pointer - start_pointer) 
           .count(); 
     std::cout << " Pointer: " << time_pointer << std::endl; 
    } 

    { 
     auto start_index_32 = std::chrono::high_resolution_clock::now(); 
     for (int i{0}; i < n; i++) { 
     p[i] += 1; 
     } 
     auto end_index_32 = std::chrono::high_resolution_clock::now(); 
     auto time_index_32 = std::chrono::duration_cast<std::chrono::nanoseconds>(
           end_index_32 - start_index_32) 
           .count(); 
     std::cout << "Index 32: " << time_index_32 << std::endl; 
    } 

    { 
     auto start_index_32 = std::chrono::high_resolution_clock::now(); 
     for (int i{0}; i < n; i++) { 
     p[i] += 1; 
     } 
     auto end_index_32 = std::chrono::high_resolution_clock::now(); 
     auto time_index_32 = std::chrono::duration_cast<std::chrono::nanoseconds>(
           end_index_32 - start_index_32) 
           .count(); 
     std::cout << "Index 32: " << time_index_32 << std::endl; 
    } 

    { 
     const std::size_t n_64{n}; 
     auto start_index_64 = std::chrono::high_resolution_clock::now(); 
     for (std::size_t i{0}; i < n_64; i++) { 
     p[i] += 1; 
     } 
     auto end_index_64 = std::chrono::high_resolution_clock::now(); 
     auto time_index_64 = std::chrono::duration_cast<std::chrono::nanoseconds>(
           end_index_64 - start_index_64) 
           .count(); 
     std::cout << "Index 64: " << time_index_64 << std::endl; 
    } 

    { 
     const std::size_t n_64{n}; 
     auto start_index_64 = std::chrono::high_resolution_clock::now(); 
     for (std::size_t i{0}; i < n_64; i++) { 
     p[i] += 1; 
     } 
     auto end_index_64 = std::chrono::high_resolution_clock::now(); 
     auto time_index_64 = std::chrono::duration_cast<std::chrono::nanoseconds>(
           end_index_64 - start_index_64) 
           .count(); 
     std::cout << "Index 64: " << time_index_64 << std::endl; 
    } 
    std::cout << std::endl; 
    } 

    delete[] p; 

    return 0; 
} 

Ecco il tipo di risultato che ottengo sulla mia macchina (core i7). Tutto quello che ricevo è "rumore".

Pointer: 883 
Pointer: 485 
Index 32: 436 
Index 32: 380 
Index 64: 372 
Index 64: 429 

Pointer: 330 
Pointer: 316 
Index 32: 336 
Index 32: 321 
Index 64: 337 
Index 64: 318 

Pointer: 311 
Pointer: 314 
Index 32: 318 
Index 32: 319 
Index 64: 316 
Index 64: 301 

Pointer: 306 
Pointer: 325 
Index 32: 323 
Index 32: 313 
Index 64: 318 
Index 64: 305 

Pointer: 311 
Pointer: 319 
Index 32: 313 
Index 32: 324 
Index 64: 315 
Index 64: 303 

Answer 1

suo (Andrei Alexandrescu) ragionamento sembra essere basata sul fatto che l'utilizzo di un registro per una variabile puntatore è generalmente più difficile per il compilatore in quanto un puntatore potrebbe essere puntando una per i dati globali. Ma non vedo nulla di specifico per l'indicizzazione gamma a 32 bit (la mia lettura, la slitta non era del tutto chiaro se è stato effettivamente riferiva ad array a 32 bit o serie di indicizzazione sistemi a 32-bit)

From the horse's mouth: (sì, è un link al suo account di Facebook :)

Minimizzare gamma scrive

per essere più veloce, il codice dovrebbe ridurre il numero di serie, scrive, e più in generale , scrive tramite puntatori.

Sulle macchine moderne con grandi file di registro e di un ampio registro rinominare l'hardware, si può supporre che le variabili individuali più denominate (numeri, puntatori) finire seduto in registri. Il funzionamento con i registri è veloce e gioca nei punti di forza dell'hardware. Anche quando le dipendenze dei dati - un importante nemico dell'istruzione - il parallelismo - entrano in gioco, le CPU dispongono di hardware speciale dedicato a che gestisce vari schemi di dipendenza. Operando con i registri (cioè le variabili nominate ) si scommette sulla casa. Fallo.

Al contrario, le operazioni di array (e gli accessi indiretti generali) sono meno naturali nell'intera gerarchia del compilatore-processore-cache. Salva per alcuni modelli evidenti, gli accessi agli array non sono registrati. Inoltre, ogni volta che sono coinvolti i puntatori, il compilatore deve assumere che i puntatori potrebbero puntare a dati globali, il che significa che qualsiasi chiamata di funzione potrebbe cambiare arbitrariamente i dati puntati su . E delle operazioni su array, le scritture su array sono il peggiore del pacchetto. Dato che tutto il traffico con memoria è fatto alla granularità della cache-line , scrivere una parola in memoria è essenzialmente una riga di cache seguita da una riga di scrittura cache.Quindi, dato che ad una buona gamma misura legge sono inevitabili in ogni caso, questo pezzo di consulenza si riduce a "evitare di gamma scrive per quanto possibile.

Egli sembra anche suggerire, è generale suggestione piuttosto che è sempre più veloce da usare array di indicizzazione (dallo stesso post):

alcune buone, ma meno noto, le cose da fare per il codice veloce:

Preferisco l statica codice di inchiostrazione e posizione dipendente (al contrario di PIC, codice indipendente dalla posizione).
Preferisci codice a 64 bit e dati a 32 bit.
Preferire l'indicizzazione di array ai puntatori (questo sembra invertire ogni dieci anni).
Preferire i normali schemi di accesso alla memoria. Riduci al minimo il flusso di controllo.
Evitare le dipendenze dei dati.

Answer 2

Il problema con un avviso di basso livello come questo (anche proveniente da Andrei Alexandrescu) è che ignora il fatto che i compilatori ottimizzano.

I compilatori moderni ottimizzano in modo così aggressivo (e, in generale, con successo) che diventa davvero un gioco da mug per cercare di indovinarli. Nel complesso, scrivere codice chiaro e leggibile aiuterà te, i tuoi colleghi e i tuoi compilatori ad analizzare il codice. E credo onestamente che sia il miglior consiglio generale che si possa dare.

Una delle ottimizzazioni note dei moderni compilatori è la conversione tra cicli basati su indici e puntatori. Nel caso particolare del tuo benchmark, con la maggior parte delle impostazioni di ottimizzazione, gcc compilerà sia il loop basato su puntatore che il loop basato su indice a 32 bit sullo stesso output assembler.

In seguito, ho sostituito la roba crono con ++sentry dove sentry è un volatile al fine di ridurre la dimensione del codice. L'uscita di montaggio corrisponde a:

for (int* q{p}; q != p + n; ++q) ++(*q); 
++sentry; 
for (int i{0}; i < n; i++) p[i] += 1; 

compilazione con -O2, questo prodotto il seguente: (%rdi e %ebp erano ancora inizializzato dal ciclo che popolata p)

 movq %rdi, %rdx 
     cmpq %rcx, %rdi 
     je  .L10 
.L16: 
     addl $1, (%rdx) 
     addq $4, %rdx 
     cmpq %rcx, %rdx 
     jne  .L16 
.L10: 
     movl sentry(%rip), %eax 
     movq %rdi, %rdx 
     addl $1, %eax 
     movl %eax, sentry(%rip) 
     testl %ebp, %ebp 
     jle  .L8 
.L14: 
     addl $1, (%rdx) 
     addq $4, %rdx 
     cmpq %rdx, %rsi 
     jne  .L14 
.L8: 

Si può vedere che non c'è differenza tra i loop a .L16 e .L14.

Diverse impostazioni di ottimizzazione producono risultati diversi, ovviamente. Con -O3 i loop sono vettorizzati usando le istruzioni SIMD e il dispositivo di Duff, ma di nuovo sono quasi identici. clang fa questa ottimizzazione a -O2

Nulla di ciò smentisce il fatto che è stato fatto, ovvero che il compilatore potrebbe aver bisogno di lavorare di più per dimostrare che un puntatore che viene scritto non può modificare la memoria arbitraria.

Ma in questo caso, come in molti casi, l'indice di ciclo è una variabile locale e il ciclo è abbastanza semplice da consentire al compilatore di analizzarlo completamente, consentendo così la riduzione della forza, lo srotolamento e la vettorizzazione; se la variabile di controllo è un puntatore o un indice è quindi irrilevante.

---

Un esempio più interessante (possibilmente) è un ciclo su due array in cui gli elementi di base sono di dimensioni diverse. Date le seguenti due funzioni:

void d2f_ptr(float* out, const double* in, int n) { 
    for (auto lim = out + n; out < lim;) *out++ = *in++; 
} 
void d2f_idx(float out[], const double in[], int n) { 
    for (int i = 0; i < n; ++i) out[i] = in[i]; 
} 

gcc (v5.3.0, -O2) non produrre diversi loop e loop indice in base è un'istruzione corta:

d2f_ptr(float*, double const*, int): d2f_idx(float*, double const*, int): 
     movslq %edx, %rdx      xorl %eax, %eax 
     leaq (%rdi,%rdx,4), %rax    testl %edx, %edx 
     cmpq %rax, %rdi      jle  .L16 
     jnb  .L11 
.L15:         .L20: 
     addq $4, %rdi      pxor %xmm0, %xmm0 
     addq $8, %rsi      cvtsd2ss (%rsi,%rax,8), %xmm0 
     pxor %xmm0, %xmm0     movss %xmm0, (%rdi,%rax,4) 
     cvtsd2ss -8(%rsi), %xmm0    addq $1, %rax 
     movss %xmm0, -4(%rdi) 
     cmpq %rdi, %rax      cmpl %eax, %edx 
     ja  .L15       jg  .L20 
.L11:         .L16: 
     ret          ret 

Ma cambiare il double e float agli oggetti le cui dimensioni non consentono più l'uso della modalità di indirizzamento indicizzato del chip Intel e il compilatore converte nuovamente il codice basato su indice in una variante basata su puntatore.

Qui il codice è essenzialmente la stessa di prima, ma il doppio è stato riempito di 48 byte:

struct Big { double val; char padding[40]; }; 
struct Small { 
    float val; 
    Small& operator=(const Big& other) { 
    val = other.val; 
    return *this; 
    } 
}; 

d2f_ptr(Small*, Big const*, int):  d2f_idx(Small*, Big const*, int): 
     movslq %edx, %rdx      testl %edx, %edx 
     leaq (%rdi,%rdx,4), %rax    jle  .L26 
     cmpq %rax, %rdi      leal -1(%rdx), %eax 
     jnb  .L21       leaq 4(%rdi,%rax,4), %rax 
.L25:         .L29: 
     addq $48, %rsi      pxor %xmm0, %xmm0 
     addq $4, %rdi      addq $4, %rdi 
     pxor %xmm0, %xmm0     cvtsd2ss (%rsi), %xmm0 
     cvtsd2ss -48(%rsi), %xmm0    addq $48, %rsi 
     movss %xmm0, -4(%rdi)     movss %xmm0, -4(%rdi) 
     cmpq %rdi, %rax      cmpq %rax, %rdi 
     ja  .L25       jne  .L29 
.L21:         .L26: 
     ret          ret 

---

'forse opportuno aggiungere che per compilatori, non è necessariamente più difficile da analizzare quale oggetto modificherà una particolare scrittura del puntatore. [Edited:. C'era una citazione da Alexandrescu qui, ma non è stato così rilevanti come ho pensato, così ho rimosso lasciando questa sezione per essere soprattutto un uomo di paglia]

Infatti, se un puntatore è solo assegnato direttamente a una volta, e tutte le altre modifiche sono attraverso operazioni di incremento e decremento (incluso += e -=), quindi il compilatore è totalmente nei suoi diritti per assumere che il puntatore punti sempre all'interno dello stesso oggetto. Se alcune modifiche additive del puntatore dovessero subire un overshoot in qualche altro oggetto, questo sarebbe Undefined Behavior e il compilatore può scartare questa possibilità. È abbastanza facile tenere traccia delle operazioni di assegnazione e inc/dec in un diagramma di flusso, quindi nei casi in cui il puntatore potrebbe essere stato sostituito con un'espressione dell'indice, è abbastanza possibile che un compilatore lo calcoli e sappia quindi che altri oggetti non sono essere casualmente mutato scrivendo attraverso il puntatore.

Answer 3

Non esattamente una risposta, ma troppo complesso per un commento:

Il test è un test molto limitato di aritmetica dei puntatori vs serie indicizzazione; nei casi più semplici, con l'ottimizzazione impostata su , ogni compilatore vale la pena saltarlo e produrre lo stesso assembly per entrambi. Quando la variabile index non viene utilizzata in altro modo, il compilatore è perfettamente libero di passare all'aritmetica del puntatore nell'assembly, ed è ugualmente in grado di commutare l'aritmetica del puntatore di nuovo sull'accesso dell'array se lo desidera.

Il miglior esempio che riesco a ottenere è di qualche anno fa (e probabilmente non è coerente dal compilatore al compilatore, dall'architettura all'architettura, ecc.). Stavo giocando intorno con (a fini di apprendimento) due versioni di codice che, in fondo pari ad un'operazione di copia serie:

for (unsigned i = 0; i < copycnt; ++i) { 
    x[i] = y[i]; 
} 

vs.

while (copycnt--) { 
    *x++ = *y++; 
} 

Sto indovinando c'era qualche fattore di complicazione (o ottimizzazioni del compilatore sono cambiate, dal momento che l'ultima volta ho provato qualcosa di simile ad alta ottimizzazione è compilato per la stessa assemblea), ma anche se il compilatore potrebbe banalmente convertire il primo caso al secondo (e in teoria salvare un registro, evitare il carico di offset e le istruzioni del negozio a favore del carico diretto e delle istruzioni del negozio, utilizzare uno testl per 0 invece di uno cmpl di due valori, per il piccolo costo dell'aggiunta di un'istruzione di decremento), il compilatore invece ha scelto di compilare il codice che sarebbe approssimato approssimativamente da:

const ptrdiff_t diff = y - x; 
decltype(*x) *const end = x + copycnt; 
while (x < end) { 
    *x = *(x + diff); 
    ++x; 
} 

Probabilmente è superiore a una delle versioni "normali" del codice se si conta il numero di registri necessari nel ciclo, il numero di istruzioni nel ciclo (presupponendo che il carico a offset del registro fisso sia un'istruzione combinata come è su x86 macchine, piuttosto che add quindi carico diretto), ecc., e il compilatore sicuramente l'ha pensato, dal momento che ha scelto questa versione con aritmetica puntatore semplice (che qualsiasi compilatore potrebbe fare qui).

Ma quando ho compilato il codice l'aritmetica dei puntatori semplice, il compilatore non riusciva a capire il rapporto (probabilmente a causa di qualche fattore di complicazione non presente in questa versione semplificata, lo so né x, y o copycnt è stato utilizzato ancora una volta, in modo da non si trattava di preservare i valori originali), e compilato in modo più o meno esattamente ciò che gli avevo dato, due indicatori, incrementato indipendentemente.

La mia teoria è che l'uso di un indice ha dato al contesto del compilatore quello che stavo facendo; non erano due indicatori indipendenti, erano due "array" accessibili tramite un indice comune e sapeva come migliorare il codice compilato per quel modello. L'aritmetica del puntatore era "fai quello che dico" senza dare il contesto per "cosa sto cercando di fare" e il compilatore non riusciva a capirlo, quindi non l'ha ottimizzato.

In ogni caso, ovviamente solo aneddotico, ma immagino che l'esempio sia rappresentativo delle possibilità più complesse; l'indicizzazione dell'array fornisce al compilatore maggiori informazioni sulla "logica superiore" di ciò che si sta facendo, dove l'aritmetica del puntatore dice cosa fare ma non perché è in esecuzione, quindi il compilatore ha un tempo di ottimizzazione più difficile, che potrebbe spiegare la raccomandazione. Spero che sia d'aiuto.

Answer 4

Ho scritto una mail a Andrei Alexandrescu e lui è stato così gentile da rispondere. Ecco la sua spiegazione:

"Affinché l'accelerazione sia visibile, è necessario sfruttare la capacità dell'ALU di eseguire due operazioni a 32 bit o un'operazione a 64 bit in un ciclo. Non tutti i benchmark mostreranno un accelerare."

Capisco che "le istruzioni SIMD elaborano più dati per ciclo con dati a 32 bit di dati a 64 bit". Devo ancora trovare un punto di riferimento (che non contenga alcun array di numeri interi) dove faccia la differenza. Ma presumo che sarà difficile. Andrei lavorava per Facebook dove valeva la pena ottenere ogni singola percentuale.

Answer 5

Questo tipo di ottimizzazione è solo a livello di metallo e si consiglia di ignorarli. Mi concentrerei maggiormente su altre cose che effettivamente introducono il rumore ai test.

[Numeri]

1. assegnazione puntatore è fatto con ++(*q), mentre per tipi integrali suo più veloce di fare (*q)++, ma in ogni caso si dovrebbe essere coerente con le prove di Int32/Int64 e fare *q+=1.
2. test puntatore calcolare ogni volta nel ciclo il puntatore finale, si dovrebbe farlo una volta int * ep{p+n} e verificare contro quello.
3. Nei test integer non è necessario utilizzare < ma != per la valutazione della terminazione.
4. L'esecuzione solo cinque volte non darà abbastanza schemi.
5. È necessario impostare CPU affinità
6. Si dovrebbe fare più loop e rappresentano solo l'ultima
7. Si dovrebbe avere un sistema in cui il compilatore è stato compilato per il metallo
8. Non si dovrebbe "scaldare la cache modo in cui lo fai "
9. Dovresti rendere casuale l'input.

Ho modificato il codice e lo si può recuperare da here.

Si dovrebbe compilare con:

g++ -O3 -march=native --std=c++11 -o intvsptr

e lanciare con

taskset 0x00000001 ./intvsptr

e poi si dovrebbe ottenere risultati coerenti.

Pointer: 4396 Pointer: 4397 Index 32: 4395 Index 32: 4394 Index 64: 4394 Indice 64: 4395

Pointer: 4395 Pointer: 4397 Index 32: 4397 Index 32: 4395 Index 64: 4393 Index 64: 4396

Pointer: 4395 Pointer: 4397 Index 32: Indice 4396 32: 4394 Index 64: 4394 Indice 64: 4396

Pointer: 4396 Pointer: 4397 Index 32: 4397 Index 32: 4395 indice 64: 4394 Indice 64: 4395

Pointer: 4395 Pointer: 7698 Index 32: 4471 Index 32: 4422 Index 64: 4425 Indice 64: 4407

Pointer: 4399 Pointer: 4416 Index 32: 4394 Index 32: 4393 Indice 64: 4399 Indice 64: 4412

precisione di questo test dovrebbe essere di ultima cifra, ma normalmente si dovrebbe fare un'analisi approfondita stat.

ho incollato le ultime corse di un'esecuzione, ma dopo aver fatto multipla, penso che sia giusto dire quanto questo microbenchmark permette che aritmetica dei puntatori è più veloce o nel peggiore dei casi solo un po 'più lento.

In ogni caso, è possibile ignorare questo tipo di punte che possono aver importato secoli fa, ma non con i compilatori attuali.