1.000.000.000 di calcoli per microsecondo?

Question

OK, ho parlato con un amico di compilatori e ottimizzazione dei programmi e ha suggerito che n * 0.5 è più veloce di n/2. Ho detto che i compilatori fare questo tipo di ottimizzazione automatica, così ho scritto un piccolo programma per vedere se ci fosse una differenza tra n/2 e n * 0.5:

Divisione:

#include <stdio.h> 
#include <time.h> 

int main(int argc, const char * argv[]) { 
    int i, m; 
    float n, s; 
    clock_t t; 

    m = 1000000000; 
    t = clock(); 
    for(i = 0; i < m; i++) { 
     n = i/2; 
    } 
    s = (float)(clock() - t)/CLOCKS_PER_SEC; 

    printf("n = i/2: %d calculations took %f seconds (last calculation = %f)\n", m, s, n); 

    return 0; 
} 

Moltiplicazione:

#include <stdio.h> 
#include <time.h> 

int main(int argc, const char * argv[]) { 
    int i, m; 
    float n, s; 
    clock_t t; 

    m = 1000000000; 
    t = clock(); 
    for(i = 0; i < m; i++) { 
     n = i * 0.5; 
    } 
    s = (float)(clock() - t)/CLOCKS_PER_SEC; 

    printf("n = i * 0.5: %d calculations took %f seconds (last calculation = %f)\n", m, s, n); 

    return 0; 
} 

E per entrambe le versioni ho ottenuto avg 0.000002s. quando compilato con clang main.c -O1. E ha detto che ci deve essere qualcosa di sbagliato nella misurazione del tempo. Così ha poi scritto un programma:

#include <cstdio> 
#include <iostream> 
#include <ctime> 

using namespace std; 

int main() 
{ 
    clock_t ts, te; 
    double dT; 

    int i, m; 
    double n, o, p, q, r, s; 
    m = 1000000000; 

    cout << "Independent calculations:\n"; 
    ts = clock(); 
    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1/2.3; 
     o = 22.2/2.3; 
     p = 33.3/2.3; 
     q = 44.4/2.3; 
     r = 55.5/2.3; 
     s = 66.6/2.3; 
    } 

    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Division: %d calculations took %f seconds\n", m, dT); 

    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1 * 0.53; 
     o = 22.2 * 0.53; 
     p = 33.3 * 0.53; 
     q = 44.4 * 0.53; 
     r = 55.5 * 0.53; 
     s = 66.6 * 0.53; 
    } 

    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Multiplication: %d calculations took %f seconds\n", m, dT); 

    cout << "\nDependent calculations:\n"; 
    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1/2.3; 
     o = n/2.3; 
     p = o/2.3; 
     q = p/2.3; 
     r = q/2.3; 
     s = r/2.3; 
    } 


    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Division: %d calculations took %f seconds\n", m, dT); 

    for (i = 0; i < m; i++) 
    { 
     // make it a trivial pure float calculation with no int casting to float 
     n = 11.1 * 0.53; 
     o = n * 0.53; 
     p = o * 0.53; 
     q = p * 0.53; 
     r = q * 0.53; 
     s = r * 0.53; 
    } 


    te = clock(); 
    dT = ((float)(te - ts))/CLOCKS_PER_SEC; // make initial call to get the elapsed time to run the loop 
    ts = clock(); 

    printf("Multiplication: %d calculations took %f seconds\n", m, dT); 

    return 0; 
} 

E per questo ha ottenuto ...

1.869570s 
1.868254s 
25.674016s 
3.497555s 

... in questo ordine.

Così ho eseguito il programma sulla mia macchina compilato con clang++ main.cpp -O1 e ho ottenuto risultati simili come prima: 0.000002 to 0.000011.

Tuttavia, quando ho compilato il programma senza ottimizzazione, ho ottenuto risultati simili a lui al suo primo test. Quindi la mia domanda è: come può una qualsiasi quantità di ottimizzazione rendere il programma quello molto più veloce?

Answer 1

Poiché il codice non fa nulla di diverso in ogni iterazione del ciclo, il compilatore è libero di spostare il codice all'interno del ciclo esterno (il risultato sarà esattamente lo stesso) e rimuovere completamente il ciclo, lasciandovi con quasi 0 run-time, come hai visto.

