110

概括：

我正在寻找最快的计算方法

(int) x / (int) y

没有例外y==0。相反，我只想要一个任意的结果。

背景：

在编码图像处理算法时，我经常需要除以（累积的）alpha 值。最简单的变体是带有整数运算的纯 C 代码。我的问题是，对于结果像素，我通常会得到除以零的误差alpha==0。然而，这正是结果无关紧要的像素：我不关心像素的颜色值alpha==0。

细节：

我正在寻找类似的东西：

result = (y==0)? 0 : x/y;

或者

result = x / MAX( y, 1 );

x 和 y 是正整数。代码在嵌套循环中执行了很多次，所以我正在寻找一种方法来摆脱条件分支。

当 y 不超过字节范围时，我对解决方案感到满意

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

但这显然不适用于更大的范围。

我想最后一个问题是：将 0 更改为任何其他整数值，同时保持所有其他值不变的最快位旋转黑客是什么？

澄清

我不是 100% 肯定分支太贵了。但是，使用了不同的编译器，所以我更喜欢几乎没有优化的基准测试（这确实是有问题的）。

可以肯定的是，编译器在位旋转方面非常出色，但我无法在 C 中表达“不关心”的结果，因此编译器将永远无法使用全部优化。

代码应该完全兼容 C，主要平台是带有 gcc 和 clang 的 Linux 64 位和 MacOS。

4

4 回答 4

107

受到一些评论的启发，我摆脱了奔腾和gcc编译器上的分支，使用

int f (int x, int y)
{
        y += y == 0;
        return x/y;
}

编译器基本上承认它可以在添加中使用测试的条件标志。

根据要求组装：

.globl f
    .type   f, @function
f:
    pushl   %ebp
    xorl    %eax, %eax
    movl    %esp, %ebp
    movl    12(%ebp), %edx
    testl   %edx, %edx
    sete    %al
    addl    %edx, %eax
    movl    8(%ebp), %edx
    movl    %eax, %ecx
    popl    %ebp
    movl    %edx, %eax
    sarl    $31, %edx
    idivl   %ecx
    ret

由于事实证明这是一个如此受欢迎的问题和答案，我将详细说明一下。上面的示例基于编译器识别的编程习惯。在上述情况下，整数运算中使用了布尔表达式，并且为此目的在硬件中发明了条件标志的使用。一般来说，条件标志只能在 C 中通过使用习语访问。这就是为什么在不诉诸（内联）汇编的情况下很难用 C 语言制作一个可移植的多精度整数库。我的猜测是大多数体面的编译器都会理解上述成语。

避免分支的另一种方法，正如在上面的一些评论中所指出的那样，是谓词执行。因此，我采用了 philipp 的第一个代码和我的代码，并通过 ARM 的编译器和 ARM 架构的 GCC 编译器运行它，该编译器具有预测执行功能。两个编译器都避免了两个代码示例中的分支：

Philipp 的带有 ARM 编译器的版本：

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

Philipp 的 GCC 版本：

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

我使用 ARM 编译器的代码：

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

我的 GCC 代码：

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

所有版本仍然需要一个分支到除法例程，因为这个版本的 ARM 没有用于除法的硬件，但测试y == 0是通过谓词执行完全实现的。

于 2013-05-27T17:14:32.197 回答
21

以下是使用 GCC 4.7.2 的 Windows 上的一些具体数字：

#include <stdio.h>
#include <stdlib.h>

int main()
{
  unsigned int result = 0;
  for (int n = -500000000; n != 500000000; n++)
  {
    int d = -1;
    for (int i = 0; i != ITERATIONS; i++)
      d &= rand();

#if CHECK == 0
    if (d == 0) result++;
#elif CHECK == 1
    result += n / d;
#elif CHECK == 2
    result += n / (d + !d);
#elif CHECK == 3
    result += d == 0 ? 0 : n / d;
#elif CHECK == 4
    result += d == 0 ? 1 : n / d;
#elif CHECK == 5
    if (d != 0) result += n / d;
#endif
  }
  printf("%u\n", result);
}

请注意，我故意不调用srand()，因此rand()始终返回完全相同的结果。另请注意，-DCHECK=0仅计算零，因此很明显出现的频率。

现在，以各种方式编译和计时：

$ for it in 0 1 2 3 4 5; do for ch in 0 1 2 3 4 5; do gcc test.cc -o test -O -DITERATIONS=$it -DCHECK=$ch && { time=`time ./test`; echo "Iterations $it, check $ch: exit status $?, output $time"; }; done; done

显示可以汇总在表格中的输出：

Iterations → | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.612s | -        | -        | -         | -         | -
Check 2      | 0m0.612s | 0m6.527s | 0m9.718s | 0m13.464s | 0m18.422s | 0m22.871s
Check 3      | 0m0.616s | 0m5.601s | 0m8.954s | 0m13.211s | 0m19.579s | 0m25.389s
Check 4      | 0m0.611s | 0m5.570s | 0m9.030s | 0m13.544s | 0m19.393s | 0m25.081s
Check 5      | 0m0.612s | 0m5.627s | 0m9.322s | 0m14.218s | 0m19.576s | 0m25.443s

如果零很少见，则该-DCHECK=2版本的性能很差。随着零开始出现更多，-DCHECK=2案例开始表现得更好。在其他选项中，确实没有太大区别。

但是，对于 来说-O3，这是一个不同的故事：

Iterations → | 0        | 1        | 2        | 3         | 4         | 5
-------------+-------------------------------------------------------------------
Zeroes       | 0        | 1        | 133173   | 1593376   | 135245875 | 373728555
Check 1      | 0m0.646s | -        | -        | -         | -         | -
Check 2      | 0m0.654s | 0m5.670s | 0m9.905s | 0m14.238s | 0m17.520s | 0m22.101s
Check 3      | 0m0.647s | 0m5.611s | 0m9.085s | 0m13.626s | 0m18.679s | 0m25.513s
Check 4      | 0m0.649s | 0m5.381s | 0m9.117s | 0m13.692s | 0m18.878s | 0m25.354s
Check 5      | 0m0.649s | 0m6.178s | 0m9.032s | 0m13.783s | 0m18.593s | 0m25.377s

在那里，检查 2 与其他检查相比没有任何缺点，并且随着零变得越来越普遍，它确实保留了好处。

不过，您应该真正测量一下您的编译器和您的代表性样本数据会发生什么。

于 2013-05-27T18:13:10.090 回答
13

在不了解平台的情况下，无法知道确切最有效的方法，但是，在通用系统上，这可能接近最优（使用 Intel 汇编器语法）：

（假设除数在ecx且被除数在eax）

mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx

四个无分支的单周期指令加上除法。商将在eax，余数将在edx最后。（这说明了为什么你不想派编译器来做人的工作）。

于 2013-05-27T17:44:27.967 回答
1

根据此链接，您可以使用sigaction()（我自己没有尝试过，但我相信它应该可以）来阻止 SIGFPE 信号。

如果除以零错误极为罕见，这是最快的方法：您只需为除以零付费，而不为有效除法付费，正常执行路径根本不会改变。

但是，操作系统将涉及每个被忽略的异常，这很昂贵。我认为，您应该忽略每个除以零的至少一千个好的除法。如果异常比这更频繁，您可能会通过忽略异常而不是在除法之前检查每个值来支付更多费用。

于 2015-01-02T14:52:15.653 回答