Schnellste Weg, um einen realen (fest / Gleitkomma) Wert zu klemmen?

StackOverflow https://stackoverflow.com/questions/427477

Frage

Gibt es eine effizientere Art und Weise reelle Zahlen zu klemmen, als wenn Aussagen oder ternäre Operatoren? Ich möchte dies verdoppelt, beides tun und für ein 32-Bit-Fixpoint Implementierung (16.16). Ich bin nicht für Code zu stellen, die beide Fälle behandeln können; sie werden in separaten Funktionen behandelt werden.

Natürlich, ich kann 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 verwendet werden.

Dies wird in einem leistungskritischen Teil des Codes getan, also suche ich nach einem so effizient wie möglich davon zu tun (was ich würde bedeuten, Bit-Manipulation vermuten)

EDIT: Es verfügt über Standard / portable C, plattformspezifische Funktionalität ist hier nicht von Interesse. Auch MY_MIN und MY_MAX sind vom gleichen Typ wie der Wert I geklemmten (Doppel in den obigen Beispielen) werden soll.

War es hilfreich?

Lösung

Für die 16.16 Darstellung, die einfache ternäre ist unwahrscheinlich, dass bettered Geschwindigkeit her.

Und für Doppelzimmer, weil Sie es Standard / portable C, Bit-Fiedeln jeglicher Art böse enden.

Auch wenn ein bisschen-Geige möglich war (was ich bezweifle), dann würden Sie auf der Binärdarstellung verdoppelt werden angewiesen zu sein. THIS (und deren Größe) ist die Umsetzung abhängig.

Vielleicht könnten Sie „erraten“ dies mit sizeof (double) und dann das Layout der verschiedenen Doppel Werte gegen den gemeinsamen binären Darstellungen zu vergleichen, aber ich denke, Sie auf ein Versteck zu nichts passiert.

Die beste Regel ist der Compiler sagen, was Sie wollen (dh ternäre) und lassen Sie es für Sie optimieren.

EDIT: Humble Pie Zeit. Ich quinmars Idee gerade getestet (siehe unten), und es funktioniert - wenn Sie IEEE-754 Schwimmer haben. Dies ergab eine Beschleunigung von etwa 20% auf den Code unten. IObviously nicht tragbar, aber ich denke, es zu fragen, den Compiler eine standardisierte Art und Weise sein kann, wenn es 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);

Andere Tipps

Alte Frage, aber ich war an diesem Problem arbeiten heute (mit Doppel / Schwimmer).

Der beste Ansatz ist SSE MinSS / MAXSS für Schwimmer und SSE2 MINSD / MAXSD für die Doppel zu verwenden. Dies sind branchless und nehmen einen Taktzyklus jeder, und sind einfach zu bedienen dank verwenden intrinsics Compiler. Sie verleihen mehr als eine Größenordnung Leistungssteigerung im Vergleich zu Spann mit std :: min / max.

Sie können von diesem überraschend finden. Ich habe auf jeden Fall! Leider VC ++ 2010 verwendet einfache Vergleiche für std :: min / max, auch wenn / arch: SSE2 und / FP: schnell aktiviert sind. Ich kann nicht für andere Compiler sprechen.

Hier ist der notwendige Code 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 doppelte Genauigkeit Code ist gleich, außer mit xxx_sd statt.

Edit: Zunächst schrieb ich die Klemmfunktion als kommentiert. Aber ein Blick auf die Assembler-Ausgabe stellte ich fest, dass die VC ++ Compiler nicht klug genug war, um die redundante Bewegung keulen. Eine weniger Anweisung. :)

Sowohl GCC und Klappern erzeugen schöne Anordnung 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 Befehle (nicht ret mitgezählt), keine Verzweigungen. Ausgezeichnet.

Dies wurde mit GCC 4.7 getestet und klirrt 3.2 auf Ubuntu 13.04 mit einem Core i3 M 350. Auf einer Seite zur Kenntnis, ruft der einfache C ++ Code std :: min und std :: max die gleiche Anordnung erzeugt wird.

Dies ist für Doppelzimmer. Und für int sowohl GCC und Klappern erzeugen Baugruppe mit fünf Befehle (nicht ret mitgezählt) und keine Filialen. Auch hervorragend.

