phi*_*ipp 109 c c++ optimization divide-by-zero
摘要:
我正在寻找最快的计算方法
(int) x / (int) y
没有得到例外y==0.相反,我只想要一个任意的结果.
背景:
在编码图像处理算法时,我经常需要除以(累积的)α值.最简单的变体是带有整数运算的普通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];
但这显然不适用于更大的范围.
我想最后一个问题是:什么是最快的位,将hack改为0到任何其他整数值,同时保持所有其他值不变？
澄清
我不是100%确定分支太贵了.但是,使用了不同的编译器,所以我更喜欢基准测试而几乎没有优化(这确实值得怀疑).
当然,编译器很有用,但是我不能在C中表达"不关心"的结果,因此编译器永远无法使用全范围的优化.
代码应完全兼容C,主要平台是带有gcc&clang和MacOS的Linux 64位.
Bry*_*ier 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是通过预测执行完全实现的.
小智 20
以下是一些具体的数字,在Windows上使用GCC 4.7.2:
#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与其他检查相比没有任何缺点,并且它确实保留了零作为更常见的好处.
不过,您应该真正测量一下编译器和代表性样本数据会发生什么.
Tyl*_*den 13
在不了解平台的情况下,无法知道确切最有效的方法,但是,在通用系统上,这可能接近最优(使用英特尔汇编语法):
(假设除数在ecx,并且红利在eax)
mov ebx, ecx
neg ebx
sbb ebx, ebx
add ecx, ebx
div eax, ecx
四个不分支的单周期指令加上除法.商将在eax,其余将在edx最后.(这种方式说明了为什么你不想发送编译器来完成一个人的工作).