Efektywna funkcja porównywania liczb całkowitych

Ten nie ma rozgałęzień i nie cierpi na przepełnienie lub niedotlenienie:

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

Z gcc -O2 -S, kompiluje się do następujących sześciu instrukcji:

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

Oto kod do porównywania różnych implementacji porównawczych:

#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;
}

Wyniki na moim 64-bitowym systemie, skompilowane z gcc -std=c99 -O2, dla dodatnich liczb całkowitych (USE_RAND=1):

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

Z rozwiązań tylko dla C, ten, który zaproponowałem, był najszybszy. rozwiązanie user315052 było wolniejsze mimo kompilacji do tylko 5 instrukcje. Spowolnienie jest prawdopodobne, ponieważ pomimo posiadania o jedną instrukcję mniej, istnieje instrukcja warunkowa (cmovge).

Ogólnie Rzecz Biorąc, implementacja zestawu 4-instrukcji FredOverflow była najszybsza, gdy była używana z dodatnimi liczbami całkowitymi. Jednak kod ten oznaczał tylko zakres liczb całkowitych RAND_MAX, więc test 4-instanction jest stronniczy, ponieważ obsługuje przepełnienia oddzielnie, a te nie występują w teście; prędkość może być spowodowana pomyślnym odgałęzieniem przewidywanie.

Z pełnym zakresem liczb całkowitych (USE_RAND=0), rozwiązanie 4-instrukcji jest w rzeczywistości bardzo wolne (inne są takie same):

compare4: 0m1.897s

Ok, udało mi się sprowadzić go do czterech instrukcji :) podstawowa idea jest następująca:

Spójrzmy na dwa skrajne przykłady, używając 8 bitów zamiast 32 bitów dla uproszczenia:

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

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

Przesunięcie bitu carry w dałoby 0 dla pierwszy przypadek (chociaż INT_MIN nie jest równy INT_MAX) i pewna liczba ujemna dla drugiego przypadku (chociaż INT_MAX nie jest mniejsza niż INT_MIN).

Ale jeśli przewrócimy bit carry przed wykonaniem zmiany, otrzymamy sensowne liczby:

 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

Jestem pewien, że istnieje głęboki matematyczny powód, dla którego ma sens przewracanie bitu do przenoszenia, ale jeszcze tego nie widzę.

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;
}

Przetestowałem kod z milionem losowych wejść plus każda kombinacja INT_MIN, -INT_MAX, INT_MIN/2, -1, 0, 1, INT_MAX/2, INT_MAX / 2+1, INT_MAX. Wszystkie testy przeszły pomyślnie. Możesz się mylić?

Jeśli to coś warte, przygotowałem implementację SSE2. vec_compare1 używa tego samego podejścia co compare2, ale wymaga tylko trzech instrukcji arytmetycznych SSE2:

#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;
}

Czas na to 0.137 s.

Czas dla compare2 z tym samym procesorem i kompilatorem wynosi 0,674 s.

Więc implementacja SSE2 jest około 4x szybsza, jak można się było spodziewać (ponieważ jest to 4-szeroka SIMD).

Ten kod nie ma gałęzi i używa 5 instrukcji. Może to przewyższać inne alternatywy bez gałęzi na ostatnich procesorach Intel, gdzie instrukcje cmov* są dość drogie. Wadą jest niesymetryczna wartość zwracana (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;
}

Ten wariant nie wymaga inicjalizacji, więc używa tylko 4 instrukcji:

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;
}

Może możesz użyć następującego pomysłu (w pseudo-kodzie; nie napisałem ASM-kodu, ponieważ nie jestem zadowolony ze składni):

1. odjąć liczby (result = a - b)
2. Jeśli nie ma przepełnienia, done (jo instrukcja i przewidywanie gałęzi powinny działać bardzo dobrze tutaj)
3. Jeśli było przepełnienie, użyj dowolnej solidnej metody (return (a < b) ? -1 : (a > b))

Edit: dla dodatkowej prostoty: jeśli było przepełnienie, Odwróć znak wyniku, zamiast kroku 3.

Możesz rozważyć promowanie liczb całkowitych do wartości 64bit.