Perché GCC utilizza la moltiplicazione per un numero strano nell’implementazione della divisione integer?

Ho letto delle operazioni div e mul assembly e ho deciso di vederle in azione scrivendo un semplice programma in C:

File division.c

 #include  #include  int main() { size_t i = 9; size_t j = i / 5; printf("%zu\n",j); return 0; } 

E quindi generare codice linguaggio assembly con:

 gcc -S division.c -O0 -masm=intel 

Ma guardando il file division.s generato, non contiene alcuna operazione div! Invece, fa un qualche tipo di magia nera con lo spostamento dei bit e numeri magici. Ecco uno snippet di codice che calcola i/5 :

 mov rax, QWORD PTR [rbp-16] ; Move i (=9) to RAX movabs rdx, -3689348814741910323 ; Move some magic number to RDX (?) mul rdx ; Multiply 9 by magic number mov rax, rdx ; Take only the upper 64 bits of the result shr rax, 2 ; Shift these bits 2 places to the right (?) mov QWORD PTR [rbp-8], rax ; Magically, RAX contains 9/5=1 now, ; so we can assign it to j 

Cosa sta succedendo qui? Perché GCC non usa affatto div? Come genera questo numero magico e perché tutto funziona?

La divisione in interi è una delle operazioni aritmetiche più lente che è ansible eseguire su un processore moderno, con latenza fino a dozzine di cicli e ctriggers velocità effettiva. (Per x86, consultare le tabelle di istruzioni di Agner Fog e la guida microarch ).

Se si conosce il divisore in anticipo, è ansible evitare la divisione sostituendola con una serie di altre operazioni (moltiplicazioni, aggiunte e turni) che hanno l’effetto equivalente. Anche se sono necessarie diverse operazioni, spesso è ancora molto più veloce della divisione intera stessa.

Implementare l’operatore C / questo modo invece che con una sequenza div coinvolge div è solo il modo predefinito di GCC di eseguire una divisione per costanti. Non richiede l’ottimizzazione delle operazioni e non cambia nulla nemmeno per il debug. (Usando -Os per le piccole dimensioni del codice si ottiene GCC per usare div , però.) Usare un inverso moltiplicativo invece di una divisione è come usare lea invece di mul e add

Di conseguenza, si tende a vedere div o idiv nell’output solo se il divisore non è noto in fase di compilazione.

Per informazioni su come il compilatore genera queste sequenze, oltre al codice per consentirgli di generarle da sé (quasi certamente non necessario a meno che non si stia lavorando con un compilatore braindead ), vedere libdivide .

