Der schnellste Weg, um einen realen (Fest- / Gleitkomma-) Wert zu klemmen?

Gibt es eine effizientere Möglichkeit, reelle Zahlen zu klemmen, als if-Anweisungen oder ternäre Operatoren zu verwenden? Ich möchte dies sowohl für Doubles als auch für eine 32-Bit-Fixpoint-Implementierung (16.16) tun. Ich bin nicht nach Code fragen, der beide Fälle handhaben 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 zu tun (was meiner Meinung nach eine Bitmanipulation beinhalten würde).

EDIT: Es muss Standard/Portable C sein, plattformspezifische Funktionalität ist hier nicht von Interesse. Ebenfalls, MY_MIN und MY_MAX sind vom gleichen Typ wie der Wert, den ich festklemmen möchte (in den obigen Beispielen verdoppelt).

Sowohl GCC als auch Clang generieren eine schöne Assemblierung für den folgenden einfachen, unkomplizierten, portablen 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

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 (Ret nicht mitgezählt), keine Verzweigungen. Exzellent.

Dies wurde mit GCC 4.7 und Clang 3.2 auf Ubuntu 13.04 mit einem Core i3 M 350 getestet. Nebenbei bemerkt, der einfache C++-Code, der std::min und std::max aufruft, generierte dieselbe Assembly.

Dies ist für Doppel. Und für int erzeugen sowohl GCC als auch Clang eine Assembly mit fünf Anweisungen (ohne ret) und ohne Verzweigungen. Auch ausgezeichnet.

Ich verwende derzeit kein Festkomma, daher werde ich keine Meinung zu Festkomma abgeben.

Alte Frage, aber ich habe heute an diesem Problem gearbeitet (mit Doubles/Floats).

Der beste Ansatz ist die Verwendung von 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-Intrinsic einfach zu verwenden. Sie verleihen eine Leistungssteigerung von mehr als einer Größenordnung im Vergleich zu einer Klemmung mit std::min/max.

Das mag Sie überraschen. Das habe ich auf jeden Fall! Leider verwendet VC++ 2010 einfache Vergleiche für std::min/max, selbst 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++ zu tun:

#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, außer dass stattdessen xxx_sd verwendet wird.

Bearbeiten: Anfangs habe ich die Klemmfunktion wie kommentiert geschrieben. Aber als ich mir die Assembler-Ausgabe ansah, bemerkte ich, dass der VC++-Compiler nicht schlau genug war, um die redundante Bewegung auszumerzen. Eine Anweisung weniger. 🙂

Wenn Ihr Prozessor eine schnelle Anweisung für Absolutwerte hat (wie es der x86 tut), können Sie ein verzweigtes Min und Max ausführen, das schneller ist als ein if Anweisung oder ternäre Operation.

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

Wenn einer der Terme null ist (was beim Klemmen oft der Fall ist), vereinfacht sich der Code etwas weiter:

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

Wenn Sie beide Operationen kombinieren, können Sie die beiden ersetzen /2 zu einem einzigen /4 oder *0.25 um einen Schritt zu sparen.

Der folgende Code ist auf meinem Athlon II X2 über 3x schneller als 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
}

Der ternäre Operator ist wirklich der richtige Weg, da die meisten Compiler in der Lage sind, sie in eine native Hardwareoperation zu kompilieren, die eine bedingte Verschiebung anstelle einer Verzweigung verwendet (und somit die Fehlvorhersage von Strafen und Pipeline-Blasen usw. vermeidet). Eine Bit-Manipulation verursacht wahrscheinlich ein Laden-Hit-Speichern.

Insbesondere PPC und x86 mit SSE2 haben eine Hardware-Operation, die wie folgt als intrinsisch ausgedrückt werden könnte:

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 das Intrinsic verwendet, können Sie es tatsächlich verwenden, um Ihre Klemme 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 Ihnen dringend Vermeiden Sie die Bit-Manipulation von Doubles mit Integer-Operationen. Auf den meisten modernen CPUs gibt es keine direkte Möglichkeit, Daten zwischen Double- und Int-Registern zu verschieben, außer durch einen Roundtrip zum dcache. Dies führt zu einem Datenrisiko, das als Load-Hit-Store bezeichnet wird und die CPU-Pipeline im Wesentlichen leert, bis das Schreiben in den Speicher abgeschlossen ist (normalerweise etwa 40 Zyklen).

Die Ausnahme hiervon ist, wenn die Double-Werte bereits im Speicher und nicht in einem Register sind: In diesem Fall besteht keine Gefahr eines Load-Hit-Store. Ihr Beispiel zeigt jedoch, dass Sie gerade das Double berechnet und von einer Funktion zurückgegeben haben, was bedeutet, dass es sich wahrscheinlich immer noch in XMM1 befindet.

Für die 16.16-Darstellung ist es unwahrscheinlich, dass die einfache ternäre Geschwindigkeit in Bezug auf die Geschwindigkeit übertroffen wird.

Und für Doubles, weil Sie es Standard/Portable C brauchen, wird jede Art von Bit-Fummelei schlecht enden.

Selbst wenn ein bisschen Gefummel möglich wäre (was ich bezweifle), würden Sie sich auf die binäre Darstellung von Doubles verlassen. DIES (und ihre Größe) IST UMSETZUNGSABHÄNGIG.

Möglicherweise könnten Sie dies mit sizeof (double) “erraten” und dann das Layout verschiedener double-Werte mit ihren gemeinsamen binären Darstellungen vergleichen, aber ich denke, Sie verstecken sich vor nichts.

Die beste Regel lautet: SAGEN SIE DEM COMPILER, WAS SIE WOLLEN (dh ternär) und lassen Sie ihn für Sie optimieren.

BEARBEITEN: Bescheidene Kuchenzeit. Ich habe gerade die Idee von Quinmars (unten) getestet und es funktioniert – wenn Sie IEEE-754-Floats haben. Dies ergab eine Beschleunigung von etwa 20 % für den untenstehenden Code. Offensichtlich 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);

Die Bits des IEEE 754-Gleitkommas sind so geordnet, dass Sie beim Vergleich der als Ganzzahl interpretierten Bits dieselben Ergebnisse erhalten, als würden Sie sie direkt als Floats vergleichen. Wenn Sie also einen Weg finden oder kennen, Ganzzahlen zu klemmen, können Sie ihn auch für (IEEE 754) Floats verwenden. Tut mir leid, ich kenne keinen schnelleren Weg.

Wenn Sie die Floats in einem Array gespeichert haben, können Sie einige CPU-Erweiterungen wie SSE3 verwenden, wie rkj sagte. Sie können sich liboil ansehen, es erledigt die ganze Drecksarbeit für Sie. Hält Ihr Programm portabel und verwendet, wenn möglich, schnellere CPU-Anweisungen. (Ich bin mir nicht sicher, wie OS/Compiler-unabhängig liboil ist).

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.