Il modo più veloce per bloccare un valore reale (fisso / virgola mobile)?

Esiste un modo più efficiente per bloccare i numeri reali rispetto all’utilizzo di istruzioni o operatori ternari? Voglio farlo sia per il doppio che per un’implementazione del fixpoint a 32 bit (16.16). Non sto chiedendo il codice che possa gestire entrambi i casi; saranno gestiti in funzioni separate.

Ovviamente, posso fare qualcosa come:

double clampedA; double a = calculate(); clampedA = a > MY_MAX ? MY_MAX : a; clampedA = a < MY_MIN ? MY_MIN : a; 

o

 double a = calculate(); double clampedA = a; if(clampedA > MY_MAX) clampedA = MY_MAX; else if(clampedA < MY_MIN) clampedA = MY_MIN; 

La versione del fixpoint userebbe funzioni / macro per il confronto.

Questo viene fatto in una parte critica del rendimento, quindi sto cercando un modo efficiente di farlo il più ansible (che sospetto implicherebbe manipolazioni di bit)

EDIT: deve essere standard / portatile C, la funzionalità specifica della piattaforma non è di alcun interesse qui. Inoltre, MY_MIN e MY_MAX sono dello stesso tipo del valore I want clamped (raddoppia negli esempi sopra).

Per la rappresentazione 16.16, è improbabile che il semplice ternario venga migliorato in termini di velocità.

E per i doppi, perché ne hai bisogno di uno standard / portatile C, un po ‘di giocherellona di qualsiasi tipo finirà male.

Anche se fosse ansible un po ‘di violino (cosa di cui dubito), faresti affidamento sulla rappresentazione binaria dei doppi. QUESTO (e le loro dimensioni) È DIPENDENTE-DIPENDENTE.

Forse potresti “indovinare” questo usando sizeof (double) e poi confrontando il layout di vari doppi valori con le loro comuni rappresentazioni binarie, ma penso che tu non ti stia nascondendo.

La regola migliore è RACCONTARE IL COMPILATORE COSA VUOI (cioè ternario) e lasciarlo ottimizzare per te.

EDIT: tempo di torta umile. Ho appena testato l’idea di quinmars (sotto), e funziona – se hai i float IEEE-754. Questo ha dato una velocità di circa il 20% sul codice qui sotto. Ovviamente non è portatile, ma penso che ci possa essere un modo standardizzato di chiedere al compilatore se usa i formati float IEEE754 con un #IF …?

  double FMIN = 3.13; double FMAX = 300.44; double FVAL[10] = {-100, 0.23, 1.24, 3.00, 3.5, 30.5, 50 ,100.22 ,200.22, 30000}; uint64 Lfmin = *(uint64 *)&FMIN; uint64 Lfmax = *(uint64 *)&FMAX; DWORD start = GetTickCount(); for (int j=0; j<10000000; ++j) { uint64 * pfvalue = (uint64 *)&FVAL[0]; for (int i=0; i<10; ++i) *pfvalue++ = (*pfvalue < Lfmin) ? Lfmin : (*pfvalue > Lfmax) ? Lfmax : *pfvalue; } volatile DWORD hacktime = GetTickCount() - start; for (int j=0; j<10000000; ++j) { double * pfvalue = &FVAL[0]; for (int i=0; i<10; ++i) *pfvalue++ = (*pfvalue < FMIN) ? FMIN : (*pfvalue > FMAX) ? FMAX : *pfvalue; } volatile DWORD normaltime = GetTickCount() - (start + hacktime); 

Vecchia domanda, ma stavo lavorando a questo problema oggi (con doppio / float).

L’approccio migliore è utilizzare SSE MINSS / MAXSS per i float e SSE2 MINSD / MAXSD per i doppi. Questi sono senza ramo e prendono un ciclo di clock ciascuno, e sono facili da usare grazie all’intrinseca del compilatore. Essi conferiscono più di un ordine di grandezza in termini di prestazioni rispetto al serraggio con std :: min / max.

Potresti trovarlo sorprendente. Ho certamente fatto! Sfortunatamente VC ++ 2010 usa semplici confronti per std :: min / max anche quando / arch: SSE2 e / FP: veloce sono abilitati. Non posso parlare per altri compilatori.

