Effiziente Integer-Vergleichsfunktion

Dieses hat keine Verzweigungen und leidet nicht an Überlauf oder Unterlauf:

return (a > b) - (a < b);

Mit gcc -O2 -S werden die folgenden sechs Anweisungen zusammengestellt:

xorl    %eax, %eax
cmpl    %esi, %edi
setl    %dl
setg    %al
movzbl  %dl, %edx
subl    %edx, %eax

Hier finden Sie Code zum Vergleich verschiedener Vergleichsimplementierungen:

#include <stdio.h>
#include <stdlib.h>

#define COUNT 1024
#define LOOPS 500
#define COMPARE compare2
#define USE_Rand 1

int arr[COUNT];

int compare1 (int a, int b)
{
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

int compare2 (int a, int b)
{
    return (a > b) - (a < b);
}

int compare3 (int a, int b)
{
    return (a < b) ? -1 : (a > b);
}

int compare4 (int a, int b)
{
    __asm__ __volatile__ (
        "sub %1, %0 \n\t"
        "jno 1f \n\t"
        "cmc \n\t"
        "rcr %0 \n\t"
        "1: "
    : "+r"(a)
    : "r"(b)
    : "cc");
    return a;
}

int main ()
{
    for (int i = 0; i < COUNT; i++) {
#if USE_Rand
        arr[i] = Rand();
#else
        for (int b = 0; b < sizeof(arr[i]); b++) {
            *((unsigned char *)&arr[i] + b) = Rand();
        }
#endif
    }

    int sum = 0;

    for (int l = 0; l < LOOPS; l++) {
        for (int i = 0; i < COUNT; i++) {
            for (int j = 0; j < COUNT; j++) {
                sum += COMPARE(arr[i], arr[j]);
            }
        }
    }

    printf("%d=0\n", sum);

    return 0;
}

Die Ergebnisse meines 64-Bit-Systems, zusammengestellt mit gcc -std=c99 -O2, für positive ganze Zahlen (USE_Rand=1):

compare1: 0m1.118s
compare2: 0m0.756s
compare3: 0m1.101s
compare4: 0m0.561s

Von den C-Only-Lösungen war die von mir vorgeschlagene die schnellste. Die Lösung von user315052 war langsamer, obwohl nur 5 Anweisungen erstellt wurden. Die Verlangsamung ist wahrscheinlich, weil es eine bedingte Anweisung gibt (cmovge), obwohl eine Anweisung weniger vorhanden ist.

Insgesamt war die Implementierung von FredOverflow mit 4 Anweisungen für Assembly am schnellsten, wenn positive Ganzzahlen verwendet wurden. Dieser Code hat jedoch nur den ganzzahligen Bereich Rand_MAX verglichen, sodass der Test mit 4 Instanzen voreingenommen ist, da er Überläufe separat behandelt, und diese treten im Test nicht auf. Die Geschwindigkeit kann auf eine erfolgreiche Verzweigungsvorhersage zurückzuführen sein.

Mit einer ganzen Reihe von Ganzzahlen (USE_Rand=0) ist die 4-Befehls-Lösung tatsächlich sehr langsam (andere sind gleich):

compare4: 0m1.897s

Okay, ich habe es auf vier Anweisungen gebracht :) Die Grundidee lautet wie folgt:

Die Hälfte der Zeit ist der Unterschied klein genug, um in eine ganze Zahl zu passen. In diesem Fall geben Sie einfach die Differenz zurück. Andernfalls verschieben Sie die Nummer eins nach rechts. Die entscheidende Frage ist, welches Bit sich dann in das MSB bewegen soll.

Schauen wir uns zwei extreme Beispiele an, die der Einfachheit halber 8 Bit anstelle von 32 Bit verwenden:

 10000000 INT_MIN
 01111111 INT_MAX
---------
000000001 difference
 00000000 shifted

 01111111 INT_MAX
 10000000 INT_MIN
---------
111111111 difference
 11111111 shifted

Das Verschieben des Übertragsbits in würde den Wert 0 für den ersten Fall ergeben (obwohl INT_MIN nicht gleich INT_MAX ist) und eine negative Zahl für den zweiten Fall (obwohl INT_MAX nicht kleiner als INT_MIN ist).

Wenn wir jedoch das Übertragsbit umdrehen, erhalten wir vernünftige Zahlen:

 10000000 INT_MIN
 01111111 INT_MAX
---------
000000001 difference
100000001 carry flipped
 10000000 shifted

 01111111 INT_MAX
 10000000 INT_MIN
---------
111111111 difference
011111111 carry flipped
 01111111 shifted

