Der schnellste Weg, um festzustellen, ob eine Ganzzahl zwischen zwei Ganzzahlen (einschließlich) mit bekannten Wertesätzen liegt

389

Gibt es eine schnellere Möglichkeit als x >= start && x <= endin C oder C ++ zu testen, ob eine Ganzzahl zwischen zwei Ganzzahlen liegt?

UPDATE : Meine spezifische Plattform ist iOS. Dies ist Teil einer Box-Unschärfe-Funktion, die Pixel auf einen Kreis in einem bestimmten Quadrat beschränkt.

UPDATE : Nachdem ich die akzeptierte Antwort ausprobiert hatte , erhielt ich in der einen Codezeile eine Beschleunigung um eine Größenordnung, weil ich es auf normale x >= start && x <= endWeise gemacht hatte.

UPDATE : Hier ist der After- und Before-Code mit Assembler von XCode:

NEUER WEG

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

ALTER WEG

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Es ist ziemlich erstaunlich, wie das Reduzieren oder Eliminieren von Verzweigungen eine solch dramatische Beschleunigung bewirken kann.

jjxtra
quelle
28
Warum machst du dir Sorgen, dass dir das nicht schnell genug ist?
Matt Ball
90
Wen interessiert es warum, es ist eine interessante Frage. Es ist nur eine Herausforderung für eine Herausforderung.
David sagt Reinstate Monica
46
@SLaks Also sollten wir all diese Fragen einfach blind ignorieren und einfach sagen "Lass den Optimierer das machen?"
David sagt Reinstate Monica
87
Es spielt keine Rolle, warum die Frage gestellt wird. Es ist eine gültige Frage, auch wenn die Antwort nein ist
tay10r
41
Dies ist ein Engpass in einer Funktion in einer meiner Apps
jjxtra

Antworten:

527

Es gibt einen alten Trick, dies mit nur einem Vergleich / Zweig zu tun. Ob es die Geschwindigkeit wirklich verbessert, ist möglicherweise fraglich, und selbst wenn dies der Fall ist, ist es wahrscheinlich zu wenig, um es zu bemerken oder sich darum zu kümmern, aber wenn Sie nur mit zwei Vergleichen beginnen, sind die Chancen für eine enorme Verbesserung ziemlich gering. Der Code sieht aus wie:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

Bei einem typischen, modernen Computer (dh bei allem, was ein Zweierkomplement verwendet) ist die Konvertierung in vorzeichenloses nicht wirklich - nur eine Änderung in der Art und Weise, wie dieselben Bits angezeigt werden.

Beachten Sie, dass Sie in einem typischen Fall upper-loweraußerhalb einer (vermuteten) Schleife vorberechnen können , sodass normalerweise keine nennenswerte Zeit zur Verfügung steht. Dies verbessert nicht nur die Anzahl der Verzweigungsbefehle, sondern verbessert auch (im Allgemeinen) die Verzweigungsvorhersage. In diesem Fall wird derselbe Zweig verwendet, unabhängig davon, ob die Zahl unter dem unteren Ende oder über dem oberen Ende des Bereichs liegt.

Wie dies funktioniert, ist die Grundidee ziemlich einfach: Eine negative Zahl ist, wenn sie als vorzeichenlose Zahl betrachtet wird, größer als alles, was als positive Zahl begann.

In der Praxis übersetzt diese Methode numberdas Intervall zum Ursprungspunkt und prüft, ob numberes sich in dem Intervall befindet [0, D], in dem D = upper - lower. Wenn numberunterhalb der Untergrenze: negativ , und wenn oberhalb der Obergrenze: größer alsD .