Ecco il codice necessario per farlo in VC ++:

 #include  float minss ( float a, float b ) { // Branchless SSE min. _mm_store_ss( &a, _mm_min_ss(_mm_set_ss(a),_mm_set_ss(b)) ); return a; } float maxss ( float a, float b ) { // Branchless SSE max. _mm_store_ss( &a, _mm_max_ss(_mm_set_ss(a),_mm_set_ss(b)) ); return a; } float clamp ( float val, float minval, float maxval ) { // Branchless SSE clamp. // return minss( maxss(val,minval), maxval ); _mm_store_ss( &val, _mm_min_ss( _mm_max_ss(_mm_set_ss(val),_mm_set_ss(minval)), _mm_set_ss(maxval) ) ); return val; } 

Il doppio codice di precisione è lo stesso ad eccezione di xxx_sd.

Modifica: Inizialmente ho scritto la funzione morsetto come commentato. Guardando l’output dell’assembler, ho notato che il compilatore VC ++ non era abbastanza intelligente da consentire la rimozione della mossa ridondante. Una istruzione in meno. 🙂

Sia GCC che clang generano un bellissimo assemblaggio per il seguente codice semplice, semplice e portatile:

 double clamp(double d, double min, double max) { const double t = d < min ? min : d; return t > max ? max : t; } 

> gcc -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c

Assemblaggio generato da GCC:

 maxsd %xmm0, %xmm1 # d, min movapd %xmm2, %xmm0 # max, max minsd %xmm1, %xmm0 # min, max ret 

> clang -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c

Assemblaggio generato da clang:

 maxsd %xmm0, %xmm1 minsd %xmm1, %xmm2 movaps %xmm2, %xmm0 ret 

Tre istruzioni (senza contare il ret), senza rami. Eccellente.

Questo è stato testato con GCC 4.7 e clang 3.2 su Ubuntu 13.04 con un Core i3 M 350. Su una nota a margine, il semplice codice C ++ che ha chiamato std :: min e std :: max ha generato lo stesso assembly.

Questo è per i doppi. E per int, sia GCC che clang generano assembly con cinque istruzioni (senza contare il ret) e senza rami. Anche eccellente.

Al momento non utilizzo il punto fisso, quindi non darò un’opinione sul punto fisso.

Se il tuo processore ha un’istruzione veloce per il valore assoluto (come fa l’x86), puoi fare un minimo e un massimo senza branch che sarà più veloce di un’istruzione if o di un’operazione ternaria.

 min(a,b) = (a + b - abs(ab)) / 2 max(a,b) = (a + b + abs(ab)) / 2 

Se uno dei termini è zero (come spesso accade quando stai bloccando) il codice semplifica un po ‘di più:

 max(a,0) = (a + abs(a)) / 2 

Quando si combinano entrambe le operazioni, è ansible sostituire il due /2 in un singolo /4 o *0.25 per salvare un passaggio.

Il seguente codice è oltre 3 volte più veloce di ternario sul mio Athlon II X2, quando si utilizza l’ottimizzazione per FMIN = 0.

 double clamp(double value) { double temp = value + FMAX - abs(value-FMAX); #if FMIN == 0 return (temp + abs(temp)) * 0.25; #else return (temp + (2.0*FMIN) + abs(temp-(2.0*FMIN))) * 0.25; #endif } 

L’operatore ternario è davvero la strada da percorrere, perché la maggior parte dei compilatori è in grado di compilarli in un’operazione hardware nativa che utilizza una mossa condizionale invece di un ramo (evitando così penalità errate e bolle della pipeline e così via). È probabile che la manipolazione dei bit causi un load-hit-store .

In particolare, PPC e x86 con SSE2 hanno un op hardware che potrebbe essere express come intrinseco qualcosa del genere:

 double fsel( double a, double b, double c ) { return a >= 0 ? b : c; } 

Il vantaggio è che lo fa all’interno della pipeline, senza causare un ramo. Infatti, se il tuo compilatore usa l’intrinseco, puoi usarlo per implementare direttamente il tuo morsetto:

 inline double clamp ( double a, double min, double max ) { a = fsel( a - min , a, min ); return fsel( a - max, max, a ); } 

Vi suggerisco caldamente di evitare la manipolazione dei bit dei doppi usando le operazioni integer . Sulla maggior parte delle CPU moderne non vi è alcun mezzo diretto per spostare i dati tra registri doppio e int, se non effettuando un viaggio di andata e ritorno verso il dcache. Ciò causerà un pericolo di dati chiamato load-hit-store che sostanzialmente svuota la pipeline della CPU fino a quando la scrittura della memoria non è completata (in genere circa 40 cicli o giù di lì).

L’eccezione a questo è se i valori double sono già in memoria e non in un registro: in tal caso non c’è pericolo di un load-hit-store. Tuttavia, il tuo esempio indica che hai appena calcolato il doppio e lo hai restituito da una funzione, il che significa che è probabile che rimanga ancora in XMM1.

I bit di IEEE 754 in virgola mobile sono ordinati in modo tale che se si confrontano i bit interpretati come un intero si ottengono gli stessi risultati come se li si confrontassero come float direttamente. Quindi, se si trova o si conosce un modo per bloccare interi, è ansible utilizzarlo anche per (IEEE 754). Scusa, non conosco un modo più veloce.

Se hai i float memorizzati in un array puoi considerare di utilizzare alcune estensioni della CPU come SSE3, come ha detto rkj. Puoi dare un’occhiata a Liboil fa tutto il lavoro sporco per te. Mantiene il tuo programma portatile e usa più velocemente le istruzioni della CPU, se ansible. (Non sono sicuro di come sia il liboil OS / compilatore indipendente).

Piuttosto che testare e ramificare, normalmente utilizzo questo formato per il serraggio:

 clampedA = fmin(fmax(a,MY_MIN),MY_MAX); 

Anche se non ho mai fatto alcuna analisi delle prestazioni sul codice compilato.

Realisticamente, nessun compilatore decente farà la differenza tra un’istruzione if () e un’espressione?:. Il codice è abbastanza semplice da essere in grado di individuare i percorsi possibili. Detto questo, i tuoi due esempi non sono identici. Il codice equivalente usando?: Sarebbe

 a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a); 

