C++性能：列表和迭代器

Question

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

使用 g++ 在 Linux 上构建调试/配置文件版本 (-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 类由整数、浮点数、双精度数、布尔值和字符串组成）

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

我无法共享代码，但是根据您的经验，是否有一些明显的原因（除了我有限的 C++ 经验之外）？

Answer 1

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

您需要使用列表吗？

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

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

事实上，运算符 != 位于列表的顶部，这使得它看起来像这样。谁这么叫的，为什么？如果您正在进行大量搜索并且这在您的运行时占据主导地位，那么您可能还需要考虑不同的数据结构，如果您进行大量插入和查找，则可能是二叉搜索树或哈希表。

Answer 2

因为最上面的项目是距离、operator++ 和operator!= 我相信您的问题是在列表上使用 size() 操作。

这是 C++ 标准允许不同实现的领域之一。 MSVC 实现将列表的大小存储为数字，因此返回值非常快。 GCC 没有，因此要获取列表的大小，它必须执行以下操作：

count = 0;
for(
    list::iterator it = l.begin()
    it != l.end();
    ++it
)
    ++count;

在该循环中，您可以看到配置文件顶部的每个操作。