为什么内联函数的效率比内置函数低？

Question

为什么内联函数的效率比内置函数低？

23

我是一个有用的助手，可以翻译文本。

我正在尝试InterviewBit中有关数组的问题。在这个问题中，我编写了一个内联函数来返回整数的绝对值。但是我被告知，我的算法在提交时效率不高。但是当我改用C ++库中的abs()时，它得到了一个正确的答案。

这是我的函数，它得到了一个低效的判断 -

inline int abs(int x){return x>0 ? x : -x;}

int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
    int l = X.size();
    int i = 0;
    int ans = 0;
    while (i<l-1){
        ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
        i++;
    }
    return ans;
}

这是得到了正确答案的那一个 -

int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
    int l = X.size();
    int i = 0;
    int ans = 0;
    while (i<l-1){
        ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
        i++;
    }
    return ans;
}

为什么会发生这种情况呢？我认为内联函数是最快的，因为不需要调用。难道这个网站出错了吗？如果网站是正确的，那么C++中的abs()比inline abs()更快，它使用了什么技术呢？

- monster

8

你可以给InterviewBit网站（hello@interviewbit.com）发送电子邮件并报告一个错误。向他们发送此问题的链接，以便他们改进他们的网站，或者如果这不是一个错误，则向我们发送一些调试数据（例如代码失败的测试用例）。 - anatolyg

17

