webentwicklung-frage-antwort-db.com.de

Schnellster Weg, um einen realen (festen/Fließkomma) Wert festzuhalten

Gibt es eine effizientere Methode, reale Zahlen zu klemmen als if-Anweisungen oder ternäre Operatoren? Ich möchte dies sowohl für Doubles als auch für eine 32-Bit-Fixpoint-Implementierung (16.16) tun. Ich bin nicht frage nach Code, der beide Fälle verarbeiten kann; Sie werden in separaten Funktionen behandelt.

Natürlich kann ich so etwas tun:

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

oder

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

Die Fixpoint-Version würde Funktionen/Makros für Vergleiche verwenden.

Dies geschieht in einem leistungskritischen Teil des Codes, daher suche ich nach einem möglichst effizienten Weg (dies ist vermutlich eine Bit-Manipulation). 

BEARBEITEN: Es muss Standard/Portable C sein, plattformspezifische Funktionen sind hier nicht von Interesse. Außerdem sind MY_MIN und MY_MAX der gleiche Typ wie der Wert, den ich geklemmt haben möchte (in den obigen Beispielen verdoppelt).

37
Niklas

Für die 16.16-Darstellung ist es unwahrscheinlich, dass das einfache Ternärmodell in Bezug auf die Geschwindigkeit besser ist.

Und für das Doppelte, weil Sie es standard/portable C brauchen, wird das Fummeln jeglicher Art schlecht enden. 

Selbst wenn eine kleine Geige möglich wäre (was ich bezweifle), würden Sie sich auf die binäre Darstellung von Doubles verlassen. DIES (und ihre Größe) IS IMPLEMENTIERUNGSABHÄNGIG.

Möglicherweise könnten Sie dies mithilfe von sizeof (double) "erraten" und dann das Layout verschiedener doppelter Werte mit ihren gebräuchlichen binären Repräsentationen vergleichen, aber ich denke, Sie verstecken sich zu nichts.

Die beste Regel ist, dem Compiler zu sagen, was er will (z. B. ternär) und ihn für Sie optimieren lassen.

EDIT: Humble pie time. Ich habe gerade die Idee von Quinmars getestet (unten), und es funktioniert - wenn Sie über IEEE-754-Floats verfügen. Dies führte zu einer Beschleunigung von etwa 20% des nachstehenden Codes. IOblyly nicht portabel, aber ich denke, es gibt eine standardisierte Möglichkeit, Ihren Compiler zu fragen, ob er IEEE754-Float-Formate mit einem #IF verwendet ...?

  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);
8
Roddy

Alte Frage, aber ich arbeitete heute an diesem Problem (mit Doppel/Floats).

Am besten verwenden Sie SSE MINSS/MAXSS für Floats und SSE2 MINSD/MAXSD für Doubles. Diese sind verzweigungslos und benötigen jeweils einen Taktzyklus und sind dank Compiler-Intrinsics einfach zu bedienen. Sie bieten eine um mehr als eine Größenordnung gesteigerte Leistung im Vergleich zum Klemmen mit std :: min/max.

Das kann Sie überraschen. Ich habe es sicherlich getan! Leider verwendet VC++ 2010 einfache Vergleiche für std :: min/max, auch wenn/Arch: SSE2 und/FP: fast aktiviert sind. Ich kann nicht für andere Compiler sprechen.

Hier ist der notwendige Code, um dies in VC++ durchzuführen:

#include <mmintrin.h>

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;
}

Der Code mit doppelter Genauigkeit ist derselbe, mit Ausnahme von xxx_sd.

Edit: Anfangs habe ich die Clamp-Funktion als kommentiert geschrieben. Bei der Assembler-Ausgabe fiel mir jedoch auf, dass der VC++ - Compiler nicht intelligent genug war, um die redundante Bewegung zu beenden. Eine Anweisung weniger. :)

37
Spat

Sowohl GCC als auch Clang erzeugen eine schöne Assembly für den folgenden einfachen, unkomplizierten tragbaren Code:

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

Von GCC generierte Assembly:

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

Clang-generierte Assembly:

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

Drei Anweisungen (das Ret zählt nicht), keine Verzweigungen. Ausgezeichnet.

Getestet wurde dies mit GCC 4.7 und clang 3.2 auf Ubuntu 13.04 mit einem Core i3 M 350 . Nebenbei gesagt, der einfache C++ - Code, der std :: min und std :: max aufruft, erzeugte dieselbe Assembly.

Dies ist für ein Doppel. Und für int generieren sowohl GCC als auch clang Assembly mit fünf Befehlen (ohne den ret zu zählen) und ohne Verzweigungen. Auch ausgezeichnet.

Derzeit verwende ich kein Festkomma, daher werde ich zu Festkomma keine Stellungnahme abgeben.