ich derzeit nicht verwenden Festkomma, also werde ich keine Stellungnahme zu Festpunkt.

Wenn Ihr Prozessor eine schnelle Anweisung zum Absolutwert hat (wie die x86 Fall ist), können Sie einen branchless min und max tun, die schneller als eine if Anweisung oder ternärer Betrieb sein werden. 

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

Wenn eine der Bedingungen ist Null (wie es oft der Fall, wenn Sie Klemm) vereinfacht den Code ein bisschen weiter: 

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

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

Der folgende Code ist über 3x schneller als ternäres auf meinem Athlon II X2, bei der Verwendung der Optimierung für FMIN = 0 ist. 

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
}

Ternary Operator ist wirklich der Weg zu gehen, weil die meisten Compiler sind in der Lage, sie in eine native Hardware-Operation zu kompilieren, die eine bedingte Bewegung anstelle einer Verzweigung verwendet (und damit vermeiden die falsche Vorhersage Strafe und Pipeline-Blasen und so weiter). Bit-Manipulation ist wahrscheinlich ein Last-Hit-store verursachen.

Insbesondere PPC und x86 mit SSE2 haben eine Hardware-op, die als intrinsisch etwas wie folgt ausgedrückt werden: 

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

Der Vorteil ist, dass es das tut in der Pipeline, ohne einen Zweig zu verursachen. In der Tat, wenn Sie Compiler die intrinsischen verwendet, können Sie es verwenden, um Ihre Klammer zu implementieren direkt: 

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

ich stark vorschlagen, dass Sie vermeiden Bit-Manipulation von Doppel Integer-Operationen mit . Auf den meisten modernen CPUs gibt es keine direkte Möglichkeit, Daten zwischen Doppel- und int Register außer, indem sie eine Hin- und Rückfahrt zum dcache bewegen. Dies wird eine Datum Gefahr bei einem Last-Hit-Speicher genannt, die im Grunde die CPU-Pipeline entleert, bis der Speicher-Schreib (in der Regel etwa 40 Zyklen oder so) abgeschlossen hat.

Die Ausnahme ist, wenn die Doppel Werte bereits im Speicher sind und nicht in einem Register: In diesem Fall besteht keine Gefahr eines Last-Hit-Speichers. Jedoch Ihr Beispiel zeigt, Sie haben gerade die doppelte berechnet und gaben es aus einer Funktion, die es wahrscheinlich noch seine in XMM1 bedeutet.

Die Bits von IEEE 754 Gleitkomma sind so angeordnet, dass, wenn Sie die Bits als Integer interpretiert vergleichen Sie die gleichen Ergebnisse erhalten, wie wenn man sie als Schwimmer direkt vergleichen würde. Also, wenn Sie einen Weg finden, oder wissen, ganze Zahlen klemmen Sie es für (IEEE 754) schwimmt auch nutzen können. Sorry, ich weiß nicht, einen schnelleren Weg.

Wenn Sie die in einem Arrays gespeichert Schwimmern Sie betrachten können einige CPU-Erweiterungen wie SSE3 zu verwenden, wie gesagt RKJ. Sie können einen Blick auf liboil es tut all die schmutzige Arbeit für Sie. Hält Ihr Programm tragbar und verwendet schnelle CPU-Anweisungen, wenn möglich. (Ich bin nicht sicher, tho, wie O / Compiler-unabhängigen liboil ist).

Anstatt die Prüfung und die Verzweigung, die ich normalerweise dieses Format zum Klemmen verwenden: 

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

Obwohl ich habe noch nie eine Performance-Analyse auf dem kompilierten Code.

Realistisch betrachtet, wird kein anständiger Compiler einen Unterschied zwischen einer if () Aussage machen und einem: Ausdruck. Der Code ist einfach genug, dass sie in der Lage sein werden, die möglichen Wege zu entdecken. Das heißt, Ihre beiden Beispiele sind nicht identisch. Der entsprechende Code verwenden:? Wäre 

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

als dass der A MAX vermeiden. Nun könnte das einen Unterschied machen, wie der Compiler sonst müßte die Beziehung zwischen den beiden Tests vor Ort.