Jerry Sarg
quelle
8
@ TomásBadan: Sie werden beide einen Zyklus auf jeder vernünftigen Maschine sein. Was teuer ist, ist die Filiale.
Oliver Charlesworth
3
Zusätzliche Verzweigung erfolgt durch Kurzschluss? Wenn dies der Fall ist, würde lower <= x & x <= upper(statt lower <= x && x <= upper) auch zu einer besseren Leistung führen?
Markus Mayr
6
@ AK4749, jxh: So cool dieses Nugget auch ist, ich zögere, es zu verbessern, da es leider nichts gibt, was darauf hindeutet, dass dies in der Praxis schneller ist (bis jemand einen Vergleich der resultierenden Assembler- und Profilinformationen durchführt). Nach allem, was wir wissen, kann der OP-Compiler den OP-Code mit einem einzigen Zweig-Opcode rendern ...
Oliver Charlesworth
152
BEEINDRUCKEND!!! Dies führte zu einer Verbesserung um eine Größenordnung in meiner App für diese bestimmte Codezeile. Durch die Vorberechnung von oben nach unten stieg meine Profilerstellung von 25% der Zeit dieser Funktion auf weniger als 2%! Engpass ist jetzt Additions- und Subtraktionsoperationen, aber ich denke, es könnte jetzt gut genug sein :)
jjxtra
28
Ah, jetzt hat der @PsychoDad die Frage aktualisiert, es ist klar, warum dies schneller ist. Der reale Code hat einen Nebeneffekt im Vergleich, weshalb der Compiler den Kurzschluss nicht optimieren konnte.
Oliver Charlesworth
17

Es ist selten möglich, signifikante Optimierungen für Code in so kleinem Maßstab vorzunehmen. Große Leistungssteigerungen ergeben sich aus der Beobachtung und Änderung des Codes von einer höheren Ebene aus. Möglicherweise können Sie die Notwendigkeit des Bereichstests ganz beseitigen oder nur O (n) anstelle von O (n ^ 2) ausführen. Möglicherweise können Sie die Tests neu anordnen, sodass immer eine Seite der Ungleichung impliziert ist. Selbst wenn der Algorithmus ideal ist, ist es wahrscheinlicher, dass Gewinne erzielt werden, wenn Sie sehen, wie dieser Code den Bereichstest 10 Millionen Mal durchführt, und Sie einen Weg finden, sie zu stapeln und SSE zu verwenden, um viele Tests parallel durchzuführen.

Ben Jackson
quelle
16
Trotz der Abstimmungen stehe ich zu meiner Antwort: Die generierte Assembly (siehe den Pastebin-Link in einem Kommentar zur akzeptierten Antwort) ist für etwas in der inneren Schleife einer Pixelverarbeitungsfunktion ziemlich schrecklich. Die akzeptierte Antwort ist ein ordentlicher Trick, aber ihre dramatische Wirkung geht weit über das hinaus, was zu erwarten ist, um einen Bruchteil eines Zweigs pro Iteration zu eliminieren. Ein sekundärer Effekt dominiert, und ich gehe immer noch davon aus, dass ein Versuch, den gesamten Prozess über diesen einen Test hinweg zu optimieren, die Vorteile eines cleveren Bereichsvergleichs im Staub belassen würde.
Ben Jackson
17

Dies hängt davon ab, wie oft Sie den Test für dieselben Daten durchführen möchten.

Wenn Sie den Test einmal durchführen, gibt es wahrscheinlich keine sinnvolle Möglichkeit, den Algorithmus zu beschleunigen.

Wenn Sie dies für einen sehr endlichen Satz von Werten tun, können Sie eine Nachschlagetabelle erstellen. Das Durchführen der Indizierung ist möglicherweise teurer. Wenn Sie jedoch die gesamte Tabelle in den Cache einfügen können, können Sie alle Verzweigungen aus dem Code entfernen, was die Arbeit beschleunigen sollte.

Für Ihre Daten wäre die Nachschlagetabelle 128 ^ 3 = 2.097.152. Wenn Sie eine der drei Variablen steuern können, berücksichtigen Sie alle Fälle, in denenstart = N gleichzeitig , sinkt die Größe des Arbeitssatzes auf128^2 = 16432 Bytes, was in die meisten modernen Caches gut passen sollte.

Sie müssten immer noch den tatsächlichen Code vergleichen, um festzustellen, ob eine verzweigungslose Nachschlagetabelle ausreichend schneller ist als die offensichtlichen Vergleiche.

