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

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

 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-битных значений.