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

Функция 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 (технически переполнение приводит к неопределенному поведению, но допустим по модулю арифметику).

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

 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 инструкций? Есть ли более простой способ, который более эффективен?

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

     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 

    У этого нет ветвей и он не страдает переполнением или недостаточным streamом:

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

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

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

     compare4: 0m1.897s 

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

    Половина времени разница достаточно мала, чтобы вписаться в целое число. В этом случае просто верните разницу. В противном случае сдвиньте номер один вправо. Ключевым вопросом является то, что бит перейдет в 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. Все тесты прошли. Вы можете ошибаться?

    Для чего стоит собрать реализацию SSE2. vec_compare1 использует тот же подход, что и для compare2 но требует только трех арифметических инструкций SSE2:

     #include  #include  #include  #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,137 секунды.

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

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

    Этот код не имеет филиалов и использует 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; } 

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

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

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

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

    Давайте будем гением компьютера.