wake-up-neo.com

Effiziente Integer-Vergleichsfunktion

Die Funktion compare ist eine Funktion, die zwei Argumente a und b verwendet und eine Ganzzahl zurückgibt, die ihre Reihenfolge beschreibt. Wenn a kleiner als b ist, ist das Ergebnis eine negative ganze Zahl. Wenn a größer als b ist, ist das Ergebnis eine positive ganze Zahl. Ansonsten sind a und b gleich und das Ergebnis ist Null.

Diese Funktion wird häufig zum Parametrieren von Sortier- und Suchalgorithmen aus Standardbibliotheken verwendet.

Die Implementierung der compare-Funktion für Zeichen ist ziemlich einfach. Sie subtrahieren einfach die Argumente:

int compare_char(char a, char b)
{
    return a - b;
}

Dies funktioniert, da angenommen wird, dass der Unterschied zwischen zwei Zeichen in eine Ganzzahl passt. (Beachten Sie, dass diese Annahme nicht für Systeme gilt, für die sizeof(char) == sizeof(int). Gilt.)

Mit diesem Trick können Ganzzahlen nicht verglichen werden, da der Unterschied zwischen zwei Ganzzahlen im Allgemeinen nicht in eine Ganzzahl passt. Zum Beispiel schlägt INT_MAX - (-1) = INT_MIN vor, dass INT_MAX kleiner ist als -1 (technisch gesehen führt der Überlauf zu undefiniertem Verhalten, nehmen wir jedoch an, Modulo-Arithmetik).

Wie können wir also die Vergleichsfunktion für Ganzzahlen effizient implementieren? Hier ist mein erster Versuch:

int compare_int(int a, int b)
{
    int temp;
    int result;
    __asm__ __volatile__ (
        "cmp %3, %2 \n\t"
        "mov $0, %1 \n\t"

        "mov $1, %0 \n\t"
        "cmovg %0, %1 \n\t"

        "mov $-1, %0 \n\t"
        "cmovl %0, %1 \n\t"
    : "=r"(temp), "=r"(result)
    : "r"(a), "r"(b)
    : "cc");
    return result;
}

Kann es in weniger als 6 Anweisungen gemacht werden? Gibt es einen weniger einfachen Weg, der effizienter ist?

57
fredoverflow

Folgendes hat sich für mich immer als ziemlich effizient erwiesen:

return (a < b) ? -1 : (a > b);

Mit gcc -O2 -S werden die folgenden fünf Anweisungen zusammengestellt:

xorl    %edx, %edx
cmpl    %esi, %edi
movl    $-1, %eax
setg    %dl
cmovge  %edx, %eax

Als Folgemaßnahme zu Ambroz Bizjaks exzellente Antwort auf die Begleitung war ich nicht überzeugt, dass sein Programm denselben Assembly-Code getestet hat, der oben veröffentlicht wurde. Als ich die Compilerausgabe genauer studierte, stellte ich fest, dass der Compiler nicht die gleichen Anweisungen generierte, die in unseren Antworten enthalten waren. Also nahm ich an seinem Testprogramm teil, modifizierte die Baugruppenausgabe von Hand, um sie mit unseren Veröffentlichungen zu vergleichen, und verglich die resultierenden Zeiten. Es scheint, dass die beiden Versionen ungefähr identisch sind.

./opt_cmp_branchless: 0m1.070s
./opt_cmp_branch:     0m1.037s

Ich versende die Vollversammlung jedes Programms vollständig, damit andere dasselbe Experiment versuchen und meine Beobachtung bestätigen oder ihnen widersprechen können.

Folgendes ist die Version mit der Anweisung cmovge ((a < b) ? -1 : (a > b)):

        .file   "cmp.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d=0\n"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
.LFB20:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        pushq   %rbx
        .cfi_def_cfa_offset 24
        .cfi_offset 3, -24
        movl    $arr.2789, %ebx
        subq    $8, %rsp
        .cfi_def_cfa_offset 32
.L9:
        leaq    4(%rbx), %rbp
.L10:
        call    Rand
        movb    %al, (%rbx)
        addq    $1, %rbx
        cmpq    %rbx, %rbp
        jne     .L10
        cmpq    $arr.2789+4096, %rbp
        jne     .L9
        xorl    %r8d, %r8d
        xorl    %esi, %esi
        orl     $-1, %edi
.L12:
        xorl    %ebp, %ebp
        .p2align 4,,10
        .p2align 3
.L18:
        movl    arr.2789(%rbp), %ecx
        xorl    %eax, %eax
        .p2align 4,,10
        .p2align 3
.L15:
        movl    arr.2789(%rax), %edx
        xorl    %ebx, %ebx
        cmpl    %ecx, %edx
        movl    $-1, %edx
        setg    %bl
        cmovge  %ebx, %edx
        addq    $4, %rax
        addl    %edx, %esi
        cmpq    $4096, %rax
        jne     .L15
        addq    $4, %rbp
        cmpq    $4096, %rbp
        jne     .L18
        addl    $1, %r8d
        cmpl    $500, %r8d
        jne     .L12
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        addq    $8, %rsp
        .cfi_def_cfa_offset 24
        xorl    %eax, %eax
        popq    %rbx
        .cfi_def_cfa_offset 16
        popq    %rbp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE20:
        .size   main, .-main
        .local  arr.2789
        .comm   arr.2789,4096,32
        .section        .note.GNU-stack,"",@progbits

Die nachfolgende Version verwendet die branchless-Methode ((a > b) - (a < b)):

        .file   "cmp.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d=0\n"
        .text
        .p2align 4,,15
.globl main
        .type   main, @function
main:
.LFB20:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        pushq   %rbx
        .cfi_def_cfa_offset 24
        .cfi_offset 3, -24
        movl    $arr.2789, %ebx
        subq    $8, %rsp
        .cfi_def_cfa_offset 32
.L9:
        leaq    4(%rbx), %rbp
.L10:
        call    Rand
        movb    %al, (%rbx)
        addq    $1, %rbx
        cmpq    %rbx, %rbp
        jne     .L10
        cmpq    $arr.2789+4096, %rbp
        jne     .L9
        xorl    %r8d, %r8d
        xorl    %esi, %esi
.L19:
        movl    %ebp, %ebx
        xorl    %edi, %edi
        .p2align 4,,10
        .p2align 3
.L24:
        movl    %ebp, %ecx
        xorl    %eax, %eax
        jmp     .L22
        .p2align 4,,10
        .p2align 3
.L20:
        movl    arr.2789(%rax), %ecx
.L22:
        xorl    %edx, %edx
        cmpl    %ebx, %ecx
        setg    %cl
        setl    %dl
        movzbl  %cl, %ecx
        subl    %ecx, %edx
        addl    %edx, %esi
        addq    $4, %rax
        cmpq    $4096, %rax
        jne     .L20
        addq    $4, %rdi
        cmpq    $4096, %rdi
        je      .L21
        movl    arr.2789(%rdi), %ebx
        jmp     .L24
.L21:
        addl    $1, %r8d
        cmpl    $500, %r8d
        jne     .L19
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        addq    $8, %rsp
        .cfi_def_cfa_offset 24
        xorl    %eax, %eax
        popq    %rbx
        .cfi_def_cfa_offset 16
        popq    %rbp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE20:
        .size   main, .-main
        .local  arr.2789
        .comm   arr.2789,4096,32
        .section        .note.GNU-stack,"",@progbits
53
jxh

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
94
Ambroz Bizjak

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?

15
fredoverflow

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

10
Paul R

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;
}
3
Evgeny Kluev

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.

0
anatolyg