Эффективная функция сравнения целого числа
Функция 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 инструкций? Есть ли более простой способ, который более эффективен?
Ответы
Ответ 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-битных значений.
