for循环中pIter！= cont.end（）的性能-Java 学习之路

我最近通过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)

对我来说，这是不必要的并发症 . 即使用紧凑的 auto 替换丑陋的类型声明，他仍然会得到两行代码而不是一行代码 . 更重要的是，他在外部范围内有这个变量 .

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

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

Update

感谢您就如何更好地制作这些无用的代码提出建议 . 请注意，我的问题是关于编译器，而不是编程技术 . 目前唯一相关的答案来自NPE和Ellioh .

7 回答

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

#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 "";
}

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

回复于 2024-04-20T15:32:20+08:00

UPD: 你所讲的这本书已于1999年出版，除非我在14年前，并且在现代节目中14年是很多时间 . 许多在1999年都很好和可靠的建议现在可能已经完全过时了 . 虽然我的答案是关于单个编译器和单个平台，但还有一个更一般的想法 .

关注额外的变量，重用琐碎方法的返回值和旧C的类似技巧，是朝着20世纪90年代的C退一步 . 像 end() 这样的简单方法应该很好地内联，并且内联的结果应该作为调用它的代码的一部分进行优化 . 99％的情况不需要手动操作，例如创建 end 变量 . 这样的事情应该只在以下情况下完成

你知道你应该在代码上运行的某些编译器/平台没有很好地优化 .
它已成为您程序的瓶颈（"avoid premature optimization"） .

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

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

最初我认为优化它应该没问题，两个版本之间应该没有区别 . 但看起来很奇怪： the version you considered non-optimal is actually better . 我认为，道德是： there is no reason to try being smarter than a compiler . 我们来看两个版本 .

#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>

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

回复于 2024-04-20T15:32:20+08:00

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

在这两种情况下，我将生成的代码与问题中的代码进行比较（使用 Headers 添加以便编译），代码如下：
```
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 ，但是（再次）这完全无关紧要 .

底线：不，你不可能通过现代编译器从循环中手动提升代码获得任何收益（至少启用了优化 - 我使用带有VC的 /O2b2 和带有g的 /O3 ;将优化与优化进行比较关闭似乎对我来说毫无意义） .
回复于 2024-04-20T15:32:20+08:00
3
一些事情......首先，通常构建迭代器的成本（在发布模式下，未经检查的分配器）是最小的 . 它们通常是指针周围的包装器 . 使用已检查的分配器（在VS中为默认值），您可能会有一些成本，但如果确实需要性能，则在使用未经检查的分配器测试重建之后 .

代码不必像你发布的那样难看：
```
for (list<Employee>::const_iterator it=emps.begin(), end=emps.end(); 
                                    it != end; ++it )
```
关于是否要使用一种或另一种方法的主要决定应该是对容器应用的操作 . 如果容器可能正在更改它的大小，那么您可能希望在每次迭代中重新计算 end 迭代器 . 如果没有，您可以预先计算一次并重复使用上面的代码 .
回复于 2024-04-20T15:32:20+08:00
8
像vector这样的容器返回变量，它在 end() 调用上存储了指向结尾的指针，并进行了优化 . 如果您已经编写了容器，它会对 end() 上的某些查找等进行调用，请考虑编写
```
for (list<Employee>::const_iterator i = emps.begin(), end = emps.end(); i != end; ++i)
{
...
}
```
为了速度
回复于 2024-04-20T15:32:20+08:00
2
如果你真的需要性能，你可以让你的闪亮的新C 11编译器为你编写它：
```
for (const auto &i : emps) {
    /* ... */
}
```
是的，这是诙谐的（有点） . 赫伯的例子现在已经过时了 . 但由于你的编译器还不支持它，让我们来看看真正的问题：

这是一种我可以依靠编译器进行优化的构造吗？

我的经验法则是编译器编写者比我更聪明 . 我不能依靠编译器来优化任何一段代码，因为它可能会选择优化其他具有更大影响的东西 . 确切知道的唯一方法是在 your 系统上的 your 编译器上试用这两种方法，看看会发生什么 . 检查您的探查器结果 . 如果对 .end() 的调用突然出现，请将其保存在单独的变量中 . 否则，不要担心 .
回复于 2024-04-20T15:32:20+08:00
0

使用标准算法

他是对的;调用 end 可以实例化和销毁一个临时对象，这通常很糟糕 .

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

有一个更好，更强大的解决方案： encapsulate your loops .

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

因此，隐藏函数中的循环并将 const& 转换为 end . 与您的示例相同，但更清洁 .

回复于 2024-04-20T15:32:20+08:00

for循环中pIter！= cont.end（）的性能

7 回答

使用标准算法

相关问题