提问人：fredoverflow 提问时间：6/12/2012 最后编辑：Jonathan Lefflerfredoverflow 更新时间：9/13/2019 访问量：42033
高效整数比较函数
Efficient integer compare function
问：
该函数是一个函数，它接受两个参数并返回一个描述其顺序的整数。如果小于 ，则为某个负整数。如果大于 ，则为某个正整数。否则，和 相等，结果为零。compareabababab
此函数通常用于参数化标准库中的排序和搜索算法。
实现字符函数非常容易;您只需减去参数：compare
int compare_char(char a, char b)
{
return a - b;
}
这之所以有效，是因为通常假定两个字符之间的差异适合整数。（请注意，此假设不适用于 .）sizeof(char) == sizeof(int)
这个技巧不能用于比较整数，因为两个整数之间的差通常不适合整数。例如，建议小于（从技术上讲，溢出会导致未定义的行为，但让我们假设模算术）。INT_MAX - (-1) = INT_MININT_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 条指令中完成吗？有没有一种不那么直接的方法更有效率？
答：
56赞
jxh
6/12/2012
#1
以下内容一直被证明对我来说相当有效：
return (a < b) ? -1 : (a > b);
使用 ，这将编译为以下 5 条指令：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
评论
3赞
John Dibling
6/12/2012
+1;另一个好处是它不依赖于关键字，我相信您知道，关键字不适用于所有平台。asm
1赞
Daniel Kamil Kozar
6/12/2012
这仅适用于 i686 及更高版本的 x86 CPU 系列，例如具有 CMOV 指令的 CPU。实际上，它是在 Pentium Pro 之后制造的任何 CPU（Pentium MMX 除外），所以你应该没问题，除非你的一个用户碰巧有一台 >10 年的机器。
3赞
Paul R
6/13/2012
@Daniel：如果你只使用 C 版本，那么无论如何你都应该得到几乎最优的代码（假设编译器一半像样）
0赞
Daniel Kamil Kozar
6/13/2012
当然，你是对的。我只是指出了来自这个特定代码的事实。
0赞
jxh
4/26/2014
@FredOverflow：这真的会导致管道停滞吗？您显示的程序集输出中似乎没有条件跳转。您使用了哪个版本的编译器？cmovge
-2赞
Puppy
6/12/2012
#2
您可以考虑将整数提升为 64 位值。
评论
1赞
Paul R
6/12/2012
你可以，但由于你必须返回一个 int，你仍然需要处理任何溢出。
0赞
Puppy
6/12/2012
@PaulR：只要掩盖多余的部分即可。
3赞
Paul R
6/12/2012
不 - 它需要更多 - 考虑不能用 32 位表示的情况 - 如果您只是屏蔽高位，则结果符号将不正确。例如，在转换回 32 位之前，您需要在 64 位处饱和。这将需要 5 条以上的指令。a - b
0赞
Puppy
6/12/2012
@PaulR：x64 具有您可以使用的算术移位指令。
1赞
MSalters
6/12/2012
@DeadMG：但是这些会错误地将 -1 或 +1 四舍五入为零。我会沿着逻辑转变的思路思考。这将符号位保持在应有的位置，并确保最终仅为零。它有一个错误是被视为负值。x = x | x>>320LL0x80000000LL
97赞
Ambroz Bizjak
6/12/2012
#3
这个没有分支，也没有溢出或下溢：
return (a > b) - (a < b);
使用 ，这将编译为以下 6 条指令：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 -O2USE_RAND=1
compare1: 0m1.118s
compare2: 0m0.756s
compare3: 0m1.101s
compare4: 0m0.561s
在纯 C 解决方案中，我建议的那个是最快的。user315052 的解决方案尽管只编译了 5 条指令，但速度较慢。速度变慢可能是因为，尽管少了一个指令，但有一个条件指令 （）。cmovge
总体而言，FredOverflow 的 4 指令汇编实现在与正整数一起使用时速度最快。但是，此代码仅对整数范围进行了基准测试RAND_MAX，因此 4 个 instuction 测试是有偏差的，因为它单独处理溢出，而这些在测试中不会发生;速度可能是由于分支预测成功。
对于全范围的整数 （），4 条指令的解决方案实际上非常慢（其他的都是一样的）：USE_RAND=0
compare4: 0m1.897s
评论
0赞
fredoverflow
6/13/2012
你能修改基准测试以生成完整的整数谱吗？如果将 ？rand()rand() | rand() << 17
0赞
jxh
4/26/2014
@AmbrozBizjak：您是否验证过您的编译器生成了与我的答案中发布的相同的 5 条指令？我只是好奇。
0赞
Ambroz Bizjak
4/27/2014
@jxh 在我当前的系统上，我得到：compare2 0m0.488s，compare3 0m0.502s。程序集与张贴的程序集不同，但相似：ideone.com/uhmIYt 和 ideone.com/cD9Zd2。这些基准测试的问题在于，结果还取决于编译器如何设法将代码内联到循环中。如果我们强制它不内联比较函数可能会更好。
0赞
BeeOnRope
1/21/2019
请注意，在 gcc 7.x（但不是 6.x 或 8.x）中，使用一个分支 - 所以如果你的比较是不可预测的，你可能会感到一个令人讨厌的惊喜！compare3(...) { a < b ? -1 : (a > b); }
0赞
anatolyg
6/12/2012
#4
也许您可以使用以下想法（在伪代码中;没有编写 asm-code，因为我对语法不满意）：
- 减去数字 （
result = a - b) - 如果没有溢出，则完成（指令和分支预测在这里应该可以很好地工作）
jo - 如果存在溢出，请使用任何可靠的方法（
return (a < b) ? -1 : (a > b))
编辑：为了更加简单：如果有溢出，请翻转结果的符号，而不是步骤 3。
评论
0赞
fredoverflow
6/12/2012
您的替代步骤 3 不适用于 。compare_int(0, -2147483648)
0赞
anatolyg
6/12/2012
同意，这是一个糟糕的优化
16赞
fredoverflow
6/13/2012
#5
好的，我设法将其归结为四个指令:)基本思路如下：
在一半的时间里，差值足够小，可以容纳成一个整数。在这种情况下，只需返回差额即可。否则，将数字 1 向右移动。关键问题是，接下来要把什么位转移到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_MININT_MAXINT_MAXINT_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 的每个组合测试了代码。所有测试均已通过。你能证明我错了吗？
评论
0赞
Paul R
6/13/2012
即使它是 4 条指令，您仍然可能会发现 5 或 6 条指令的无分支序列更快。
1赞
fredoverflow
6/13/2012
@mfontanini 对于随机输入，我预计我的解决方案是迄今为止最慢的。另一方面，如果溢出很少发生，我希望它表现得很好（分支预测）。无论如何，我只是发现找到一个更短的解决方案:)
1赞
Alexey Frunze
6/14/2012
你会看到，如果你写出一个比特完全减法的真值表，反向进位确实等于有符号溢出时的正确符号。在此过程中，请记住，对于正确的符号和有符号溢出计算，应被视为算术，并且总和不是溢出 IFF，它是 或 。所以，你的猜想是正确的。minuend bit=1subtrahend bit=1-10-1
10赞
Paul R
6/13/2012
#6
值得一提的是，我整理了一个 SSE2 实现。 使用与 SSE2 相同的方法，但只需要三个 SSE2 算术指令：vec_compare1compare2
#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.137 秒。
使用相同的 CPU 和编译器进行 compare2 的时间为 0.674 秒。
因此，正如预期的那样，SSE2 实现的速度大约快了 4 倍（因为它是 4 宽 SIMD）。
3赞
Evgeny Kluev
6/13/2012
#7
此代码没有分支，使用 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;
}
评论
0赞
fredoverflow
6/14/2012
您提出的解决方案似乎存在缺陷，请参阅我的编辑。
0赞
Evgeny Kluev
6/14/2012
@FredOverflow：没错，“res”初始化丢失了。
评论
return (a<b)?-1:(a>b);if (compare_int(a,b) < 0)if (a < b)