confronto dei numeri in virgola mobile rispetto al confronto dei numeri interi in C [chiuso]

Question

confronto dei numeri in virgola mobile rispetto al confronto dei numeri interi in C [chiuso]

#1 da (2 voti)
#2 da (1 voti)
#3 da (1 voti)

1

Il confronto tra numeri in virgola mobile richiede (considerevolmente) tempo più lungo rispetto al confronto dei numeri interi in C?

Ho appena scritto un programma C di heap sort per ordinare i numeri in virgola mobile.

Sono su ubuntu 14.04 e ho usato il comando time per controllare il tempo impiegato da questo programma per l'ordinamento di numeri casuali 50, 5000 e 50000 e poi ho appena cambiato tutto double in int e di nuovo il tempo controllato per 50, 5000 e 5000 numeri e statistiche sono i seguenti:

$ time ./heap 50 < input.txt 

real    0m0.003s
user    0m0.001s
sys 0m0.002s
$ time ./temp 50 < input.txt 

real    0m0.003s
user    0m0.001s
sys 0m0.002s
$ time ./heap 5000 < input.txt 

real    0m0.008s
user    0m0.007s
sys 0m0.002s
$ time ./temp 5000 < input.txt 

real    0m0.005s
user    0m0.004s
sys 0m0.001s
$ time ./heap 50000 < input.txt 

real    0m0.030s
user    0m0.028s
sys 0m0.002s
$ time ./temp 50000 < input.txt 

real    0m0.027s
user    0m0.026s
sys 0m0.002s
$ time ./heap 500000 < input.txt 

real    0m0.263s
user    0m0.259s
sys 0m0.003s
$ time ./temp 500000 < input.txt 

real    0m0.219s
user    0m0.216s
sys 0m0.003s

Qui heap è l'eseguibile di heapsort in virgola mobile e temp è l'eseguibile di Numero intero di heapsort.

Come possiamo vedere, c'è una differenza notevole nei tempi di esecuzione? Qual è il motivo? Posso caricare i codici se necessario.

c performance sorting

posta Nullpointer 06.05.2014 - 14:52

fonte

3 risposte

Leggi altre domande sui tag c performance sorting

Quando il mio codice è automaticamente in GPL? In che modo il caricamento / memorizzazione dei byte è implementato dalla CPU?

score 2 · Answer 1

Cronometrare il tuo codice come questo non dice molto.

Esiste un sovraccarico dell'interprete di testo di bash
Esiste un sovraccarico del programma di caricamento del kernel
Esiste un sovraccarico del processo stesso (inizializzazione e collegamento di dylib)
I dati letti dal file sono inclusi nel tempo (atoi e / o atof)
Hai utilizzato un metodo AlmostEqual2sComplement o solo l'operatore ==?

Ulteriori informazioni su AlmostEqual2sComplement

Anche se dovessi usare un tempo più preciso, che dovrebbe essere incluso nel programma. Direi che la differenza è ancora più grande. Quando utilizziamo due punti mobili, f1 = 2,25 + 2,75 e f2 = 2,5 + 2,5. Ora un confronto come fp1 == fp2 probabilmente restituirà false. Qui un articolo su come confronta i punti fluttuanti . Ciò significa che non puoi utilizzare fp1 == fp2 nel tuo benchmark e la funzione AlmostEqual2sComplement() che stai cercando richiede così tante più istruzioni per un confronto migliore che il confronto effettivo tra i punti mobili è molto più lento rispetto al confronto di due interi .

Anche se vuoi continuare a usare fp1 == fp2 la migliore risposta alla tua domanda sarebbe che dipende totalmente dal processore e dal compilatore. Solo un confronto di dati è necessario per assicurarsi che entrambi gli elementi di dati sono ugualmente in lunghezza di bit. Quindi quando un float è 64-bit avrai bisogno anche di un numero intero a 64-bit. Quindi il confronto == potrebbe essere altrettanto veloce in teoria, ma ancora dipende dal compilatore e dal processore.

score 1 · Answer 2

In generale, ci aspettiamo che le operazioni FP siano più costose. Non parlare di double s. Questo perché float s richiede operazioni a complessità elevata. Richiedono anche cure speciali nelle funzioni matematiche. Sono un'approssimazione del numero che desideri. Quindi queste funzioni fanno ciò che possono fare per ottenere piccoli errori.

L'aritmetica in virgola mobile è implementata da FPU . Sulle CPU che si trovano nei personal computer, FPU è avanzato rispetto alle CPU di sistemi embedded e altri dispositivi mobili (smartphone, ecc.). E questo perché l'aritmetica in virgola mobile non è efficiente quanto l'aritmetica dei numeri interi.

Quindi la conclusione qui, considerando che lavori su un personal computer e vedendo i tuoi delta temporali, i risultati sono logici. Se avessi eseguito questo programma su uno smartphone vedresti un delta più grande in tempi.

score 1 · Answer 3

A livello di CPU, le operazioni integer e floating point sono istruzioni separate.

Un intero è un semplice schema di bit in cui ogni bit rappresenta una potenza di due o un bit di segno. Ci sono molte ottimizzazioni del microcodice nelle moderne CPU (anche su dispositivi mobili) che rendono l'aritmetica dei numeri interi e i confronti super veloci.

Le operazioni e i confronti in virgola mobile sono più complessi. La stragrande maggioranza delle moderne CPU in grado di gestire in virgola mobile utilizza lo standard IEEE-754 . Un numero in virgola mobile (o doppio, o doppio lungo, l'idea è la stessa) è più complesso: ha sia una mantissa che un esponente oltre al bit del segno. Ha anche schemi di bit speciali che rappresentano NaN (non un numero), infinito positivo e negativo, nonché positivo e negativo zero.

Ciò significa in pratica che anche se un punto mobile confronta o aggiunge o qualsiasi altra operazione è una singola istruzione CPU, tale istruzione ha molto lavoro da fare e richiederà parecchie volte più di un'operazione intera. Qual è il risultato di "NaN < 4.5" o "7.0 < 7.0"? Che ne dici di "1e-30 < 1e30"? La CPU deve essere in grado di gestire i "numeri" speciali come NaN e trattarli correttamente secondo le specifiche. Deve anche essere in grado di gestire situazioni di overflow o underflow in cui due numeri non possono essere usati realisticamente insieme a causa delle limitazioni nella dimensione dell'esponente.

I circuiti nella CPU devono essere in grado di gestire tutto ciò che aggiunge complessità, aggiunge tempo all'elaborazione in virgola mobile e significa che il programma che hai scritto per ordinare i float impiegherà più tempo.

Un'altra cosa che potrebbe essere utile esaminare (ma non è strettamente parte di questa risposta) è di scaricare il programma in virgola mobile su una GPU. I processori grafici rivaleggiano con le CPU qui nel 2014 per complessità e dimensioni del circuito. Sono altamente paralleli e altamente ottimizzati per le operazioni in virgola mobile, dal momento che la grafica 3D si basa molto sulla matematica in virgola mobile.

Scrivere un programma per ordinare i float usando la GPU potrebbe essere un'interessante diversione e una buona esperienza di apprendimento.