Эффективная функция сравнения целого числа - программирование

Эффективная функция сравнения целого числа

Функция compare - это функция, которая принимает два аргумента a и b и возвращает целое число, описывающее их порядок. Если a меньше, чем b, результатом является некоторое отрицательное целое число. Если a больше, чем b, результатом будет некоторое положительное целое число. В противном случае a и b равны, а результат равен нулю.

Эта функция часто используется для параметризации алгоритмов сортировки и поиска из стандартных библиотек.

Реализация функции compare для символов довольно проста; вы просто вычитаете аргументы:

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

Это работает, потому что различие между двумя символами обычно считается помещенным в целое число. (Заметим, что это предположение не выполняется для систем, где sizeof(char) == sizeof(int).)

Этот трюк не может работать для сравнения целых чисел, поскольку разница между двумя целыми числами обычно не вписывается в целое число. Например, INT_MAX - (-1) = INT_MIN предполагает, что INT_MAX меньше, чем -1 (технически переполнение приводит к поведению undefined, но пусть принимает по модулю арифметику).

Итак, как эффективно реализовать функцию сравнения для целых чисел? Вот моя первая попытка:

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

Можно ли выполнить менее 6 инструкций? Есть ли более простой способ, который более эффективен?

4b9b3361

ОТВЕТЫ

Ответ 1

Для меня всегда было достаточно эффективным:

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

С gcc -O2 -S, это сводится к следующим пяти инструкциям:

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

Как продолжение отличного сопутствующего ответа Ambroz Bizjak, я не был уверен, что его программа проверила тот же код сборки, что и выше. И когда я больше изучал вывод компилятора, я заметил, что компилятор не генерировал те же инструкции, которые были опубликованы в любом из наших ответов. Итак, я взял свою тестовую программу, вручную изменил сборку, чтобы она соответствовала тому, что мы разместили, и сравнил полученные результаты. Кажется, что две версии сравниваются примерно одинаково.

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

Я публикую сборку каждой программы в полном объеме, чтобы другие могли попробовать один и тот же эксперимент и подтвердить или противоречить моему наблюдению.

Ниже приведена версия с инструкцией 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

В приведенной ниже версии используется метод разветвления ((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

Ответ 2

У этого нет ветвей и он не страдает от переполнения или недостаточного потока:

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

С gcc -O2 -S, это сводится к следующим шести инструкциям:

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

Здесь некоторый код для сравнения различных реализаций сравнения:

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

Результаты моей 64-битной системы, скомпилированные с gcc -std=c99 -O2, для целых положительных чисел (USE_RAND=1):

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

Из решений только для С, тот, который я предложил, был самым быстрым. Решение user315052 было медленнее, несмотря на составление всего лишь 5 инструкций. Замедление, скорее всего, связано с тем, что, несмотря на одну инструкцию, существует условная инструкция (cmovge).

В целом, реализация сборки FredOverflow 4-инструкции была самой быстрой при использовании с положительными целыми числами. Тем не менее, этот код только сравнивал целочисленный диапазон RAND_MAX, поэтому тест с 4-ступенчатостью смещен, поскольку он обрабатывает переполнение отдельно, и это не происходит в тесте; скорость может быть вызвана успешным предсказанием ветвления.

С полным диапазоном целых чисел (USE_RAND=0) решение с 4 командами на самом деле очень медленно (другие одинаковы):

compare4: 0m1.897s

Ответ 3

Хорошо, мне удалось разобраться с четырьмя инструкциями:) Основная идея такова:

Половина времени, разница достаточно мала, чтобы вписаться в целое число. В этом случае просто верните разницу. В противном случае сдвиньте номер один вправо. Критический вопрос заключается в том, какой бит должен перейти в MSB.

Посмотрим на два крайних примера, используя для этого просто 8 бит вместо 32 бит:

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

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

При переносе бит переноса в первом случае получится 0 (хотя INT_MIN не равно INT_MAX) и некоторое отрицательное число для второго случая (хотя INT_MAX не меньше INT_MIN).

Но если мы перевернем бит переноса перед выполнением сдвига, мы получим разумные числа:

 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

Я уверен, что есть глубокая математическая причина, почему имеет смысл перевернуть бит переноса, но я пока этого не вижу.

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

Я тестировал код с миллионом случайных входов плюс каждая комбинация INT_MIN, -INT_MAX, INT_MIN/2, -1, 0, 1, INT_MAX/2, INT_MAX/2 + 1, INT_MAX. Все тесты прошли. Вы можете ошибаться?

Ответ 4

Для чего я собрал реализацию SSE2. vec_compare1 использует тот же подход, что и compare2, но требует только трех арифметических инструкций 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;
}

Время для этого равно 0.137s.

Время для сравнения2 с тем же процессором и компилятором составляет 0.674 с.

Таким образом, реализация SSE2 примерно в 4 раза быстрее, как и следовало ожидать (поскольку это 4-х SIM-код).

Ответ 5

Этот код не имеет ветвей и использует 5 инструкций. Он может превосходить другие альтернативы без ветвей на последних процессорах Intel, где инструкции cmov * довольно дороги. Недостатком является несимметричное возвращаемое значение (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;
}

Этот вариант не требует инициализации, поэтому он использует только 4 команды:

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

Ответ 6

Может быть, вы можете использовать следующую идею (в псевдокоде, не писать asm-код, потому что мне не удобно с синтаксисом):

  • Вычтите числа (result = a - b)
  • Если никакого переполнения, сделано (jo инструкция и предсказание ветки должны работать очень хорошо здесь)
  • Если произошло переполнение, используйте любой надежный метод (return (a < b) ? -1 : (a > b))

Изменить: для дополнительной простоты: если произошло переполнение, переверните знак результата вместо шага 3.

Ответ 7

Вы можете подумать о продвижении целых чисел до 64-битных значений.