Calcoli in virgola mobile vs integer su hardware moderno

Question

Sto eseguendo alcune operazioni critiche sulle prestazioni in C++ e attualmente utilizziamo calcoli integer per problemi che sono intrinsecamente a virgola mobile perché "più veloce". Questo causa un sacco di fastidiosi problemi e aggiunge un sacco di codice fastidioso.

Ora, mi ricordo di aver letto su come i calcoli in virgola mobile sono stati così lenti approssimativamente circa i 386 giorni, dove credo (IIRC) che ci fosse un co-Processore opzionale. Ma sicuramente al giorno d'oggi con CPU esponenzialmente più complesse e potenti non fa differenza in "velocità" se si eseguono calcoli in virgola mobile o interi? Soprattutto perché il tempo di calcolo effettivo è minuscolo rispetto a qualcosa di simile a causare uno stallo della pipeline o il recupero di qualcosa dalla memoria principale?

So che la risposta corretta è quella di eseguire il benchmark sull'hardware di destinazione, quale sarebbe un buon modo per testarlo? Ho scritto due piccoli programmi C++ e ho confrontato il loro tempo di esecuzione con "time" su Linux, ma il tempo di esecuzione effettivo è troppo variabile (non aiuta a funzionare su un server virtuale). A parte passare tutto il giorno a gestire centinaia di benchmark, fare grafici, ecc. C'è qualcosa che posso fare per ottenere un ragionevole test della velocità relativa? Qualche idea o pensiero? Ho completamente torto?

I programmi che ho usato come segue, essi non sono identici con qualsiasi mezzo:

#include <iostream> 
#include <cmath> 
#include <cstdlib> 
#include <time.h> 

int main(int argc, char** argv) 
{ 
    int accum = 0; 

    srand(time(NULL)); 

    for(unsigned int i = 0; i < 100000000; ++i) 
    { 
     accum += rand() % 365; 
    } 
    std::cout << accum << std::endl; 

    return 0; 
} 

Programma 2:

#include <iostream> 
#include <cmath> 
#include <cstdlib> 
#include <time.h> 

int main(int argc, char** argv) 
{ 

    float accum = 0; 
    srand(time(NULL)); 

    for(unsigned int i = 0; i < 100000000; ++i) 
    { 
     accum += (float)(rand() % 365); 
    } 
    std::cout << accum << std::endl; 

    return 0; 
} 

Grazie in anticipo!

Modifica: la piattaforma a cui tengo è regolare x86 o x86-64 in esecuzione su computer desktop Linux e Windows.

Modifica 2 (incollato da un commento di seguito): Attualmente disponiamo di una base di codice estesa. In realtà mi sono imbattuto nella generalizzazione secondo la quale "non dobbiamo usare float dato che il calcolo degli interi è più veloce" - e sto cercando un modo (se questo è vero) per smentire questa ipotesi generalizzata. Mi rendo conto che sarebbe impossibile prevedere il risultato esatto per noi, a corto di fare tutto il lavoro e di profilarlo in seguito.

In ogni caso, grazie per tutte le vostre eccellenti risposte e aiuto. Sentiti libero di aggiungere altro :).

Answer 1

Ahimè, posso solo darvi un "dipende" risposta ...

Dalla mia esperienza, ci sono molte, molte variabili da prestazioni ... soprattutto tra interi & matematica in virgola mobile. Varia fortemente da processore a processore (anche all'interno della stessa famiglia come x86) perché i processori diversi hanno lunghezze "pipeline" differenti. Inoltre, alcune operazioni sono in genere molto semplici (come l'aggiunta) e hanno un percorso accelerato attraverso il processore, mentre altre (come la divisione) richiedono molto, molto più tempo.

L'altra grande variabile è dove risiedono i dati. Se hai solo pochi valori da aggiungere, tutti i dati possono risiedere nella cache, dove possono essere rapidamente inviati alla CPU. Un'operazione in virgola mobile molto, molto lenta che ha già i dati nella cache sarà molte volte più veloce di un'operazione intera in cui un intero deve essere copiato dalla memoria di sistema.