Andrew Prock
quelle
Sie würden also eine Art Suche mit einem Wert, Start und Ende speichern und ein BOOL enthalten, das Ihnen sagt, ob es dazwischen liegt?
jjxtra
Richtig. Es wäre eine 3D-Nachschlagetabelle : bool between[start][end][x]. Wenn Sie wissen, wie Ihr Zugriffsmuster aussehen wird (z. B. x nimmt monoton zu), können Sie die Tabelle so gestalten, dass die Lokalität erhalten bleibt, auch wenn die gesamte Tabelle nicht in den Speicher passt.
Andrew Prock
Ich werde sehen, ob ich diese Methode ausprobieren und sehen kann, wie es geht. Ich habe vor, dies mit einem Bitvektor pro Zeile zu tun, bei dem das Bit gesetzt wird, wenn sich der Punkt im Kreis befindet. Denken Sie, das ist schneller als ein Byte oder int32 gegenüber der Bitmaskierung?
jjxtra
2

Diese Antwort soll über einen Test berichten, der mit der akzeptierten Antwort durchgeführt wurde. Ich habe einen Closed-Range-Test mit einem großen Vektor sortierter zufälliger Ganzzahlen durchgeführt und zu meiner Überraschung ist die grundlegende Methode von (niedrig <= num && num <= hoch) tatsächlich schneller als die oben akzeptierte Antwort! Der Test wurde mit HP Pavilion g6 (AMD A6-3400APU mit 6 GB RAM) durchgeführt. Hier ist der Kerncode, der zum Testen verwendet wird:

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

verglichen mit der folgenden, die oben akzeptierte Antwort ist:

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

Achten Sie darauf, dass randVec ein sortierter Vektor ist. Für jede Größe von MaxNum schlägt die erste Methode die zweite auf meinem Computer!

rezeli
quelle
1
Meine Daten sind nicht sortiert und meine Tests befinden sich auf der iPhone-Arm-CPU. Ihre Ergebnisse mit unterschiedlichen Daten und CPU können abweichen.
jjxtra
In meinem Test wurde nur sortiert, um sicherzustellen, dass die Obergrenze nicht kleiner als die Untergrenze ist.
Rezeli
1
Sortierte Zahlen bedeuten, dass die Verzweigungsvorhersage sehr zuverlässig ist und alle Verzweigungen bis auf einige wenige an den Umschaltpunkten richtig sind. Der Vorteil von verzweigtem Code besteht darin, dass diese Art von Fehlvorhersagen für unvorhersehbare Daten beseitigt werden.
Andreas Klebinger
0

Für jede Überprüfung des variablen Bereichs:

if (x >= minx && x <= maxx) ...

Die Bitoperation ist schneller:

if ( ((x - minx) | (maxx - x)) >= 0) ...

Dadurch werden zwei Zweige zu einem.

Wenn Sie sich für typsicher interessieren:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

Sie können mehrere variable Bereichsprüfungen miteinander kombinieren:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

Dadurch werden 4 Zweige zu 1.

Es ist 3,4-mal schneller als das alte in gcc:

Geben Sie hier die Bildbeschreibung ein

skywind3000
quelle
-4

Ist es nicht möglich, nur eine bitweise Operation für die Ganzzahl durchzuführen?

Da es zwischen 0 und 128 liegen muss, ist es, wenn das 8. Bit gesetzt ist (2 ^ 7), 128 oder mehr. Der Randfall wird jedoch ein Schmerz sein, da Sie einen umfassenden Vergleich wünschen.

Eiswasser
quelle
3
Er will wissen ob x <= end, wo end <= 128. Nicht x <= 128.
Ben Voigt
1
Diese Aussage " Da es zwischen 0 und 128 liegen muss, wenn das 8. Bit gesetzt ist (2 ^ 7), ist es 128 oder mehr " ist falsch. Betrachten Sie 256.
Happy Green Kid Nickerchen
1
Ja, anscheinend habe ich das nicht genug durchdacht. Es tut uns leid.
Eiswasser