c++ - pIter != cont.end() 在 for 循环中的性能

Question

我最近正在阅读 Herb Sutter 的“Exceptional C++”，我对他在第 6 项 - 临时对象中给出的特定建议表示严重怀疑。

他提出在以下代码中查找不必要的临时对象：

string FindAddr(list<Employee> emps, string name) 
{
  for (list<Employee>::iterator i = emps.begin(); i != emps.end(); i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

作为示例之一，他建议emps.end()在循环之前预先计算的值，因为每次迭代都会创建一个临时对象：

对于大多数容器（包括列表），调用 end() 返回一个必须构造和销毁的临时对象。因为值不会改变，所以在每次循环迭代中重新计算（以及重建和重新销毁）它既不必要地低效又不美观。该值应该只计算一次，存储在本地对象中并重复使用。

他建议替换为以下内容：

list<Employee>::const_iterator end(emps.end());
for (list<Employee>::const_iterator i = emps.begin(); i != end; ++i)

对我来说，这是不必要的复杂化。即使有人用 compact 替换了丑陋的类型声明auto，他仍然得到两行代码而不是一行。更重要的是，他end在外部范围内有这个变量。

我确信现代编译器无论如何都会优化这段代码，因为我实际上const_iterator在这里使用并且很容易检查循环内容是否以某种方式访问容器。编译器在过去 13 年里变得更聪明了，对吧？

无论如何，在大多数情况下，我会更喜欢第一个版本i != emps.end()，我不太担心性能。但我想确定的是，这是否是一种我可以依靠编译器来优化的结构？

更新

感谢您对如何使这个无用的代码变得更好的建议。请注意，我的问题是关于编译器，而不是编程技术。目前唯一相关的答案来自NPE和Ellioh。

score 12 · Accepted Answer

UPD：你所说的这本书已经出版于 1999 年，除非我弄错了。那是 14 年前的事了，在现代编程中，14 年是很多时间。许多在 1999 年很好且可靠的建议现在可能已经完全过时了。虽然我的回答是关于单一编译器和单一平台，但也有一个更普遍的想法。

关心额外的变量、重用琐碎方法的返回值和旧 C++ 的类似技巧是向 1990 年代 C++ 的倒退。像这样的普通方法end()应该被很好地内联，并且内联的结果应该作为调用它的代码的一部分进行优化。99% 的情况根本不需要手动操作，例如创建end变量。只有在以下情况下才应该这样做：

你知道在一些你应该在代码上运行的编译器/平台上没有得到很好的优化。
它已成为您程序中的瓶颈（“避免过早优化”）。

我查看了 64 位 g++ 生成的内容：

gcc version 4.6.3 20120918 (prerelease) (Ubuntu/Linaro 4.6.3-10ubuntu1)

最初我认为对其进行优化应该没问题，两个版本之间应该没有区别。但看起来事情很奇怪：您认为非最佳的版本实际上更好。我认为，道德是：没有理由尝试比编译器更聪明。让我们看看这两个版本。

#include <list>

using namespace std;

int main() {
  list<char> l;
  l.push_back('a');

  for(list<char>::iterator i=l.begin(); i != l.end(); i++)
      ;

  return 0;
}

int main1() {
  list<char> l;
  l.push_back('a');
  list<char>::iterator e=l.end();
  for(list<char>::iterator i=l.begin(); i != e; i++)
      ;

  return 0;
}

然后我们应该通过优化（我使用 64 位g++，你可以试试你的编译器）和反汇编来编译main它main1：

对于main：

(gdb) disas main
Dump of assembler code for function main():
   0x0000000000400650 <+0>: push   %rbx
   0x0000000000400651 <+1>: mov    $0x18,%edi
   0x0000000000400656 <+6>: sub    $0x20,%rsp
   0x000000000040065a <+10>:    lea    0x10(%rsp),%rbx
   0x000000000040065f <+15>:    mov    %rbx,0x10(%rsp)
   0x0000000000400664 <+20>:    mov    %rbx,0x18(%rsp)
   0x0000000000400669 <+25>:    callq  0x400630 <_Znwm@plt>
   0x000000000040066e <+30>:    cmp    $0xfffffffffffffff0,%rax
   0x0000000000400672 <+34>:    je     0x400678 <main()+40>
   0x0000000000400674 <+36>:    movb   $0x61,0x10(%rax)
   0x0000000000400678 <+40>:    mov    %rax,%rdi
   0x000000000040067b <+43>:    mov    %rbx,%rsi
   0x000000000040067e <+46>:    callq  0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt>
   0x0000000000400683 <+51>:    mov    0x10(%rsp),%rax
   0x0000000000400688 <+56>:    cmp    %rbx,%rax
   0x000000000040068b <+59>:    je     0x400698 <main()+72>
   0x000000000040068d <+61>:    nopl   (%rax)
   0x0000000000400690 <+64>:    mov    (%rax),%rax
   0x0000000000400693 <+67>:    cmp    %rbx,%rax
   0x0000000000400696 <+70>:    jne    0x400690 <main()+64>
   0x0000000000400698 <+72>:    mov    %rbx,%rdi
   0x000000000040069b <+75>:    callq  0x400840 <std::list<char, std::allocator<char> >::~list()>
   0x00000000004006a0 <+80>:    add    $0x20,%rsp
   0x00000000004006a4 <+84>:    xor    %eax,%eax
   0x00000000004006a6 <+86>:    pop    %rbx
   0x00000000004006a7 <+87>:    retq

查看位于 0x0000000000400683-0x000000000040068b 的命令。那是循环体，它似乎被完美优化：

   0x0000000000400690 <+64>:    mov    (%rax),%rax
   0x0000000000400693 <+67>:    cmp    %rbx,%rax
   0x0000000000400696 <+70>:    jne    0x400690 <main()+64>

对于main1：

(gdb) disas main1
Dump of assembler code for function main1():
   0x00000000004007b0 <+0>: push   %rbp
   0x00000000004007b1 <+1>: mov    $0x18,%edi
   0x00000000004007b6 <+6>: push   %rbx
   0x00000000004007b7 <+7>: sub    $0x18,%rsp
   0x00000000004007bb <+11>:    mov    %rsp,%rbx
   0x00000000004007be <+14>:    mov    %rsp,(%rsp)
   0x00000000004007c2 <+18>:    mov    %rsp,0x8(%rsp)
   0x00000000004007c7 <+23>:    callq  0x400630 <_Znwm@plt>
   0x00000000004007cc <+28>:    cmp    $0xfffffffffffffff0,%rax
   0x00000000004007d0 <+32>:    je     0x4007d6 <main1()+38>
   0x00000000004007d2 <+34>:    movb   $0x61,0x10(%rax)
   0x00000000004007d6 <+38>:    mov    %rax,%rdi
   0x00000000004007d9 <+41>:    mov    %rsp,%rsi
   0x00000000004007dc <+44>:    callq  0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt>
   0x00000000004007e1 <+49>:    mov    (%rsp),%rdi
   0x00000000004007e5 <+53>:    cmp    %rbx,%rdi
   0x00000000004007e8 <+56>:    je     0x400818 <main1()+104>
   0x00000000004007ea <+58>:    mov    %rdi,%rax
   0x00000000004007ed <+61>:    nopl   (%rax)
   0x00000000004007f0 <+64>:    mov    (%rax),%rax
   0x00000000004007f3 <+67>:    cmp    %rbx,%rax
   0x00000000004007f6 <+70>:    jne    0x4007f0 <main1()+64>
   0x00000000004007f8 <+72>:    mov    (%rdi),%rbp
   0x00000000004007fb <+75>:    callq  0x4005f0 <_ZdlPv@plt>
   0x0000000000400800 <+80>:    cmp    %rbx,%rbp
   0x0000000000400803 <+83>:    je     0x400818 <main1()+104>
   0x0000000000400805 <+85>:    nopl   (%rax)
   0x0000000000400808 <+88>:    mov    %rbp,%rdi
   0x000000000040080b <+91>:    mov    (%rdi),%rbp
   0x000000000040080e <+94>:    callq  0x4005f0 <_ZdlPv@plt>
   0x0000000000400813 <+99>:    cmp    %rbx,%rbp
   0x0000000000400816 <+102>:   jne    0x400808 <main1()+88>
   0x0000000000400818 <+104>:   add    $0x18,%rsp
   0x000000000040081c <+108>:   xor    %eax,%eax
   0x000000000040081e <+110>:   pop    %rbx
   0x000000000040081f <+111>:   pop    %rbp
   0x0000000000400820 <+112>:   retq

循环的代码类似，它是：

   0x00000000004007f0 <+64>:    mov    (%rax),%rax
   0x00000000004007f3 <+67>:    cmp    %rbx,%rax
   0x00000000004007f6 <+70>:    jne    0x4007f0 <main1()+64>

但是循环周围有很多额外的东西。显然，额外的代码使事情变得更糟。

score 8 · Accepted Answer

我已经使用g++ 4.7.2with编译了以下稍微有点 hacky 的代码-O3 -std=c++11，并为这两个函数获得了相同的程序集：

#include <list>
#include <string>

using namespace std;

struct Employee: public string { string addr; };

string FindAddr1(list<Employee> emps, string name)
{
  for (list<Employee>::const_iterator i = emps.begin(); i != emps.end(); i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

string FindAddr2(list<Employee> emps, string name)
{
  list<Employee>::const_iterator end(emps.end());
  for (list<Employee>::const_iterator i = emps.begin(); i != end; i++)
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

无论如何，我认为这两个版本之间的选择应该主要基于可读性。如果没有分析数据，像这样的微优化在我看来还为时过早。

score 4 · Accepted Answer

与普遍的看法相反，我认为 VC++ 和 gcc 在这方面没有任何区别。我对 g++ 4.7.2 和 MS C++ 17（又名 VC++ 2012）进行了快速检查。

在这两种情况下，我将生成的代码与问题中的代码（添加了标题等以使其编译）与以下代码进行了比较：

string FindAddr(list<Employee> emps, string name) 
{
    auto end = emps.end();
    for (list<Employee>::iterator i = emps.begin(); i != end; i++)
    {
        if( *i == name )
        {
            return i->addr;
        }
    }
    return "";
}

在这两种情况下，两段代码的结果基本相同。VC++ 在代码中包含行号注释，由于额外的行而改变了，但这是唯一的区别。使用 g++，输出文件是相同的。

std::vector用而不是做同样的std::list事情，得到了几乎相同的结果——没有显着差异。出于某种原因，g++ 确实将一条指令的操作数顺序从cmp esi, DWORD PTR [eax+4]切换到cmp DWORD PTR [eax+4], esi，但是（再次）这完全无关紧要。

底线：不，您不太可能通过使用现代编译器手动将代码提升出循环来获得任何收益（至少在启用优化的情况下——我使用/O2b2的是 VC++ 和/O3g++；比较优化与关闭的优化似乎对我来说毫无意义）。

score 3 · Accepted Answer

有几件事……首先是构建迭代器（在发布模式下，未经检查的分配器）的成本通常是最低的。它们通常是指针的包装器。使用检查的分配器（VS 中的默认值）您可能需要一些成本，但如果您真的需要性能，请在使用未检查的分配器测试重建后。

代码不必像您发布的那样丑陋：

for (list<Employee>::const_iterator it=emps.begin(), end=emps.end(); 
                                    it != end; ++it )

关于是否要使用一种或其他方法的主要决定应该是对容器应用哪些操作。如果容器可能正在改变它的大小，那么您可能希望end在每次迭代中重新计算迭代器。如果没有，您可以像上面的代码一样预先计算一次并重用。

score 3 · Accepted Answer

如果您真的需要性能，您可以让闪亮的新 C++11 编译器为您编写它：

for (const auto &i : emps) {
    /* ... */
}

是的，这是开玩笑的（有点）。Herb 在这里的例子现在已经过时了。但是由于你的编译器还不支持它，让我们来看看真正的问题：

这是一种我可以依靠编译器来优化的结构吗？

我的经验法则是编译器编写者比我聪明得多。我不能依赖编译器来优化任何一段代码，因为它可能会选择优化其他影响更大的东西。唯一确定的方法是在系统上的编译器上尝试这两种方法，看看会发生什么。检查您的探查器结果。如果调用到突出，请将其保存在单独的变量中。否则，不要担心。.end()

score 2 · Accepted Answer

像向量这样的容器返回变量，该变量存储指向末尾的指针，在end()调用时进行优化。如果您编写了可以进行一些查找等操作的容器，end()请考虑编写

for (list<Employee>::const_iterator i = emps.begin(), end = emps.end(); i != end; ++i)
{
...
}

为了速度

score 0 · Accepted Answer

使用`std`算法

他当然是对的；调用end可以实例化和销毁一个临时对象，这通常是不好的。

当然，编译器可以在很多情况下优化它。

有一个更好更健壮的解决方案：封装你的循环。

您给出的示例实际上是std::find，给或取返回值。许多其他循环也有std算法，或者至少有足够相似的东西可以适应——transform_if例如，我的实用程序库有一个实现。

因此，隐藏函数中的循环并使用const&to end。与您的示例相同的修复程序，但更清洁。

c++ - pIter != cont.end() 在 for 循环中的性能

7 回答 7

使用std算法

Related

Reference

使用`std`算法