Suppongo che tu stia facendo questa domanda perché stai lavorando su un'applicazione performante. Se stai sviluppando per l'architettura x86 e hai bisogno di prestazioni extra, potresti voler utilizzare le estensioni SSE. Ciò può velocizzare enormemente l'aritmetica in virgola mobile a precisione singola, poiché la stessa operazione può essere eseguita su più dati contemporaneamente, inoltre vi è un banco * separato di registri per le operazioni SSE. (Ho notato che nel tuo secondo esempio hai usato "float" invece di "double", facendomi pensare che stai usando una matematica a precisione singola).

* Nota: l'utilizzo delle vecchie istruzioni MMX rallenterebbe effettivamente i programmi, poiché quelle vecchie istruzioni utilizzavano effettivamente gli stessi registri della FPU, rendendo impossibile l'uso simultaneo di FPU e MMX.

Answer 2

A meno che non si stia scrivendo il codice che verrà chiamato milioni di volte al secondo (ad esempio, disegnando una linea sullo schermo in un'applicazione grafica), l'aritmetico intero vs virgola mobile è raramente il collo di bottiglia.

Il solito primo passo verso le domande sull'efficienza consiste nel profilare il codice per vedere dove viene effettivamente speso il tempo di esecuzione. Il comando linux per questo è gprof.

Edit:

Anche se suppongo si può sempre implementare l'algoritmo di disegno line utilizzando numeri interi e in virgola mobile i numeri, chiamare un gran numero di volte e vedere se fa la differenza:

http://en.wikipedia.org/wiki/Bresenham's_algorithm

Answer 3

L'aggiunta è molto più veloce di rand, quindi il tuo programma è (soprattutto) inutile.

È necessario identificare gli hotspot delle prestazioni e modificare in modo incrementale il programma.Sembra che tu abbia problemi con il tuo ambiente di sviluppo che dovrà essere risolto prima. È impossibile eseguire il programma sul PC per un piccolo problema?

In genere, il tentativo di processi FP con aritmetica intera è una ricetta per lenta.

Answer 4

Basato su quel "qualcosa che ho sentito" così affidabile, ai vecchi tempi, il calcolo di interi era da 20 a 50 volte più veloce di quello in virgola mobile, e in questi giorni è due volte più veloce.

Answer 5

Ho eseguito un test che ha appena aggiunto 1 al numero anziché a rand(). I risultati (su un x86-64) sono stati:

• breve: 4.260s
• int: 4.020s
• lunga lunga: 3.350s
• float: 7.330s
• doppia: 7.210s

Answer 6

È probabile che vi sia una differenza significativa nella velocità del mondo reale tra la matematica a virgola fissa e quella a virgola mobile, ma il throughput teorico dei casi migliori tra ALU e FPU è completamente irrilevante. Invece, il numero di registri interi e virgola mobile (registri reali, non nomi dei registri) sulla tua architettura che non sono altrimenti utilizzati dal tuo calcolo (ad esempio per il controllo del ciclo), il numero di elementi di ogni tipo che si adattano a una linea della cache , ottimizzazioni possibili considerando la semantica diversa per la matematica a virgola mobile rispetto a quella a virgola mobile - questi effetti domineranno. Le dipendenze dei dati dell'algoritmo svolgono qui un ruolo significativo, in modo che nessun confronto generale preveda il divario di prestazioni sul tuo problema.Ad esempio, l'aggiunta di interi è commutativa, quindi se il compilatore vede un ciclo come quello che hai usato per un benchmark (supponendo che i dati casuali siano stati preparati in anticipo in modo da non oscurare i risultati), può srotolare il ciclo e calcolare somme parziali senza dipendenze, quindi aggiungerle quando termina il ciclo. Ma con il floating point, il compilatore deve eseguire le operazioni nello stesso ordine richiesto (ci sono dei punti di sequenza, quindi il compilatore deve garantire lo stesso risultato, il che non consente il riordino), quindi c'è una forte dipendenza di ogni aggiunta su il risultato del precedente.

È probabile che sia possibile montare più operandi interi nella cache alla volta. Quindi la versione a virgola fissa potrebbe sovraperformare la versione float di un ordine di grandezza anche su una macchina in cui la FPU ha un throughput teoricamente più elevato.

Answer 7

Per esempio (i numeri minori sono più veloci),

a 64 bit Intel Xeon X5550 @ 2.67GHz, gcc 4.1.2 -O3

short add/sub: 1.005460 [0] 
short mul/div: 3.926543 [0] 
long add/sub: 0.000000 [0] 
long mul/div: 7.378581 [0] 
long long add/sub: 0.000000 [0] 
long long mul/div: 7.378593 [0] 
float add/sub: 0.993583 [0] 
float mul/div: 1.821565 [0] 
double add/sub: 0.993884 [0] 
double mul/div: 1.988664 [0] 

32-bit Dual Core AMD Opteron (tm) Processor 265 @ 1.81GHz, gcc 3.4.6 -O3

short add/sub: 0.553863 [0] 
short mul/div: 12.509163 [0] 
long add/sub: 0.556912 [0] 
long mul/div: 12.748019 [0] 
long long add/sub: 5.298999 [0] 
long long mul/div: 20.461186 [0] 
float add/sub: 2.688253 [0] 
float mul/div: 4.683886 [0] 
double add/sub: 2.700834 [0] 
double mul/div: 4.646755 [0] 

Come Dan pointed out, anche una volta che si normalizzare per frequenza di clock (che può essere fuorviante in se stessa in disegni pipeline), risultati variano selvaggiamente basato su un'architettura CPU (individuale ALU/FPU prestazioni, nonché effettivo numero di ALU/FPU disponibile per core in superscalar disegni che influenza quante independent operations can execute in parallel - la quest'ultimo fattore non sia esercitata con il codice di seguito come tutte le operazioni seguenti si sequenzialmente dipendente)

