c - 高效的整数比较函数

Question

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(从技术上讲，溢出会导致未定义的行为，但让我们假设模运算)。

那么我们如何才能有效地实现整数的比较功能呢？这是我的第一次尝试:

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 条指令完成吗？有没有更高效的不那么直接的方法？

Answer 1

这个没有分支，也没有上溢或下溢:

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