Wenn Klemm selten ist, können Sie die Notwendigkeit testen mit einem einzigen Test zu klemmen: 

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

z. mit MIN = 6 und MAX = 10, wird dies zunächst einen um 8 verschieben, dann prüfen, ob es zwischen -2 und +2 liegt. Ob dies alles spart hängt viel von den relativ Kosten der Verzweigung.

Hier ist eine möglicherweise schnellere Implementierung ähnlich wie @ Roddy Antwort : 

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 die Mindest Berechnen (min) oder maximale ( max) zweier ganzer Zahlen ohne Verzweigung und Gleitkommazahlen Vergleich

  

Die IEEE float und double-Formate waren   so ausgelegt, dass die Zahlen sind   „Lexikographisch geordnet“, die -   in den Worten von IEEE Architekten William   Kahan bedeutet „wenn zwei Gleitkommazahlen   Zahlen im gleichen Format bestellt   (Sagen wir x

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

habe ich versucht, den SSE-Ansatz, diese selbst und die Anordnung Ausgang sah ziemlich viel saubere, also war ich zunächst ermutigt, aber nachdem es tausende Male Timing, war es eigentlich ziemlich viel langsamer. Es sieht in der Tat wie der VC ++ Compiler nicht intelligent genug, um zu wissen, was Sie wirklich wollen, und es scheint, die Dinge hin und her zwischen den XMM Register und Speicher, wenn es sollte nicht zu bewegen. Das heißt, ich weiß nicht, warum der Compiler nicht intelligent genug ist, um die SSE min / max Anweisungen auf dem ternären Operator zu verwenden, wenn es scheint sowieso SSE-Befehle für alle Floating-Point-Berechnungen zu verwenden. Auf der anderen Seite, wenn Sie für PowerPC sind kompilieren, können Sie die FSEL intrinsische auf den FP-Register verwenden, und es ist viel schneller.

Wenn ich richtig verstehe, Sie einen Wert zu begrenzen, „a“ auf einen Bereich zwischen MY_MIN und MY_MAX. Die Art der „a“ ist eine doppelte. Sie haben nicht die Art von MY_MIN oder MY_MAX angeben.

Der einfache Ausdruck: 

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

sollte es tun.

Ich denke, es kann eine kleine Optimierung vorgenommen werden, wenn MY_MAX und MY_MIN passieren ganze Zahlen sein: 

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

Durch die Änderung Vergleiche auf Integer ist es möglich, Sie könnten einen leichten Geschwindigkeitsvorteil erhalten.

Wenn Sie wollen schnell Absolutwert Anweisungen verwenden, lesen Sie in diesem snipped von Code, den ich in Minicomputer , die einen Schwimmer auf den Bereich klemmt [0,1] 

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

(I vereinfacht den Code ein wenig). Wir denken kann es zwei Werte als Einnahme, ein reflektiertes> 0 

fabs(x)

und die andere reflektiert etwa 1,0 bis sein <1,0 

1.0-fabs(x-1.0)

Und wir nehmen den Durchschnitt von ihnen. Wenn es sich in Reichweite ist, dann werden beide Werte gleich wie x, also wieder ihre durchschnittliche x sein wird. Wenn es außerhalb des Bereichs liegt, dann einer der Werte wird x, und das andere x wird über die „Grenze“ Punkt gekippt, so dass ihre durchschnittliche genau der Grenzpunkt sein wird.

Wie bereits erwähnt, fmin / fmax Funktionen funktionieren gut (in gcc, mit -ffast-math). Obwohl gfortran hat Muster IA Anweisungen max / min, g entsprechend verwenden ++ nicht der Fall ist. In icc muss man stattdessen std :: min / max, weil icc nicht kurz Schneiden der Spezifikation, wie fmin / fmax Arbeit mit nicht-finite Operanden erlaubt.

Mein 2 Cent in C ++. Wahrscheinlich nicht anders als ternäre Operatoren und hoffentlich kein Verzweigungscode erzeugt 

template <typename T>
inline T clamp(T val, T lo, T hi) {
    return std::max(lo, std::min(hi, val));
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top