36
Jorge

Wenn Ihr Prozessor eine schnelle Anweisung für den absoluten Wert hat (wie bei x86), können Sie ein verzweigungsloses min und max ausführen, was schneller ist als eine if-Anweisung oder eine ternäre Operation.

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

Wenn einer der Ausdrücke gleich Null ist (wie es beim Klemmen häufig der Fall ist), vereinfacht der Code ein wenig:

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

Wenn Sie beide Vorgänge kombinieren, können Sie die beiden /2 durch einen einzigen /4 oder *0.25 ersetzen, um einen Schritt zu speichern.

Der folgende Code ist bei meinem Athlon II X2 mehr als dreimal so schnell wie ternär, wenn die Optimierung für FMIN = 0 verwendet wird.

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
}
15
Mark Ransom

Ein ternärer Operator ist wirklich der richtige Weg, da die meisten Compiler sie in eine native Hardware-Operation kompilieren können, die eine bedingte Verschiebung anstelle einer Verzweigung verwendet (und somit Fehlstrafen und Pipeline-Blasen usw. verhindert). Bit-Manipulation verursacht wahrscheinlich einen Load-Hit-Store .

Insbesondere haben PPC und x86 mit SSE2 eine Hardwareoperation, die als intrinsisch wie folgt ausgedrückt werden kann:

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

Der Vorteil ist, dass dies innerhalb der Pipeline geschieht, ohne eine Verzweigung zu verursachen. Wenn Ihr Compiler den intrinsic verwendet, können Sie ihn verwenden, um Ihre Clamp direkt zu implementieren:

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

Ich empfehle dringend, dass Sie Bit-Manipulation von Doubles mit Integer-Operationen vermeiden . Bei den meisten modernen CPUs gibt es keine direkte Möglichkeit, Daten zwischen Doppel- und Int-Registern zu verschieben, außer durch einen Rundgang zum Dcache. Dies führt zu einer Datengefahr, die als Load-Hit-Store bezeichnet wird und die die CPU-Pipeline im Wesentlichen leert, bis der Speicherschreibvorgang abgeschlossen ist (normalerweise etwa 40 Zyklen). 

Die Ausnahme ist, wenn die doppelten Werte bereits im Speicher und nicht in einem Register gespeichert sind: In diesem Fall besteht keine Gefahr eines Load-Hit-Speichers. Ihr Beispiel zeigt jedoch, dass Sie das Doppelte berechnet und aus einer Funktion zurückgegeben haben. Das bedeutet, dass es wahrscheinlich immer noch in XMM1 ist.

14
Crashworks

Anstatt zu testen und zu verzweigen, verwende ich normalerweise dieses Format zum Klemmen:

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

Obwohl ich noch nie eine Leistungsanalyse des kompilierten Codes durchgeführt habe.

7
Linasses

Die Bits des IEEE 754-Gleitkommas sind so angeordnet, dass beim Vergleich der als Ganzzahl interpretierten Bits die gleichen Ergebnisse erzielt werden, als würden sie direkt als Floats verglichen. Wenn Sie also eine Methode zum Klemmen von Ganzzahlen finden oder kennen, können Sie diese auch für (IEEE 754) -Objekte verwenden. Entschuldigung, ich kenne keinen schnelleren Weg.

Wenn Sie die Floats in Arrays gespeichert haben, können Sie erwägen, einige CPU-Erweiterungen wie SSE3 zu verwenden, wie rkj gesagt hat. Sie können einen Blick auf liboil werfen, es erledigt all die schmutzige Arbeit für Sie. Hält Ihr Programm portabel und verwendet wenn möglich schnellere CPU-Anweisungen. (Ich bin nicht sicher, wie OS/Compiler-unabhängige liboil ist).

7
quinmars

Realistisch gesehen macht kein anständiger Compiler einen Unterschied zwischen einer if () - Anweisung und einem?: - Ausdruck. Der Code ist so einfach, dass er die möglichen Pfade erkennen kann. Ihre beiden Beispiele sind jedoch nicht identisch. Der äquivalente Code mit?: Wäre

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

vermeiden Sie daher den A <MIN-Test, wenn a> MAX. Das könnte einen Unterschied machen, da der Compiler sonst die Beziehung zwischen den beiden Tests feststellen müsste.

Wenn das Klemmen selten ist, können Sie die Notwendigkeit des Klemmens mit einem einzigen Test testen:

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

Z.B. Bei MIN = 6 und MAX = 10 wird dies zunächst um 8 nach unten verschoben und dann überprüft, ob es zwischen -2 und +2 liegt. Ob dies etwas spart, hängt stark von den relativen Verzweigungskosten ab.

4
MSalters