Dividere per 5 equivale a moltiplicare 1/5, che è di nuovo uguale moltiplicando per 4/5 e spostando a destra 2 bit. Il valore in questione è CCCCCCCCCCCCD in esadecimale, che è la rappresentazione binaria di 4/5 se messo dopo un punto esadecimale (cioè il binario per quattro quinti è 0.110011001100 ricorrente – vedi sotto per il perché). Penso che tu possa prenderlo da qui! Potresti voler controllare l’ aritmetica in virgola fissa (sebbene si noti che è arrotondata a un intero alla fine.

Per quanto riguarda il motivo, la moltiplicazione è più veloce della divisione e quando il divisore è riparato, questo è un percorso più veloce.

Vedi Moltiplicazione reciproca, un tutorial per una descrizione dettagliata di come funziona, spiegando in termini di punto fisso. Mostra come l’algoritmo per trovare il lavoro reciproco e come gestire la divisione e il modulo firmati.

Consideriamo per un minuto perché 0.CCCCCCCC... (hex) o 0.110011001100... binary è 4/5. Dividi la rappresentazione binaria per 4 (sposta a destra 2 punti), e otterremo 0.001100110011... che per ispezione banale può essere aggiunto l’originale per ottenere 0.111111111111... , che è ovviamente uguale a 1, allo stesso modo 0.9999999... in decimale è uguale a uno. Pertanto, sappiamo che x + x/4 = 1 , quindi 5x/4 = 1 , x=4/5 . Questo viene quindi rappresentato come CCCCCCCCCCCCD in esadecimale per arrotondamento (poiché la cifra binaria oltre l’ultimo presente sarebbe 1 ).

In generale, la moltiplicazione è molto più veloce della divisione. Quindi, se possiamo farla franca moltiplicando per il reciproco, invece, possiamo accelerare significativamente la divisione di una costante

Una ruga è che non possiamo rappresentare esattamente il reciproco (a meno che la divisione non sia dovuta a una potenza di due, ma in questo caso di solito possiamo semplicemente convertire la divisione in un bit shift). Quindi per garantire risposte corrette dobbiamo fare attenzione che l’errore nel nostro reciproco non causi errori nel nostro risultato finale.

-3689348814741910323 è 0xCCCCCCCCCCCCCCCD che è un valore di poco più di 4/5 express in 0,64 punti fissi.

Quando moltiplichiamo un intero a 64 bit di un numero a 0.64 punti fissi otteniamo un risultato 64.64. Tronchiamo il valore a un numero intero a 64 bit (arrotondandolo effettivamente verso lo zero) e quindi eseguiamo un ulteriore spostamento che divide per quattro e di nuovo troncando Osservando il livello di bit è chiaro che possiamo trattare entrambi i troncamenti come un singolo troncamento.

Questo ci fornisce chiaramente un’approssimazione della divisione per 5 ma ci dà una risposta esatta arrotondata correttamente verso lo zero?

Per ottenere una risposta esatta, l’errore deve essere abbastanza piccolo da non spingere la risposta oltre un limite di arrotondamento.

La risposta esatta a una divisione per 5 avrà sempre una parte frazionaria di 0, 1/5, 2/5, 3/5 o 4/5. Pertanto un errore positivo inferiore a 1/5 nel risultato moltiplicato e spostato non sposterà mai il risultato su un limite di arrotondamento.

L’errore nella nostra costante è (1/5) * 2 -64 . Il valore di i è inferiore a 2 64, quindi l’errore dopo la moltiplicazione è inferiore a 1/5. Dopo la divisione per 4 l’errore è inferiore a (1/5) * 2 -2 .

(1/5) * 2 -2 <1/5 quindi la risposta sarà sempre uguale a fare una divisione esatta e arrotondamento verso lo zero.


Sfortunatamente questo non funziona per tutti i divisori.

Se proviamo a rappresentare 4/7 come numero di punto fisso 0,64 con arrotondamento a partire da zero, finiamo con un errore di (6/7) * 2 -64 . Dopo aver moltiplicato per un valore i di poco meno di 2 64 finiamo con un errore appena sotto 6/7 e dopo aver diviso per quattro finiamo con un errore di appena 1.5 / 7 che è maggiore di 1/7.

Quindi per implementare correttamente la divisione di 7 dobbiamo moltiplicare per un numero di punto fisso di 0,65. Possiamo implementarlo moltiplicando per i 64 bit inferiori del nostro numero di punti fissi, quindi aggiungendo il numero originale (questo potrebbe traboccare nel carry bit) quindi fare una rotazione attraverso carry.

Qui è il collegamento a un documento di un algoritmo che produce i valori e il codice che vedo con Visual Studio (nella maggior parte dei casi) e che presumo sia ancora usato in GCC per la divisione di un intero variabile di un numero intero costante.

http://gmplib.org/~tege/divcnst-pldi94.pdf

Nell’articolo, uword ha N bit, una udword ha 2N bit, n = numeratore, d = denominatore = divisore, ℓ è inizialmente impostato su ceil (log2 (d)), shpre è pre-shift (usato prima di moltiplicare) = e = numero di bit zero finali in d, shpost è post-shift (usato dopo moltiplicare), prec è precisione = N – e = N – shpre. L’objective è ottimizzare il calcolo di n / d utilizzando un pre-shift, un multiplo e un post-shift.

Scorri verso il basso fino alla figura 6.2, che definisce come viene generato un moltiplicatore di udword (la dimensione massima è N + 1 bit), ma non spiega chiaramente il processo. Spiegherò questo sotto.

La figura 4.2 e la figura 6.2 mostrano come il moltiplicatore può essere ridotto a un moltiplicatore N o inferiore per la maggior parte dei divisori. L’equazione 4.5 spiega come è stata derivata la formula usata per trattare i moltiplicatori N + 1 bit nelle figure 4.1 e 4.2.

Tornando alla Figura 6.2. Il numeratore può essere maggiore di un udword solo quando divisore> 2 ^ (N-1) (quando ℓ == N), in questo caso la sostituzione ottimizzata per n / d è un confronto (se n> = d, q = 1 , altrimenti q = 0), quindi non viene generato alcun moltiplicatore. I valori iniziali di mlow e mhigh saranno N + 1 bit e due divisioni udword / uword possono essere utilizzate per produrre ciascun valore N + 1 bit (mlow o mhigh). Utilizzando X86 in modalità 64 bit come esempio:

 ; upper 8 bytes of numerator = 2^(ℓ) = (upper part of 2^(N+ℓ)) ; lower 8 bytes of numerator for mlow = 0 ; lower 8 bytes of numerator for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e) numerator dq 2 dup(?) ;16 byte numerator divisor dq 1 dup(?) ; 8 byte divisor ; ... mov rcx,divisor mov rdx,0 mov rax,numerator+8 ;upper 8 bytes of numerator div rcx ;after div, rax == 1 mov rax,numerator ;lower 8 bytes of numerator div rcx mov rdx,1 ;rdx:rax = N+1 bit value = 65 bit value 

Puoi testarlo con GCC. Hai già visto come viene gestito j = i / 5. Dai un’occhiata a come viene gestito j = i / 7 (che dovrebbe essere il caso moltiplicatore N + 1 bit).