performance - C++ 性能 : lists and iterators

Question

我有一些继承的内部 C++ 代码，在 Windows 上用 VC++ 编译时，运行速度比在 Linux 上用 g++ 编译时快一个数量级(5 分钟 vs. 2 小时)。无论有没有“正常”优化标志，以及每个编译器和相应平台的几个不同版本，都在可比的硬件上，情况仍然如此。

在 Linux 上使用 g++ 构建调试/配置文件版本 (-g -pg)，我看到以下三个区域大部分时间都在消耗:

%   cumulative   self              self     total
time   seconds   seconds    calls  Ks/call  Ks/call  name
31.95    955.93   955.93 3831474321     0.00     0.00  std::_List_const_iterator<xxFile>::operator!=(std::_List_const_iterator<xxFile> const&) const
22.51   1629.64   673.71 3144944335     0.00     0.00  std::_List_const_iterator<xxFile>::operator++()
15.56   2095.29   465.65 686529986      0.00     0.00  std::iterator_traits<std::_List_const_iterator<dtFile> >::difference_type std::__distance<std::_List_const_iterator<xxFile> >(std::_List_const_iterator<xxFile>, std::_List_const_iterator<xxFile>, std::input_iterator_tag)

(xxFile 类由整数、浮点数、 double 数、 bool 值和字符串组成)

我天真的猜测是 VC++ 正在补偿某些编码不佳的东西，或者 GNU STL 可能没有优化。我目前正在使用 Boost 库编译 g++/Linux 版本，从 assign/std/list.hpp 和 boost::assign 命名空间开始。

我无法分享代码，但根据您的经验，是否有明显的原因(除了我有限的 C++ 经验)跳出原因？

Answer 1

除了花费大量时间迭代列表之外，我会在不了解您的代码的情况下扔掉一些东西。

你需要使用列表吗？

如果您的大部分时间都花在迭代上，也许您应该使用连续的数据结构(数组/向量)。除非您出于其他原因需要列表行为(即，在其他地方进行大量插入，否则可能会支配您的运行时)，由于内存局部性，使用数组应该会提供更好的性能。尽管迭代数组和列表都是 O(n)，但实际上由于适当利用了 CPU 的缓存，数组可以快得多。当你浏览一个列表->next 时，你不知道你会在哪里结束，如果你最终总是出现页面错误，你的性能会很糟糕。

您是否进行了大量搜索？也许很多线性搜索？

运算符 != 位于列表顶部的事实使其显示为这种方式。谁在调用它，为什么？如果您进行了大量搜索并且这在您的运行时中占主导地位，您可能还需要考虑不同的数据结构，如果您进行大量插入和查找，则可能是二叉搜索树或哈希表。