高效的整数比较function
compare函数是一个函数，它接受两个参数a和b并返回一个描述其顺序的整数。 如果a小于b ，结果是一些负整数。 如果a大于b ，结果是一些正整数。 否则， a和b相等，结果为零。
这个函数经常被用来参数化从标准库中sorting和searchalgorithm。
实现字符的comparefunction非常简单， 你简单地减去参数：
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; }
可以用less于6条指令完成吗？ 有没有更直接的方式，更有效率？
以下对我来说总是被certificate是相当有效率的：
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出色的同伴回答的后续工作，我不相信他的程序testing了上面发布的相同的汇编代码。 而且，当我更仔细地研究编译器的输出时，我注意到编译器并没有生成与我们的答案中发布的相同的指令。 于是，我拿着他的testing程序，手工修改了程序集的输出以匹配我们发布的内容，并比较了结果的时间。 看来这两个版本大致相同。
./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
这个没有分支，没有上溢或下溢：
return (a > b) - (a < b);
使用gcc -O2 -S ，可以编译成以下六个指令：
xorl %eax, %eax cmpl %esi, %edi setl %dl setg %al movzbl %dl, %edx subl %edx, %eax
这里有一些代码来testing各种比较实现：
#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
在C-only解决scheme中，我build议的解决scheme是最快的。 尽pipe只编译了5条指令，但user315052的解决scheme却比较慢。 减速的原因可能是因为尽pipe只有一条指令，但却有一个条件指令（ cmovge ）。
总体而言，与正整数一起使用时，FredOverflow的4指令汇编实现是最快的。 然而，这个代码只testing了整数范围RAND_MAX，所以4-instuctiontesting是有偏见的，因为它分别处理溢出，而这些在testing中不会发生; 速度可能是由于分支预测成功。
对于全部范围的整数（ USE_RAND=0 ），4条指令的解决scheme实际上非常缓慢（其他条件相同）：
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
在第一种情况下（即使INT_MIN不等于INT_MAX ）和第二种情况下的负数（尽pipeINT_MAX不小于INT_MIN ），将进位进位移位将产生0。
但是如果我们在进行转换之前翻转进位，我们会得到合理的数字：
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
我确信有一个深刻的math原因，为什么翻转进位是有道理的，但我还没有看到它。
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; }
我已经用一百万个随机input加上INT_MIN，-INT_MAX，INT_MIN / 2，-1,0,1，INT_MAX / 2，INT_MAX / 2 + 1，INT_MAX的每个组合来testing代码。 所有testing通过。 你能否certificate我错了？
为了什么值得我放在一起SSE2实施。 vec_compare1使用与vec_compare1相同的方法，但只需要三条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。
compare2与相同的CPU和编译器的时间是0.674s。
所以SSE2的执行速度比预期快4倍左右（因为它是SIMD的4倍宽）。
此代码没有分支并使用5条指令。 在最近的英特尔处理器上，它的性能可能会超过其他无分支产品，因为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代码，因为我不习惯语法）：
- 减去数字（
result = a - b） - 如果没有溢出，完成（
jo指令和分支预测应该在这里工作得很好） - 如果有溢出，使用任何健壮的方法（
return (a < b) ? -1 : (a > b)）
编辑： 为了更加简单：如果有溢出，请翻转结果的符号，而不是第3步 。
你可以考虑把整数提升到64位的值。