Answer 2

for (i = 0; i < m; i++) 
{ 
    // make it a trivial pure float calculation with no int casting to float 
    n = 11.1 * 0.53; 
    o = n * 0.53; 
    p = o * 0.53; 
    q = p * 0.53; 
    r = q * 0.53; 
    s = r * 0.53; 
} 

è un ciclo che non fa riferimento i o m e non contiene riferimenti circolari ed è quindi banale per il compilatore per rimuovere l'istruzione loop

Answer 3

Questo è un buon esempio di come il benchmarking un linguaggio ad alto livello è ancora più difficile dell'assemblaggio di benchmarking (che è già abbastanza difficile da avere già ragione). Il compilatore può, e spesso lo farà, interferire con il tuo benchmark.

Il tuo amico ha un punto, una divisione (effettiva divisione, non solo la scrittura / in C) è più lenta di una moltiplicazione. Per i doppi, il rapporto è di circa 4 per la latenza, e la divisione non è pipeline mentre la moltiplicazione è, quindi il rapporto di throughput è molto peggiore: intorno a 20. (questi numeri sono per Haswell, ma sono tipici)

divisione intera è più lento della divisione in virgola mobile, ma l'uso della moltiplicazione in virgola mobile sul numero intero causa due conversioni. Le conversioni non sono male, quindi in totale, la moltiplicazione in virgola mobile è ancora più veloce.

Ma qualsiasi compilatore appropriato trasformerà la divisione in intero di una costante in una moltiplicazione intera e uno shift, e forse alcuni aggiustamenti aggiuntivi (a seconda del divisore e del tipo). La divisione di una potenza di due è ancora più semplice. Per dettagli, vedere Division by Invariant Integers using Multiplication.Come esempio, si consideri

int div2(int i) 
{ 
    return i/2; 
} 

GCC trasforma questo in

mov eax, edi 
shr eax, 31 
add eax, edi 
sar eax 
ret 

Quale seconda del μarch, avrebbe preso 3 o 4 cicli (esclusi flusso di controllo).

D'altra parte,

int div2(int i) 
{ 
    return i * 0.5; 
} 

si trasforma in

cvtsi2sd xmm0, edi 
    mulsd xmm0, QWORD PTR .LC0[rip] 
    cvttsd2si eax, xmm0 
    ret 
.LC0: 
    .long 0 
    .long 1071644672 

che avrebbe preso circa 4 + 5 + 4 = 13 cicli.

Un compilatore è consentito anche per trasformare f/2.0 in f * 0.5 anche senza "ottimizzazioni non sicuri", divisione per una potenza di due è equivalente alla moltiplicazione per il suo inverso. Ciò non vale per i numeri che non sono un potere di due.

Quindi, anche con un benchmark che misurava almeno qualcosa di, probabilmente non avrebbe misurato la cosa giusta. Al fine di misurare la divisione in virgola mobile di latenza vs moltiplicazione, si potrebbe scrivere qualcosa di simile:

.section data 
align 16 
one: dq 1.0, 1.0 
.section text 
_bench1: 
    mov ecx, -10000000 
    movapd xmm0, [one] 
loopone: 
    mulpd xmm0, xmm0 
    mulpd xmm0, xmm0 
    add ecx, 1 
    jnz loopone 
    ret 
_bench2: 
    mov ecx, -10000000 
    movapd xmm0, [one] 
looptwo: 
    divpd xmm0, xmm0 
    divpd xmm0, xmm0 
    add ecx, 1 
    jnz looptwo 
    ret 

chiamata sia un migliaio, avvolto in rdtsc per ottenere il tempo. Prendi il tempo più basso per entrambi. Moltiplicare il tempo in base al rapporto tra l'orologio base e l'orologio turbo. Quindi si dovrebbe avere (approssimativamente) il numero di cicli di entrambi i cicli, dividere per 20000000 per ottenere il numero di cicli per mulpd o divpd. La divisione del tempo richiede dipende dai valori che vengono divisi, quindi non fornisce il risultato più generale.

Potresti anche essere interessato a list of instruction latencies and throughputs.