Confronta array float come int array

Question

Ho bisogno di un algoritmo di ricerca binaria ottimizzato su una matrice di numeri ordinati. Ho fatto questo e ha scoperto che l'uso di float ai numeri Store è più veloce rispetto all'utilizzo intero, perché alla fine devo calcolare

(frameNumber-this->frameNumber[imin])/(this->frameNumber[imax]-this->frameNumber[imin]) 

this->frameNumber[imin] è il più grande frameNumber meno uguali che frameNumber e this->frameNumber[imax] è il più piccolo uno più grande uguale quella. Quel codice serve a calcolare l'avanzamento tra i due keyframe. l'array frameNumber è statico. Devo solo ordinarlo una volta. Ma accedilo molte volte con una ricerca binaria e il codice sopra per calcolare i progressi.

La conversione da int a galleggiante ha trascorso alcuni cicli. Poi ho scoperto che nell'asma ci sono un sacco di istruzioni per la Fpu. Mi preoccupo che potrebbero essere più lenti dei numeri interi.

Quindi ecco la domanda. Posso convertire un array di numeri in virgola mobile ordinati in un * int e eseguire una ricerca binaria su di esso?

Ciò significa:

void binary_search(float key,float* array,...) 
{ 
    int key_integer=*(int*)&key; 
    int* array_intege(int*)array; 
    binary_search_for_integers(key_integer,array_integer,...); 
} 

O la mia sopra conclusioni sono sbagliati? (Come la fusione int a stare a galla non è così costy, o confronto tra i punti di galleggiamento è lo stesso veloce come numeri interi?

Grazie mille!

Answer 1

Questo mi sembra una cattiva idea. Utilizzando intero Confronta su dati float in realtà si tradurrà in un array correttamente ordinata di carri allegorici, come @rlbond sottolinea. (Vedi http://www.h-schmidt.net/FloatConverter/IEEE754.html per giocare con le rappresentazioni binarie di carri allegorici.) Controllare che sizeof(int32_t) == sizeof(float) prima di utilizzare questo.

un hack come questo non è realmente necessario. Il confronto float non è molto più costoso del confronto int, su hardware moderno. (Intel Haswell: ucomiss è 1 uop, con 1 per ciclo di throughput.Per confronto con un operando di memoria è 2 uops, nessuna microfusione, però. E non può fungere da macro come cmp/jcc) Tuttavia, FP add/sub e FP mul ha latenze più elevate rispetto ai loro equivalenti interi e meno throughput. Sembra stupido convertire un'intera matrice in float mentre ci stai scrivendo solo perché vuoi fare un po 'di matematica FP con i valori minimo e massimo alla fine.

Un carico-e-convert-int-to-galleggiante istruzione (x86 cvtsi2ss (firmato integer 2 scalare singolo)) è circa veloce, e prende lo stesso spazio di codice, come un carico normale (movss).

Se i dati in origine erano interi e ne si utilizza solo uno, utilizzare int (evitando la conversione per valori che non è necessario in seguito). Se accedi a tutto questo e utilizzi sempre i dati come float, memorizzalo come float. Se lo si utilizza come entrambi, è probabilmente meglio memorizzarlo come int, quindi è più veloce quando lo si utilizza come numero intero e alla stessa velocità in entrambi i casi quando lo si utilizza come float.

Dal tuo esempio di codice, stai semplicemente utilizzando i valori nelle posizioni min e max? È molto più veloce trovare i valori minimo e massimo in un array piuttosto che ordinare l'intero array. min/max vectorizza anche con le istruzioni packed-min.

Molte piattaforme non hanno il punto di virgola mobile più veloce delle moderne CPU Intel, quindi non esagerare con virgola mobile.