in quanto evita il test A MAX. Ora ciò potrebbe fare la differenza, in quanto altrimenti il ​​compilatore dovrebbe individuare la relazione tra i due test.

Se il serraggio è raro, è ansible testare la necessità di serrare con un singolo test:

 if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ... 

Ad esempio con MIN = 6 e MAX = 10, questo cambierà prima un down di 8, quindi verificherà se si trova tra -2 e +2. Se questo risparmia qualcosa dipende molto dal costo relativo della ramificazione.

Ecco un’implementazione possibilmente più veloce simile alla risposta di @ Roddy :

 typedef int64_t i_t; typedef double f_t; static inline i_t i_tmin(i_t x, i_t y) { return (y + ((x - y) & -(x < y))); // min(x, y) } static inline i_t i_tmax(i_t x, i_t y) { return (x - ((x - y) & -(x < y))); // max(x, y) } f_t clip_f_t(f_t f, f_t fmin, f_t fmax) { #ifndef TERNARY assert(sizeof(i_t) == sizeof(f_t)); //assert(not (fmin < 0 and (f < 0 or is_negative_zero(f)))); //XXX assume IEEE-754 compliant system (lexicographically ordered floats) //XXX break strict-aliasing rules const i_t imin = *(i_t*)&fmin; const i_t imax = *(i_t*)&fmax; const i_t i = *(i_t*)&f; const i_t iclipped = i_tmin(imax, i_tmax(i, imin)); #ifndef INT_TERNARY return *(f_t *)&iclipped; #else /* INT_TERNARY */ return i < imin ? fmin : (i > imax ? fmax : f); #endif /* INT_TERNARY */ #else /* TERNARY */ return fmin > f ? fmin : (fmax < f ? fmax : f); #endif /* TERNARY */ } 

Vedi Calcola il minimo (min) o il massimo (massimo) di due numeri interi senza diramazioni e confronti tra numeri in virgola mobile

Il float IEEE e i doppi formati sono stati progettati in modo che i numeri siano "ordinati lessicograficamente", che - per le parole dell'architetto IEEE William Kahan significa "se due numeri in virgola mobile nello stesso formato sono ordinati (per esempio x

Un programma di test:

 /** gcc -std=c99 -fno-strict-aliasing -O2 -lm -Wall *.c -o clip_double && clip_double */ #include  #include  // not, and #include  // isnan() #include  // bool #include  // int64_t #include  static bool is_negative_zero(f_t x) { return x == 0 and 1/x < 0; } static inline f_t range(f_t low, f_t f, f_t hi) { return fmax(low, fmin(f, hi)); } static const f_t END = 0./0.; #define TOSTR(f, fmin, fmax, ff) ((f) == (fmin) ? "min" : \ ((f) == (fmax) ? "max" : \ (is_negative_zero(ff) ? "-0.": \ ((f) == (ff) ? "f" : #f)))) static int test(f_t p[], f_t fmin, f_t fmax, f_t (*fun)(f_t, f_t, f_t)) { assert(isnan(END)); int failed_count = 0; for ( ; ; ++p) { const f_t clipped = fun(*p, fmin, fmax), expected = range(fmin, *p, fmax); if(clipped != expected and not (isnan(clipped) and isnan(expected))) { failed_count++; fprintf(stderr, "error: got: %s, expected: %s\t(min=%g, max=%g, f=%g)\n", TOSTR(clipped, fmin, fmax, *p), TOSTR(expected, fmin, fmax, *p), fmin, fmax, *p); } if (isnan(*p)) break; } return failed_count; } int main(void) { int failed_count = 0; f_t arr[] = { -0., -1./0., 0., 1./0., 1., -1., 2, 2.1, -2.1, -0.1, END}; f_t minmax[][2] = { -1, 1, // min, max 0, 2, }; for (int i = 0; i < (sizeof(minmax) / sizeof(*minmax)); ++i) failed_count += test(arr, minmax[i][0], minmax[i][1], clip_f_t); return failed_count & 0xFF; } 

In console:

 $ gcc -std=c99 -fno-strict-aliasing -O2 -lm *.c -o clip_double && ./clip_double 

Stampa:

 error: got: min, expected: -0. (min=-1, max=1, f=0) error: got: f, expected: min (min=-1, max=1, f=-1.#INF) error: got: f, expected: min (min=-1, max=1, f=-2.1) error: got: min, expected: f (min=-1, max=1, f=-0.1) 

Ho provato l’approccio SSE a me stesso, e l’output di assemblaggio sembrava un po ‘più pulito, quindi all’inizio ero incoraggiato, ma dopo averlo cronometrato migliaia di volte, era in realtà un po’ più lento. Sembra davvero che il compilatore VC ++ non sia abbastanza intelligente per sapere cosa si intende davvero, e sembra spostare le cose avanti e indietro tra i registri XMM e la memoria quando non dovrebbe. Detto questo, non so perché il compilatore non sia abbastanza intelligente da utilizzare le istruzioni min / max SSE sull’operatore ternario quando sembra utilizzare comunque le istruzioni SSE per tutti i calcoli in virgola mobile. D’altra parte, se stai compilando per PowerPC, puoi usare fsel intrinsic nei registri FP, ed è molto più veloce.

Se ho capito bene, vuoi limitare un valore “a” a un intervallo compreso tra MY_MIN e MY_MAX. Il tipo di “a” è un doppio. Non hai specificato il tipo di MY_MIN o MY_MAX.

La semplice espressione:

 clampedA = (a > MY_MAX)? MY_MAX : (a < MY_MIN)? MY_MIN : a; 

dovrebbe fare il trucco

Penso che ci possa essere una piccola ottimizzazione da fare se MY_MAX e MY_MIN capita di essere interi:

 int b = (int)a; clampedA = (b > MY_MAX)? (double)MY_MAX : (b < MY_MIN)? (double)MY_MIN : a; 

Passando ai confronti tra interi, è ansible che si ottenga un leggero vantaggio di velocità.

Penso che potresti usare SSE3 o una tecnologia simile per questo, ma non so esattamente quali comandi / come … Puoi dare un’occhiata a: Aritmetica della saturazione

Se vuoi usare istruzioni rapide di valore assoluto, controlla questo frammento di codice che ho trovato nel minicomputer , che blocca un float nell’intervallo [0,1]

 clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f); 

(Ho semplificato un po ‘il codice). Possiamo pensarci prendendo due valori, uno riflesso per essere> 0

 fabs(x) 

e l’altro riflette su 1.0 per essere <1,0

 1.0-fabs(x-1.0) 

E prendiamo la media di loro. Se è nell’intervallo, entrambi i valori saranno uguali a x, quindi la loro media sarà nuovamente x. Se è fuori intervallo, allora uno dei valori sarà x, e l’altro sarà x capovolto sul punto “limite”, quindi la loro media sarà esattamente il punto di confine.

Come sottolineato sopra, le funzioni fmin / fmax funzionano bene (in gcc, con -ffast-math). Sebbene gfortran abbia schemi per usare le istruzioni IA corrispondenti a max / min, g ++ no. In icc si deve usare invece std :: min / max, perché icc non consente di scorciare le specifiche di come fmin / fmax funzioni con operandi non finiti.

I miei 2 centesimi in C ++. Probabilmente non è diverso da usare gli operatori ternari e si spera che non venga generato alcun codice di diramazione

 template  inline T clamp(T val, T lo, T hi) { return std::max(lo, std::min(hi, val)); }