FPU/ALU operazione benchmark povera, stile:.

#include <stdio.h> 
#ifdef _WIN32 
#include <sys/timeb.h> 
#else 
#include <sys/time.h> 
#endif 
#include <time.h> 

double 
mygettime(void) { 
# ifdef _WIN32 
    struct _timeb tb; 
    _ftime(&tb); 
    return (double)tb.time + (0.001 * (double)tb.millitm); 
# else 
    struct timeval tv; 
    if(gettimeofday(&tv, 0) < 0) { 
    perror("oops"); 
    } 
    return (double)tv.tv_sec + (0.000001 * (double)tv.tv_usec); 
# endif 
} 

template< typename Type > 
void my_test(const char* name) { 
    Type v = 0; 
    // Do not use constants or repeating values 
    // to avoid loop unroll optimizations. 
    // All values >0 to avoid division by 0 
    // Perform ten ops/iteration to reduce 
    // impact of ++i below on measurements 
    Type v0 = (Type)(rand() % 256)/16 + 1; 
    Type v1 = (Type)(rand() % 256)/16 + 1; 
    Type v2 = (Type)(rand() % 256)/16 + 1; 
    Type v3 = (Type)(rand() % 256)/16 + 1; 
    Type v4 = (Type)(rand() % 256)/16 + 1; 
    Type v5 = (Type)(rand() % 256)/16 + 1; 
    Type v6 = (Type)(rand() % 256)/16 + 1; 
    Type v7 = (Type)(rand() % 256)/16 + 1; 
    Type v8 = (Type)(rand() % 256)/16 + 1; 
    Type v9 = (Type)(rand() % 256)/16 + 1; 

    double t1 = mygettime(); 
    for (size_t i = 0; i < 100000000; ++i) { 
    v += v0; 
    v -= v1; 
    v += v2; 
    v -= v3; 
    v += v4; 
    v -= v5; 
    v += v6; 
    v -= v7; 
    v += v8; 
    v -= v9; 
    } 
    // Pretend we make use of v so compiler doesn't optimize out 
    // the loop completely 
    printf("%s add/sub: %f [%d]\n", name, mygettime() - t1, (int)v&1); 
    t1 = mygettime(); 
    for (size_t i = 0; i < 100000000; ++i) { 
    v /= v0; 
    v *= v1; 
    v /= v2; 
    v *= v3; 
    v /= v4; 
    v *= v5; 
    v /= v6; 
    v *= v7; 
    v /= v8; 
    v *= v9; 
    } 
    // Pretend we make use of v so compiler doesn't optimize out 
    // the loop completely 
    printf("%s mul/div: %f [%d]\n", name, mygettime() - t1, (int)v&1); 
} 

