pow（int，int）为什么这么慢？
我一直在做一些Euler练习，以提高我对C ++的了解。
我写了下面的函数：
int a = 0,b = 0,c = 0; for (a = 1; a <= SUMTOTAL; a++) { for (b = a+1; b <= SUMTOTAL-a; b++) { c = SUMTOTAL-(a+b); if (c == sqrt(pow(a,2)+pow(b,2)) && b < c) { std::cout << "a: " << a << " b: " << b << " c: "<< c << std::endl; std::cout << a * b * c << std::endl; } } } 这在17毫秒计算。
但是，如果我改变了这一行
if (c == sqrt(pow(a,2)+pow(b,2)) && b < c)
至
if (c == sqrt((a*a)+(b*b)) && b < c)
计算发生在2毫秒。 有没有pow(int, int)一些明显的实现细节，我失踪，这使得第一个expression式计算如此之慢？
pow()与真正的浮点数一起使用，并在公式底下使用
pow(x,y) = e^(y log(x))
来计算x^y 。 在调用pow之前， int被转换为double 。 （ log是自然对数，基于e）
因此使用pow() x^2比x*x慢。
根据相关意见进行编辑
- 甚至整数指数使用
pow可能会产生不正确的结果（ PaulMcKenzie ） - 除了使用doubletypes的math函数，
pow是一个函数调用（而x*x不是）（ jtbandes ） - 许多现代编译器实际上会用常量整数参数来优化pow，但是这不应该被依赖。
你已经select了一个最慢的方法来检查
c*c == a*a + b*b // assuming c is non-negative
编译成三个整数乘法（其中一个可以从循环中提升）。 即使没有pow() ，你仍然转换为double并且取一个平方根，这对吞吐量来说是很糟糕的。 （还有等待时间，但分支预测+现代CPU上的推测执行意味着延迟不是一个因素）。
英特尔Haswell的SQRTSD指令的吞吐量为每8-14个周期一个（ 来源：Agner Fog的指令表 ），所以即使您的sqrt()版本保持FP sqrt执行单元饱和，它仍然比我的gcc慢四倍发射（下图）。
当条件的b < c部分变为false时，您还可以优化循环条件以打破循环，因此编译器只需执行该检查的一个版本。
void foo_optimized() { for (int a = 1; a <= SUMTOTAL; a++) { for (int b = a+1; b < SUMTOTAL-ab; b++) { // int c = SUMTOTAL-(a+b); // gcc won't always transform signed-integer math, so this prevents hoisting (SUMTOTAL-a) :( int c = (SUMTOTAL-a) - b; // if (b >= c) break; // just changed the loop condition instead // the compiler can hoist a*a out of the loop for us if (/* b < c && */ c*c == a*a + b*b) { // Just print a newline. std::endl also flushes, which bloats the asm std::cout << "a: " << a << " b: " << b << " c: "<< c << '\n'; std::cout << a * b * c << '\n'; } } } }
这个编译（用gcc6.2 -O3 -mtune=haswell ）用这个内部循环进行编码。 请参阅Godbolt编译器资源pipe理器上的完整代码。
# a*a is hoisted out of the loop. It's in r15d .L6: add ebp, 1 # b++ sub ebx, 1 # c-- add r12d, r14d # ivtmp.36, ivtmp.43 # not sure what this is or why it's in the loop, would have to look again at the asm outside cmp ebp, ebx # b, _39 jg .L13 ## This is the loop-exit branch, not-taken until the end ## .L13 is the rest of the outer loop. ## It sets up for the next entry to this inner loop. .L8: mov eax, ebp # multiply a copy of the counters mov edx, ebx imul eax, ebp # b*b imul edx, ebx # c*c add eax, r15d # a*a + b*b cmp edx, eax # tmp137, tmp139 jne .L6 ## Fall-through into the cout print code when we find a match ## extremely rare, so should predict near-perfectly
在Intel Haswell上，所有这些指令都是1Uop。 （并且cmp / jcc对macros观融合成比较分支微分）。这就是10个融合域微分， 每2.5个循环一次迭代就可以发出 。
Haswell以每时钟一次的吞吐量运行imul r32, r32 ，所以内循环内的两次乘法不会使端口1饱和，每2.5c两次乘法。 这留下了空间来吸收从ADD和SUB窃取端口1不可避免的资源冲突。
我们甚至没有接近任何其他的执行端口瓶颈，所以前端瓶颈是唯一的问题，并且这应该在Intel Haswell及更高版本的每2.5个周期迭代一次 。
循环展开可以帮助这里减less每次检查的uops数量。 例如使用lea ecx, [rbx+1]来计算下一次迭代的b + 1，所以我们可以在不使用MOV的情况下使imul ebx, ebx无破坏性。
强度的降低也是可能的 ：给定b*b我们可以尝试计算(b-1) * (b-1)而不需要IMUL。 (b-1) * (b-1) = b*b - 2*b + 1 ，所以也许我们可以做一个lea ecx, [rbx*2 - 1]然后从b*b减去。 （没有寻址模式可以减去而不是增加，嗯，也许我们可以保存-b在一个寄存器，并计数到零，所以我们可以使用lea ecx, [rcx + rbx*2 - 1]来更新b*b ECX中的-b在EBX中给出-b ）。
除非你真的在IMUL吞吐量方面遇到瓶颈，否则这可能会导致更多的微软，而不是一个胜利。 看看编译器如何在C ++源代码中减less这个强度可能是有趣的。
你也可以用SSE或AVX对它进行vector化 ，并行检查4或8个连续的b值。 由于命中是非常罕见的，你只要检查是否有任何8击中，然后在罕见的情况下，哪一个匹配。
另请参阅x86标签维基以获取更多优化内容。
