64

compare函数是一个接受两个参数ab返回一个整数来描述它们的顺序的函数。如果a小于b,则结果为某个负整数。如果a大于b,则结果为某个正整数。否则,ab相等,结果为零。

此函数通常用于参数化标准库中的排序和搜索算法。

实现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 条指令内完成吗?有没有更直接但更有效的方法?

4

7 回答 7

97

这个没有分支,也没有溢出或下溢:

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

在纯 C 的解决方案中,我建议的解决方案是最快的。尽管只编译为 5 条指令,但 user315052 的解决方案速度较慢。减速可能是因为尽管少了一条指令,但还是有一条条件指令(cmovge)。

总的来说,FredOverflow 的 4 指令汇编实现在与正整数一起使用时是最快的。但是,这段代码只对整数范围 RAND_MAX 进行了基准测试,因此 4 指令测试是有偏差的,因为它单独处理溢出,而这些在测试中不会发生;速度可能是由于成功的分支预测。

使用全范围的整数 ( USE_RAND=0),4 指令解决方案实际上非常慢(其他相同):

compare4: 0m1.897s
于 2012-06-12T13:13:01.270 回答
55

以下一直被证明对我来说是相当有效的:

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
于 2012-06-12T12:21:35.840 回答
16

好的,我设法把它归结为四个指令:) 基本思想如下:

有一半的时间,差异小到可以放入一个整数。在这种情况下,只需返回差额即可。否则,将数字一向右移动。关键问题是什么位转移到 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 的每个组合测试了代码。所有测试都通过了。你能证明我错了吗?

于 2012-06-12T16:00:56.157 回答
10

对于它的价值,我将一个 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.137 秒。

相同 CPU 和编译器的 compare2 时间为 0.674 秒。

因此,正如预期的那样,SSE2 的实现速度提高了大约 4 倍(因为它是 4 宽 SIMD)。

于 2012-06-12T21:17:05.783 回答
3

此代码没有分支并使用 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;
}
于 2012-06-13T15:29:35.040 回答
0

也许您可以使用以下想法(在伪代码中;没有编写 asm 代码,因为我对语法不满意):

  1. 减去数字 ( result = a - b)
  2. 如果没有溢出,完成(jo指令和分支预测在这里应该可以很好地工作)
  3. 如果发生溢出,请使用任何稳健的方法 ( return (a < b) ? -1 : (a > b))

编辑:为了更加简单:如果有溢出,翻转结果的符号,而不是 step 3

于 2012-06-12T13:23:06.747 回答
-2

您可以考虑将整数提升为 64 位值。

于 2012-06-12T12:32:24.597 回答