你对 for 循环过敏吗？为什么要写那个 while，而不是写更常用的 for (int i = 0; i < l-1; i++) { 呢？（你还可以将 l-1 的计算提出循环条件外）此外，使用 ans += max(...) 会更符合良好的编程风格。 - Peter Cordes

是的，当我使用for循环时，我会起皮疹，你怎么知道的？：p - monster

2

除了for循环和+=之外，你应该养成使用++i而不是后缀的习惯（虽然在这里没有关系），并且注意Stroustrup教授将指针修饰符与类型而不是变量放在一起：char* p。这实际上是他原始书籍中介绍C++给公众的第一件事。哦，还有不要把某些东西命名为l。即使它作为后缀在语言中使用，也选择大写字母以避免看起来模糊不清。 - JDługosz

你的X和Y参数不是“const”。你是想说在工作时允许销毁它们吗？ - JDługosz

3个回答

20

你的abs根据条件执行分支。虽然内置变体只是从整数中删除符号位，但很可能只使用几条指令。可能的汇编示例（取自此处）：

cdq
xor eax, edx
sub eax, edx

cdq指令将寄存器eax的符号位复制到edx寄存器。例如，如果它是一个正数，则edx将为零，否则edx将为0xFFFFFF，表示-1。与原始数字的异或操作如果是正数则不会改变任何东西（任何数字异或0都不会改变）。但是，当eax为负数时，eax异或0xFFFFFF将得到（非eax）。最后一步是从eax中减去edx。同样，如果eax是正数，则edx为零，最终值仍然相同。对于负值，（~ eax）-（-1）= -eax，这是所需的值。

正如您所看到的，此方法仅使用三个简单的算术指令，根本没有条件分支。

编辑：经过一些研究，发现许多内置的abs实现都使用相同的方法，return __x >= 0 ? __x : -__x;，这种模式是编译器优化的明显目标，以避免不必要的分支。

然而，这并不能证明使用自定义的abs实现是合理的，因为它违反了DRY原则，没有人能保证你的实现在更复杂的场景和/或不寻常的平台上也同样出色。通常只有在现有实现存在明显性能问题或其他缺陷时，才应考虑重写某些库函数。 编辑2：仅从int切换到float就会导致显著的性能下降：

float libfoo(float x)
{
    return ::std::fabs(x);
}

andps   xmm0, xmmword ptr [rip + .LCPI0_0]

还有一个自定义版本：

inline float my_fabs(float x)
{
    return x>0.0f?x:-x;
}

float myfoo(float x)
{
    return my_fabs(x);
}

movaps  xmm1, xmmword ptr [rip + .LCPI1_0] # xmm1 = [-0.000000e+00,-0.000000e+00,-0.000000e+00,-0.000000e+00]
xorps   xmm1, xmm0
xorps   xmm2, xmm2
cmpltss xmm2, xmm0
andps   xmm0, xmm2
andnps  xmm2, xmm1
orps    xmm0, xmm2

online compiler

- user7860670

5

最重要的是，内置的设计不会因为随机数据而出现分支预测失败，从而使指令高速缓存更友好。 - StoryTeller - Unslander Monica

4

@StoryTeller：在条件移动中，并不存在分支预测失败这一说法。 - Damon

4

没有优化编译器会为 OP 的 abs() 函数生成一个分支语句。 - geza

3

稍微跑题了，但无论如何我还是会添加一个评论...我非常支持DRY原则，但当考虑到无法打破或弯曲的规则时，我们通常会陷入同样糟糕的开发质量境地。DRY确实会将代码耦合在一起，这也是我们需要考虑的平衡。 - Jamie

3

关于浮点数版本：由于编译器使用了严格的浮点数算法，所以它不能优化掉那段代码。如果您添加了“-ffast-math”选项，您将得到同样好的解决方案。 - geza

显示剩余11条评论

8

您的解决方案可能从教科书的角度来看使用标准库版本会更“规范”，但我认为评估结果是错误的。你的代码被拒绝没有真正好的、合理的原因。

这是一个典型的例子，某人在形式上是正确的（按照教科书要求），但却执意以单一愚蠢的方式坚持认为只有唯一正确的解决方案，而无法接受其他解决方案并说出"...但这里是最佳实践，你知道的"。

在技术上来说，说"使用标准库，那就是它的用途，并且已经尽可能地优化了"，是一种正确、实用的方法。虽然有时候"尽可能地优化"这部分会因为标准对于某些算法和/或容器的限制而出现错误。

现在，撇开观点、最佳实践和信仰不谈。事实上，如果您比较这两个方法...

int main(int argc, char**)
{
  40f360:       53                      push   %rbx
  40f361:       48 83 ec 20             sub    $0x20,%rsp
  40f365:       89 cb                   mov    %ecx,%ebx
  40f367:       e8 a4 be ff ff          callq  40b210 <__main>
return std::abs(argc);
  40f36c:       89 da                   mov    %ebx,%edx
  40f36e:       89 d8                   mov    %ebx,%eax
  40f370:       c1 fa 1f                sar    $0x1f,%edx
  40f373:       31 d0                   xor    %edx,%eax
  40f375:       29 d0                   sub    %edx,%eax
//}

int main(int argc, char**)
{
  40f360:       53                      push   %rbx
  40f361:       48 83 ec 20             sub    $0x20,%rsp
  40f365:       89 cb                   mov    %ecx,%ebx
  40f367:       e8 a4 be ff ff          callq  40b210 <__main>
return (argc > 0) ? argc : -argc;
  40f36c:       89 da                   mov    %ebx,%edx
  40f36e:       89 d8                   mov    %ebx,%eax
  40f370:       c1 fa 1f                sar    $0x1f,%edx
  40f373:       31 d0                   xor    %edx,%eax
  40f375:       29 d0                   sub    %edx,%eax
//}

......它们产生完全相同的指令。

但是，即使编译器使用比较后跟条件移动（在更复杂的“分支赋值”中可能会这样做，在min/max的情况下也会这样做），那么与位操作相比，这可能慢了一个CPU周期左右，因此，除非您这样做数百万次，否则说“不高效”这个说法是有点可疑的。
一次缓存未命中，您就会受到条件移动100倍的惩罚。

对于任何一种方法都有有效的支持和反对的论据，我不会详细讨论。我的观点是，因为如此微不足道的细节而将OP的解决方案拒之门外是相当狭隘的。

编辑：

（有趣的小知识）

我只是出于好玩，没有利润，在我的Linux Mint桌面上尝试了一下，该桌面使用了较旧版本的GCC（5.4与上面的7.1相比）。

由于我没有多想就包含了<cmath>（嘿，像abs这样的函数显然属于数学，不是吗！）而没有使用整数重载的<cstdlib>，结果是...... 令人惊讶。调用库函数比单表达式包装程序要差得多。

现在，为了维护标准库，如果您包含<cstdlib>，那么无论哪种情况下产生的输出都完全相同。

供参考，测试代码如下：

#ifdef DRY
  #include <cmath>
  int main(int argc, char**)
  {
     return std::abs(argc);
  }
#else
  int abs(int v) noexcept { return (v >= 0) ? v : -v; }
  int main(int argc, char**)
  {
     return abs(argc);
  }
#endif

...导致

4004f0: 89 fa                   mov    %edi,%edx
4004f2: 89 f8                   mov    %edi,%eax
4004f4: c1 fa 1f                sar    $0x1f,%edx
4004f7: 31 d0                   xor    %edx,%eax
4004f9: 29 d0                   sub    %edx,%eax
4004fb: c3                      retq

现在，很容易陷入不知不觉使用错误标准库函数的陷阱中（我自己演示了它是多么容易！）。而且所有这些都没有任何来自编译器的警告，比如“嘿，你知道吗，你正在对整数值使用双重重载（显然没有警告，这是有效的转换）”。

考虑到这一点，可能还有另一个“理由”解释为什么OP提供自己的一行代码并不是那么糟糕和错误的。毕竟，他也可能犯同样的错误。

- Damon

所以你使用的库实现有一个天真的abs。那又怎样？你不能保证总是得到超级优化的版本，但你可以。这会产生巨大的差异，就像OP的代码一样。 - StoryTeller - Unslander Monica

1

问题不在于分支的额外周期，而在于分支的额外周期+分支预测失败的额外周期+指令缓存变脏所带来的影响。这可能会造成一些严重的惩罚，具体取决于数据的分布情况。而“位运算技巧”则不会造成这种问题。 - StoryTeller - Unslander Monica

@StoryTeller 这是相反的情况。编译器将自定义的naive abs视为等同于abs并替换为与库abs生成的相同指令。 - user743382

5

你落入了和VTT一样的陷阱中。使用cstdlib而不是cmath。 - geza

1

标量double是一个常数，除了符号位之外的所有位都被设置。按位与运算清除符号位是在SSE寄存器中实现浮点/双精度绝对值的最快方法。单独一行的00是因为movsd指令很长而进行的换行。使用objdump -dw禁用长指令换行。(我使用alias disas='objdump -drwC -Mintel')。正如geza所说，这只发生在您忘记为std::abs()的整数重载包含<cstdlib>头文件时。愚蠢的C++。 - Peter Cordes

显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- geza · Accepted Answer

我不同意他们的裁决。他们明显是错误的。

在当前的优化编译器上，这两个解决方案都会产生完全相同的输出。即使它们没有产生完全相同的输出，它们也会产生像库函数一样高效的代码（可能有点令人惊讶，因为算法、使用的寄存器都匹配。也许实际的库实现与 OP 的实现相同？）。

如果可以在没有分支的情况下完成，任何明智的优化编译器都不会在您的 abs() 代码中创建分支，就像其他答案建议的那样。如果编译器没有进行优化，则可能不会内联库函数 abs()，因此速度也不会很快。

对于编译器来说，优化 abs() 是最简单的事情之一（只需在 peephole 优化器中添加一个条目即可）。

此外，过去我曾见过一些库实现，其中 abs() 被实现为非内联库函数（虽然那是很久以前的事了）。

证明这两个实现是相同的：

GCC：

myabs:
    mov     edx, edi    ; argument passed in EDI by System V AMD64 calling convention
    mov     eax, edi
    sar     edx, 31
    xor     eax, edx
    sub     eax, edx
    ret

libabs:
    mov     edx, edi    ; argument passed in EDI by System V AMD64 calling convention
    mov     eax, edi
    sar     edx, 31
    xor     eax, edx
    sub     eax, edx
    ret

Clang：

myabs:
    mov     eax, edi    ; argument passed in EDI by System V AMD64 calling convention
    neg     eax
    cmovl   eax, edi
    ret

libabs:
    mov     eax, edi    ; argument passed in EDI by System V AMD64 calling convention
    neg     eax
    cmovl   eax, edi
    ret

Visual Studio（MSVC）：

libabs:
    mov      eax, ecx    ; argument passed in ECX by Windows 64-bit calling convention 
    cdq
    xor      eax, edx
    sub      eax, edx
    ret      0

myabs:
    mov      eax, ecx    ; argument passed in ECX by Windows 64-bit calling convention 
    cdq
    xor      eax, edx
    sub      eax, edx
    ret      0

国际刑事法院：

myabs:
    mov       eax, edi    ; argument passed in EDI by System V AMD64 calling convention 
    cdq
    xor       edi, edx
    sub       edi, edx
    mov       eax, edi
    ret      

libabs:
    mov       eax, edi    ; argument passed in EDI by System V AMD64 calling convention 
    cdq
    xor       edi, edx
    sub       edi, edx
    mov       eax, edi
    ret