int main() { 
    my_test<short>("short"); 
    my_test<long>("long"); 
    my_test< long long >("long long"); 
    my_test<float>("float"); 
    my_test<double>("double"); 

    return 0; 
} 

Answer 8

Due punti da considerare -

L'hardware moderno può sovrapporsi alle istruzioni, eseguirle in parallelo e riordinarle per sfruttare al meglio l'hardware. Inoltre, qualsiasi programma in virgola mobile significativo ha probabilmente un lavoro intero significativo anche se calcola solo indici in matrici, contatori di loop ecc. Quindi anche se si dispone di un'istruzione a virgola mobile lenta potrebbe essere in esecuzione su un bit separato di hardware sovrapposto ad alcuni dei lavori interi. Il mio punto è che anche se le istruzioni in virgola mobile sono lente su quelle intere, il tuo programma generale potrebbe girare più veloce perché può utilizzare più hardware.

Come sempre, l'unico modo per essere sicuri è profilare il tuo programma attuale.

In secondo luogo, la maggior parte delle CPU in questi giorni dispone di istruzioni SIMD per virgola mobile in grado di operare su più valori in virgola mobile tutti allo stesso tempo. Ad esempio è possibile caricare 4 float in un singolo registro SSE e eseguire 4 moltiplicazioni su di essi tutti in parallelo. Se riesci a riscrivere parti del tuo codice per utilizzare le istruzioni SSE, sembra probabile che sarà più veloce di una versione intera. Visual C++ fornisce funzioni intrinseche del compilatore per fare ciò, vedere http://msdn.microsoft.com/en-us/library/x5c07e2a(v=VS.80).aspx per alcune informazioni.

Answer 9

Oggi, le operazioni integer sono di solito un po 'più veloci delle operazioni in virgola mobile. Quindi, se puoi fare un calcolo con le stesse operazioni in interi e in virgola mobile, usa numeri interi.TUTTAVIA stai dicendo "Questo causa un sacco di fastidiosi problemi e aggiunge un sacco di codice fastidioso". Sembra che tu abbia bisogno di più operazioni perché usi l'aritmetica dei numeri interi invece del punto mobile. In tal caso, in virgola mobile verrà eseguito più velocemente perché

(a) non appena avete bisogno di più le operazioni di interi, probabilmente avete bisogno di molto di più, quindi il vantaggio leggero velocità è più che divorato dalle operazioni aggiuntive

(b) il codice in virgola mobile è più semplice, il che significa che è più veloce scrivere il codice, il che significa che se è critico per la velocità, è possibile dedicare più tempo all'ottimizzazione del codice.

Answer 10

La versione in virgola mobile sarà molto più lenta, se non vi è alcuna operazione di resto. Poiché tutti gli add sono sequenziali, la cpu non sarà in grado di parallelizzare la sommatoria. La latenza sarà critica. La latenza di aggiunta di FPU è in genere di 3 cicli, mentre l'aggiunta di interi è di 1 ciclo. Tuttavia, il divisore per l'operatore restante sarà probabilmente la parte critica, in quanto non è completamente pipeline su CPU moderne. quindi, supponendo che l'istruzione divide/resto consumi la maggior parte del tempo, la differenza dovuta all'aggiunta della latenza sarà piccola.