Puntatore di ottimizzazione micro + senza segno + 1

Question

È difficile credere che il costrutto p[u+1] si verifichi in più punti negli anelli di codice più interni, in modo tale che ottenere la micro ottimizzazione di esso faccia sì ore di differenza in un'operazione che viene eseguita per giorni.

In genere *((p+u)+1) è più efficiente. A volte *(p+(u+1)) è più efficiente. Raramente *((p+1)+u) è la cosa migliore. (Ma solitamente un ottimizzatore può convertire *((p+1)+u) in *((p+u)+1) quando quest'ultimo è migliore, e non può convertire *(p+(u+1)) con nessuno degli altri).

p è un puntatore e u è un non firmato. Nel codice attuale almeno uno di essi (più probabilmente entrambi) sarà già nei registri nel punto in cui viene valutata l'espressione. Questi fatti sono fondamentali al punto della mia domanda.

In 32-bit (prima che il mio progetto lasciasse il supporto per questo) tutti e tre hanno esattamente la stessa semantica e qualsiasi compilatore mezzo decente sceglie semplicemente il meglio dei tre e il programmatore non ha mai bisogno di preoccuparsi.

In questi usi a 64 bit, il programmatore sa che tutti e tre hanno la stessa semantica, ma il compilatore non lo sa. Per quanto il compilatore sa, la decisione su quando estendere u da 32-bit a 64-bit può influire sul risultato.

Qual è il modo più pulito per dire al compilatore che la semantica di tutti e tre è la stessa e il compilatore dovrebbe selezionare il più veloce di essi?

In un Linux a 64-bit compilatore, ho avuto quasi arrivati ​​con p[u+1L] che fa sì che il compilatore per selezionare in modo intelligente tra il genere migliore *((p+u)+1) e talvolta meglio *(p+((long)(u) + 1)). Nel raro caso *(p+(u+1)) era ancora meglio del secondo di quelli, un po 'è perso.

Ovviamente, ciò non va bene in Windows a 64 bit. Ora che abbiamo abbandonato il supporto a 32 bit, forse p[u+1LL] è abbastanza portatile e abbastanza buono. Ma posso fare di meglio?

Si noti che l'utilizzo di std::size_t anziché unsigned per u eliminerebbe l'intero problema, ma crea un problema di prestazioni più ampio nelle vicinanze. Casting u a std::size_t giusto c'è abbastanza buono, e forse il meglio che posso fare. Ma questo è piuttosto prolisso per una soluzione imperfetta.

La semplice codifica (p+1)[u] rende una selezione più probabile che sia ottimale rispetto a p[u+1]. Se il codice fosse meno basato sui modelli e più stabile, potrei impostarli tutti su (p+1)[u] quindi profilo, quindi passare di nuovo a p[u+1]. Ma il modello tende a distruggere quell'approccio (Una singola riga di origine appare in molti posti nel profilo che aggiungono fino a tempi serie, ma non individualmente tempo serio).

I compilatori che dovrebbero essere efficienti per questo sono GCC, ICC e MSVC.

Answer 1

La risposta è inevitabilmente compilatore e target specifico, ma anche se 1ULL è più largo di un puntatore su qualsiasi architettura di destinazione, un buon compilatore dovrebbe ottimizzarlo. Which 2's complement integer operations can be used without zeroing high bits in the inputs, if only the low part of the result is wanted? spiega perché un calcolo più ampio troncato alla larghezza del puntatore fornirà risultati identici come fare il calcolo con la larghezza del puntatore in primo luogo.Questo è il motivo per cui i compilatori possono ottimizzarlo anche su macchine a 32 bit (o x86-64 con l'ABI x32) quando 1ULL porta alla promozione degli operandi + in un tipo a 64 bit. (O su un ABI a 64 bit per alcune architetture in cui lo long long è 128b).

---

1ULLlooks optimal for 64bit, and for 32bit with clang. Non ti importa comunque di 32 bit, ma gcc spreca un'istruzione nello return p[u + 1ULL];. Tutti gli altri casi sono compilati con un singolo carico con indice di indice + 4 + p modalità di indirizzamento. Quindi, a parte l'errore di ottimizzazione di un compilatore, 1ULL sembra buono anche per 32 bit. (Penso che sia improbabile che sia un bug clang e che l'ottimizzazione sia illegale).

int v1ULL(std::uint32_t u) { return p[u + 1ULL]; } 
// ... load u from the stack 
// add  eax, 1 
// mov  eax, DWORD PTR p[0+eax*4] 

anziché

mov  eax, DWORD PTR p[4+eax*4] 

interessante, gcc 5.3 doesn't make this mistake when targeting the x32 ABI (lungo modo con puntatori a 32 bit ed un registro-call ABI simile a SysV AMD64). Utilizza un prefisso della dimensione dell'indirizzo a 32 bit per evitare l'uso del 32b superiore di edi.

Annoyingly, utilizza ancora un prefisso dimensione indirizzo quando è possibile salvare un byte di codice macchina utilizzando un indirizzo effettivo a 64 bit (quando non c'è possibilità di overflow/carry in upper32 generando un indirizzo al di fuori del 4GiB basso). Passare il puntatore per riferimento è un buon esempio:

int x2 (char *&c) { return *c; } 
// mov  eax, DWORD PTR [edi] ; upper32 of rax is zero 
// movsx eax, BYTE PTR [eax] ; could be byte [rax], saving one byte of machine code 

Err, in realtà ho dimenticato. Gli indirizzi a 32 bit potrebbero firmare-estendersi a 64b, non estendersi a zero. Se questo è il caso, potrebbe aver usato anche movsx per la prima istruzione, ma sarebbe costato un byte perché movsx ha un opcode più lungo di mov.

In ogni caso, x32 è ancora una scelta interessante per il codice puntatore-pesante che vuole più registri e un ABI più bello, senza il colpo di cache-miss di puntatori 8B.

---

Il 64bit asm deve azzerare l'upper32 del registro che tiene il parametro (con mov edi,edi), ma che scompare quando inlining. Guardare l'output di Godbolt per piccole funzioni è un modo valido per testarlo.

Se vogliamo essere doppiamente sicuri che il compilatore non si stia sparando al piede e azzeri il upper32 quando dovrebbe sapere che è già zero, potremmo fare delle funzioni di test con un arg passato per riferimento.

int v1ULL(const std::uint32_t &u) { return p[u + 1ULL]; } 
// mov  eax, DWORD PTR [rdi] 
// mov  eax, DWORD PTR p[4+rax*4]