Hier ist eine möglicherweise schnellere Implementierung ähnlich der Antwort von @ 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 */
}

Siehe Berechne das Minimum (Min) oder Maximum (Max) von zwei ganzen Zahlen ohne Verzweigung und Vergleich von Fließkommazahlen

Die IEEE-Float- und -Doppelformate waren so gestaltet, dass die Zahlen .__ sind. "Lexikographisch geordnet", das – mit den Worten des IEEE-Architekten William Kahan bedeutet "wenn zwei Gleitkomma Zahlen im gleichen Format werden geordnet (sagen Sie x <y), dann werden sie geordnet die gleiche Weise, wenn ihre Bits .__ sind. neu interpretiert als Vorzeichengröße ganze Zahlen. “

Ein Testprogramm:

/** gcc -std=c99 -fno-strict-aliasing -O2 -lm -Wall *.c -o clip_double && clip_double */
#include <assert.h> 
#include <iso646.h>  // not, and
#include <math.h>    // isnan()
#include <stdbool.h> // bool
#include <stdint.h>  // int64_t
#include <stdio.h>

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 der Konsole:

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

Es druckt:

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)
2
jfs

Ich habe den Ansatz von SSE selbst versucht, und die Assembly-Ausgabe sah ein bisschen sauberer aus, daher wurde ich zuerst ermutigt, aber nachdem ich sie tausendmal getaktet hatte, war sie tatsächlich ein bisschen langsamer. Es sieht tatsächlich so aus, als ob der VC++ - Compiler nicht intelligent genug ist, um zu wissen, was Sie wirklich vorhaben, und er scheint Dinge zwischen den XMM-Registern und dem Speicher hin und her zu verschieben, wenn dies nicht der Fall sein sollte. Ich weiß jedoch nicht, warum der Compiler nicht intelligent genug ist, die min/max-Anweisungen SSE für den ternären Operator zu verwenden, wenn er sowieso SSE -Anweisungen für alle Gleitkommaberechnungen zu verwenden scheint. Wenn Sie dagegen für PowerPC kompilieren, können Sie die in den FP -Registern enthaltene fsel verwenden, und das ist viel schneller.

1
Corey

Wie bereits erwähnt, funktionieren die Funktionen von fmin/fmax gut (in gcc mit -ffast-math). Obwohl gfortran Muster hat, um IA-Anweisungen zu verwenden, die max/min entsprechen, ist dies bei g ++ nicht der Fall. In icc muss man stattdessen std :: min/max verwenden, da icc die Angabe der Funktionsweise von fmin/fmax mit nicht endlichen Operanden nicht zulässt.

0
tim18

Wenn Sie schnelle Absolutwertanweisungen verwenden möchten, überprüfen Sie diesen Code, den ich in Minicomputer gefunden habe, der einen Float im Bereich [0,1] festhält.

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

(Ich habe den Code etwas vereinfacht). Wir können darüber nachdenken, dass wir zwei Werte annehmen, von denen einer als> 0 gilt

fabs(x)

und der andere reflektierte etwa 1,0 zu <1,0

1.0-fabs(x-1.0)

Und wir nehmen den Durchschnitt von ihnen. Wenn es sich innerhalb des Bereichs befindet, sind beide Werte gleich x, daher wird ihr Durchschnitt wieder x sein. Wenn es außerhalb des Bereichs liegt, ist einer der Werte x, und der andere wird x über den "Grenz" -Punkt geschwenkt, so dass deren Durchschnitt genau der Grenzpunkt ist.

0
Jeremy Salwen

Meine 2 Cent in C++. Wahrscheinlich nicht anders als ternäre Operatoren verwenden und hoffentlich wird kein Verzweigungscode generiert

template <typename T>
inline T clamp(T val, T lo, T hi) {
    return std::max(lo, std::min(hi, val));
}
0
wcochran

Wenn ich es richtig verstanden habe, möchten Sie einen Wert "a" auf einen Bereich zwischen MY_MIN und MY_MAX begrenzen. Der Typ von "a" ist ein Double. Sie haben den Typ von MY_MIN oder MY_MAX nicht angegeben.

Der einfache Ausdruck:

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

sollte den Trick tun.

Ich denke, dass es eine kleine Optimierung gibt, wenn MY_MAX und MY_MIN Ganzzahlen sind:

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

Durch den Wechsel zu ganzzahligen Vergleichen können Sie möglicherweise einen geringfügigen Geschwindigkeitsvorteil erzielen.

0
abelenky

Ich denke, Sie könnten SSE3 oder eine ähnliche Technologie dafür verwenden, wissen jedoch nicht genau, welche Befehle/wie ....__ Sie können einen Blick darauf werfen: Sättigungsarithmetik

0
rkj