Schnellster Weg, um festzustellen, ob eine ganze Zahl zwischen zwei ganzen Zahlen (einschließlich) mit bekannten Wertemengen liegt

Question

Gibt es einen schnelleren Weg als x >= start && x <= end in C oder C++, um zu testen, ob eine Ganzzahl zwischen zwei Ganzzahlen liegt?

UPDATE: Mein spezifisches Betriebssystem ist iOS. Dies ist Teil einer Feldunschärfe-Funktion, die Pixel auf einen Kreis in einem gegebenen Quadrat beschränkt.

UPDATE: Nachdem ich die akzeptierte Antwort ausprobiert habe, erzielte ich eine Geschwindigkeitssteigerung um eine Größenordnung bei einer Codezeile gegenüber der normalen Art des Testens x >= start && x <= end.

UPDATE: Hier ist der Code nach und vorher mit Assembler aus 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-Neuladen
 ldr    r1, [sp, #164] @ 4-Byte-Neuladen
 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-Neuladen
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-Byte-Neuladen
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Ziemlich erstaunlich, wie eine Reduzierung oder Eliminierung von Verzweigungen eine so dramatische Geschwindigkeitssteigerung bewirken kann.

Answer 1

Es gibt einen alten Trick, um dies mit nur einem Vergleichszweig zu tun. Ob es wirklich die Geschwindigkeit verbessern wird, ist vielleicht fraglich, und selbst wenn ja, dürfte es zu gering sein, um bemerkt oder beachtet zu werden. Aber wenn Sie nur mit zwei Vergleichen beginnen, sind die Chancen auf eine enorme Verbesserung ziemlich gering. Der Code sieht wie folgt aus:

// benutze ein < für eine inklusive untere Grenze und exklusive obere Grenze
// benutze <= für eine inklusive untere Grenze und obere obere Grenze
// alternativ, wenn die obere Grenze inklusiv ist und du upper-lower vorberechnen kannst
//  addiere einfach +1 zu upper-lower und benutze den < Operator
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

Mit einem typischen, modernen Computer (d. h. alles, was Zweierkomplemente verwendet), ist die Konvertierung in eine vorzeichenlose Zahl wirklich ein no-op - nur eine Änderung, wie die gleichen Bits betrachtet werden.

Beachten Sie, dass Sie in einem typischen Fall upper-lower außerhalb einer (angenommenen) Schleife vorberechnen können, so dass dies normalerweise keine signifikante Zeit erfordert. Neben der Reduzierung der Anzahl von Zweigbefehlen verbessert dies auch (im Allgemeinen) die Zweigvorhersage. In diesem Fall wird derselbe Zweig genommen, ob die Nummer unterhalb des unteren Endes oder über dem oberen Ende des Bereichs liegt.

Was die Funktionsweise betrifft, ist die Grundidee ziemlich einfach: Eine negative Zahl, wenn sie als vorzeichenlose Zahl betrachtet wird, wird größer sein als alles, was als positive Zahl begonnen hat.

In der Praxis übersetzt diese Methode number und das Intervall zum Ursprungspunkt und überprüft, ob number im Intervall [0, D] liegt, wobei D = upper - lower. Wenn number unterhalb der unteren Grenze ist: negativ, und wenn oberhalb der oberen Grenze: größer als D.

Answer 2

Es ist selten, signifikante Optimierungen am Code in einem so kleinen Maßstab vornehmen zu können. Große Leistungsgewinne ergeben sich aus der Beobachtung und Modifizierung des Codes auf einer höheren Ebene. Möglicherweise können Sie die Notwendigkeit des Bereichstests vollständig eliminieren oder nur O(n) davon anstelle von O(n^2) durchführen. Möglicherweise können Sie die Tests neu anordnen, sodass eine Seite der Ungleichung immer impliziert ist. Selbst wenn der Algorithmus ideal ist, sind Gewinne wahrscheinlicher, wenn Sie sehen, wie dieser Code den Bereichstest 10 Millionen Mal durchführt, und einen Weg finden, sie zu stapeln und SSE zu verwenden, um viele Tests parallel durchzuführen.

Answer 3

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

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

Wenn Sie dies für eine sehr begrenzte Reihe von Werten tun, könnten Sie eine Lookup-Tabelle erstellen. Das Indizieren könnte teurer sein, aber wenn Sie die gesamte Tabelle im Cache speichern können, können Sie alle Verzweigungen aus dem Code entfernen, was die Dinge beschleunigen sollte.

Für Ihre Daten wäre die Lookup-Tabelle 128^3 = 2.097.152. Wenn Sie eine der drei Variablen kontrollieren können, sodass Sie alle Instanzen berücksichtigen, bei denen start = N zur gleichen Zeit ist, dann sinkt die Größe des Arbeitsbereichs auf 128^2 = 16432 Bytes, was in die meisten modernen Caches passen sollte.

Sie müssten den tatsächlichen Code immer noch benchmarken, um festzustellen, ob eine verzweigungsfreie Lookup-Tabelle ausreicht schneller als die offensichtlichen Vergleiche.

Answer 4

Für jede Variablenbereichsprüfung:

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

Es ist schneller, Bit-Operationen zu verwenden:

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

Dadurch werden zwei Verzweigungen auf eine reduziert.

Wenn Sie auf den Typ achten:

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

Sie können mehrere Variablenbereichsprüfungen kombinieren:

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

Dadurch werden 4 Verzweigungen auf 1 reduziert.

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

Answer 5

Diese Antwort dient dazu, über einen Test mit der akzeptierten Antwort zu berichten. Ich führte einen geschlossenen Bereichstest an einem großen Vektor von sortierten Zufallszahlen durch und zu meiner Überraschung ist die Grundmethode ( low <= num && num <= high) tatsächlich schneller als die obige akzeptierte Antwort! Der Test wurde auf einem HP Pavilion g6 (AMD A6-3400APU mit 6GB RAM) durchgeführt. Hier ist der Kerncode, der für den Test verwendet wurde:

int num = rand();  // num zum Vergleich in aufeinanderfolgenden Bereichen.
chrono::time_point 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 elapsed_s1 = end - start;

im Vergleich dazu steht folgendes, was die oben akzeptierte Antwort ist:

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

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