什么是最快的整数除法，支持无论结果如何都可以除以零？

Question

摘要：

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

(int) x / (int) y

不希望在y==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更改为任何其他整数值的最快位操作技巧是什么？

---

澄清

我不确定分支是否太昂贵。 但是，使用不同的编译器进行基准测试，因此我更喜欢使用少量优化（确实是有问题的）。

当涉及位操作时，编译器确实非常好，但我无法在C中表示“不关心”的结果，因此编译器永远无法使用全部优化范围。

代码应完全兼容C，主要平台是Linux 64位与gcc和clang以及MacOS。

- philipp

---

你是如何判断 if-branch 的成本太高的？ - djechlin

你是如何确定存在一个分支的？ - leemes

支持使用剖析技术，但在现代分支预测的帮助下，您可能不需要这样做。另外，为什么要编写自己的图像处理算法？ - TC1

什么是最快的二进制操作技巧？也许是 y += !y 吗？不需要分支来计算。你可以将 x / (y + !y) 与 x / max(y, 1) 进行比较，也许还有 y ? (x/y) : 0。我猜在启用优化的情况下，它们都不会有分支。 - leemes

如果有人认为现代分支预测可以避免这种问题，那么他们可能还没有足够地对以每个像素级别运行的分支消除代码进行分析。如果 alpha 的 0 部分非常巨大而且是连续的，那么现代分支预测是可接受的。微小优化确实有其应用场景，而针对每个像素的操作正是这样一个场景。 - Yakk - Adam Nevraumont

Answer 1

在一些评论的启发下，我通过使用gcc编译器摆脱了我的Pentium上的分支。

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的编译器和GCC编译器上运行，这两者都支持条件执行。两个编译器都避免了两个代码示例中的分支：

使用ARM编译器的Philipp版本：

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

使用GCC编译的Philipp版本：

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的测试是完全通过谓词执行来实现的。

- Bryan Olivier

---

你能展示一下生成的汇编代码吗？或者你是如何确定没有分支的？ - Haatschii

太棒了。可以将其制作为constexpr并避免像这样不必要的类型转换：template<typename T, typename U> constexpr auto fdiv( T t, U u ) -> decltype(t/(u+!u)) { return t/(u+!u); } 如果你想要255，则可以使用(lhs)/(rhs+!rhs) & -!rhs。 - Yakk - Adam Nevraumont

@leemes 但我是指 | 而不是 &。哎呀--如果 rhs 是 0，( (lhs)/(rhs+!rhs) ) | -!rhs 应该将您的值设置为 0xFFFFFFF，如果 rhs!=0，则设置为 lhs/rhs。 - Yakk - Adam Nevraumont

很棒的答案！我通常会使用汇编来处理这些事情，但那总是很难维护（更不用说不太可移植了;)）。 - Leo

你展示编译器的汇编输出的未优化版本是有意为之吗？启用优化后，编译器变得更加智能，代码变得更易读。请注意，还有一些编译器会使用条件移动指令（自 Pentium Pro 以来由 x86 支持），如果你只写 return x / (y == 0 ? 1 : y);，它们将生成更高效的代码。 - Cody Gray

Answer 2

以下是一些具体数字，在使用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没有任何缺点，并且它确实保留了零越来越普遍的好处。

不过，你应该真正进行测量，看看你的编译器和代表性样本数据会发生什么。

- user743382

---

将50%的输入随机设置为 d=0，而不是几乎总是设置为 d!=0，你将会看到更多分支预测失败。如果一个分支几乎总是被跟随，或者跟随其中一个分支的情况非常集中，那么分支预测就非常有效... - Yakk - Adam Nevraumont

@Yakk d 迭代是内部循环，因此 d == 0 的情况被均匀分布。让 50% 的情况成为 d == 0 真实吗？ - user743382

制造0.002%的情况下d==0是现实的吗？ 它们分布在整个过程中，每65000次迭代就会出现一次d==0情况。 虽然50％可能不经常发生，但10％或1％很容易发生，甚至可能是90％或99％。如所显示的测试，只是真正测试了“如果你基本上从不走一个分支，那么分支预测是否使去除分支无意义？”答案是“是的，但这没什么意义”。 - Yakk - Adam Nevraumont

不会，因为由于噪音的存在，这些差异将是无法有效地被察觉到的。 - Joe

零点的分布与问题提出者情境中的分布无关。混合了0透明度和其他值的图像可能会有空洞或不规则形状，但（通常）这不是噪声。假设您对数据一无所知（并将其视为噪声）是错误的。这是一个真实世界的应用程序，具有可能存在0透明度的实际图像。由于像素行很可能要么全部为a=0，要么全部为a>0，利用分支预测可能是最快的选择，特别是当a=0经常出现时并避免（缓慢的）除法（15+个周期！）。 - DDS

Answer 3

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

（假设除数在ecx中，被除数在eax中）

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

四条未分支的单周期指令加上除法指令。商将在eax中，余数将在edx中。

（这也说明为什么你不想让编译器来完成一个人的工作）。

- Tyler Durden

---

这并不执行除法，它只是污染了被除数，以使得除以零变为不可能。 - Tyler Durden

@Jens Timmerman 对不起，我在添加div语句之前写了那个。我已经更新了文本。 - Tyler Durden

Answer 4

根据此链接，您可以使用sigaction()来阻止SIGFPE信号（我自己没有尝试过，但我相信它应该有效）。如果除以零错误非常罕见，则这是最快的方法：您只需为除以零付费，而不是为有效的除法付费，正常执行路径根本不会改变。然而，每个被忽略的异常都会涉及操作系统，这很昂贵。我认为，您应该至少有一千个良好的除数，才能忽略每个除以零。如果异常比这更频繁，您可能会因忽略异常而支付更多，而不是在除法之前检查每个值。

- cmaster - reinstate monica