Ich bin sicher, es gibt einen tiefen mathematischen Grund, warum es Sinn macht, das Übertragsstück umzudrehen, aber ich sehe es noch nicht.

int compare_int(int a, int b)
{
    __asm__ __volatile__ (
        "sub %1, %0 \n\t"
        "jno 1f \n\t"
        "cmc \n\t"
        "rcr %0 \n\t"
        "1: "
    : "+r"(a)
    : "r"(b)
    : "cc");
    return a;
}

Ich habe den Code mit einer Million zufälligen Eingaben getestet und jede Kombination von INT_MIN, -INT_MAX, INT_MIN/2, -1, 0, 1, INT_MAX/2, INT_MAX/2 + 1, INT_MAX. Alle Tests bestanden. Kannst du mich falsch beweisen?

Für das, was es wert ist, habe ich eine SSE2-Implementierung zusammengestellt. vec_compare1 verwendet den gleichen Ansatz wie compare2, erfordert jedoch nur drei arithmetische SSE2-Anweisungen:

#include <stdio.h>
#include <stdlib.h>
#include <emmintrin.h>

#define COUNT 1024
#define LOOPS 500
#define COMPARE vec_compare1
#define USE_Rand 1

int arr[COUNT] __attribute__ ((aligned(16)));

typedef __m128i vSInt32;

vSInt32 vec_compare1 (vSInt32 va, vSInt32 vb)
{
    vSInt32 vcmp1 = _mm_cmpgt_epi32(va, vb);
    vSInt32 vcmp2 = _mm_cmpgt_epi32(vb, va);
    return _mm_sub_epi32(vcmp2, vcmp1);
}

int main ()
{
    for (int i = 0; i < COUNT; i++) {
#if USE_Rand
        arr[i] = Rand();
#else
        for (int b = 0; b < sizeof(arr[i]); b++) {
            *((unsigned char *)&arr[i] + b) = Rand();
        }
#endif
    }

    vSInt32 vsum = _mm_set1_epi32(0);

    for (int l = 0; l < LOOPS; l++) {
        for (int i = 0; i < COUNT; i++) {
            for (int j = 0; j < COUNT; j+=4) {
                vSInt32 v1 = _mm_loadu_si128(&arr[i]);
                vSInt32 v2 = _mm_load_si128(&arr[j]);
                vSInt32 v = COMPARE(v1, v2);
                vsum = _mm_add_epi32(vsum, v);
            }
        }
    }

    printf("vsum = %vd\n", vsum);

    return 0;
}

Zeit dafür ist 0.137s.

Die Zeit für Compare2 mit derselben CPU und demselben Compiler beträgt 0,674 Sekunden.

Daher ist die SSE2-Implementierung wie erwartet etwa viermal schneller (da es sich um eine 4-breite SIMD handelt).

Dieser Code hat keine Verzweigungen und verwendet 5 Anweisungen. Bei aktuellen Intel-Prozessoren können andere branchenlose Alternativen übertroffen werden, bei denen cmov * -Anweisungen recht teuer sind. Nachteil ist ein nicht symmetrischer Rückgabewert (INT_MIN + 1, 0, 1).

int compare_int (int a, int b)
{
    int res;

    __asm__ __volatile__ (
        "xor %0, %0 \n\t"
        "cmpl %2, %1 \n\t"
        "setl %b0 \n\t"
        "rorl $1, %0 \n\t"
        "setnz %b0 \n\t"
    : "=q"(res)
    : "r"(a)
    , "r"(b)
    : "cc"
    );

    return res;
}

Diese Variante benötigt keine Initialisierung, daher werden nur 4 Anweisungen verwendet:

int compare_int (int a, int b)
{
    __asm__ __volatile__ (
        "subl %1, %0 \n\t"
        "setl %b0 \n\t"
        "rorl $1, %0 \n\t"
        "setnz %b0 \n\t"
    : "+q"(a)
    : "r"(b)
    : "cc"
    );

    return a;
}

Vielleicht können Sie die folgende Idee verwenden (in Pseudo-Code; Asm-Code wurde nicht geschrieben, weil ich mit der Syntax nicht vertraut bin):

1. Zahlen abziehen (result = a - b)
2. Wenn kein Überlauf, fertig (jo Anweisungen und Verzweigungsvorhersage sollten hier sehr gut funktionieren)
3. Wenn es einen Überlauf gab, verwenden Sie eine robuste Methode (return (a < b) ? -1 : (a > b))

Bearbeiten: zur Vereinfachung: Wenn es einen Überlauf gab, drehen Sie das Vorzeichen des Ergebnisses anstelle von Schritt 3.