解释两个几乎相同算法的性能差异

Question

这个问题比较模糊，我并不是真的需要一个答案，但是我非常好奇答案可能是什么，所以我还是要问一下。

我有一个生成大量矩阵的算法。稍后它会运行第二个算法来生成解决方案。我运行了100次，平均需要约17秒。

第二个算法几乎完全相同，唯一的区别是在每个矩阵生成时就运行第二个算法，这样它们实际上不需要存储在任何地方。这种变体显然需要更少的空间，这也是我制作它的原因，但对于同一个问题，它只需要平均约2秒钟。

我没有预料到它会运行得更快，尤其是那么多。

代码相当复杂，所以我将尝试用类似伪代码的方式概述差异。

recursiveFill(vector<Matrix> &cache, Matrix permutation) {
  while(!stopCondition) {
    // generate next matrix from current permutation
    if(success)
      cache.push_back(permutation);
    else
      recursiveFill(cache, permutation);
    // some more code
  }
}

recursiveCheck(Matrix permutation) {
  while(!stopCondition) {
    // alter the matrix some
    if(success)
      checkAlgorithm(permutation);
    else
      recursiveCheck(permutation);
    // some more code
  }
}

在递归填充后，循环运行checkAlgorithm来检查缓存中的所有元素。两个算法除了我未在代码中包含的内容之外完全相同。我猜存储在向量中是耗费所有时间的原因，但如果我记得正确的话，C++向量的大小每次超出限制时都会翻倍，所以重新分配不应该发生太频繁。 有什么想法吗？

- Arne

---

不好意思，我不明白你在问什么。然而，std::vector的开销不仅仅在于数组被重新调整大小并因此被复制（虽然这也是其中的一部分），而且你的元素必须是可复制的才能使用std::vector，所以除非你存储指针或引用，否则你将得到完整的深度拷贝推入向量中。 - San Jacinto

cachegrind是valgrind的缓存检查工具，你可以通过在命令行中添加--tool=cachegrind来激活它。它对你的两个代码有何评价？ - cmaster - reinstate monica

这真的取决于具体实现。我猜测你不仅会产生缓存未命中，还会产生页表未命中，这时操作系统会被迫不断地进行虚拟地址的转换，因为第一个递归调用的顺序与较少顺序不同。 - Mdev

什么是“矩阵”？它使用堆分配吗？它是否可移动（并且您的编译器支持移动语义）？swap是否正确重载和有效实现？ - D Drmmr

Answer 1

这里的罪魁祸首可能是时间局部性。您的 CPU 缓存有限，因此当您保存每次运行后的所有内容并在稍后回来时，它已经离开了您的 CPU 缓存，并且需要更长的时间（10 到 100 个周期）才能访问。使用第二种方法，它就在 L1 缓存（或可能是 MMX 寄存器）中，只需一个或两个周期即可访问。

在优化中，通常要像 Wu-Tang Clan 一样思考：缓存决定一切。 一些人进行了测试，缓存中的副本通常比主内存中的解引用要便宜得多。

- Dan

---

我认为这样草率地得出结论还为时过早。并不是说你错了，但15秒的差距相当大，我们对他的缓存大小一无所知，我们对他的复制语义也一无所知等等。 - San Jacinto

缓存中的副本可能比主内存中的取消引用更便宜，但是如果你回答时表现得好像这个副本无关紧要，那你就是在进行错误的二分法。我们不知道他正在从哪里复制或复制到哪里；我们还没有看到他的实现或数据集。这个答案确实可能是最终解决方案的一部分，但就目前而言，这个答案就像医生建议患者感冒了，只因为他打了个喷嚏。 - San Jacinto

Answer 2

我猜额外的时间是由于在vector内部复制矩阵所致。根据你所提供的时间，一次数据遍历需要20或170毫秒，这在许多复制操作中是正确的数量级。

请记住，尽管由于vector重新分配而产生的复制开销是线性的，但平均每个插入的矩阵会被复制两次，一次在插入期间，一次在重新分配期间。加上复制大量数据的缓存破坏效应，这可能会产生额外的运行时。

现在你可能会说：但是当我将它们传递给递归调用时，我也在复制矩阵，难道我不应该预计第一个算法的时间最多是第二个算法的三倍吗？
答案是，如果递归下降没有受到堆上数据缓存利用的影响，那么任何递归下降都是完全友好的。因此，几乎所有递归下降中执行的复制甚至不会进入L2缓存。如果您偶尔通过进行vector重新分配来清除整个缓存，那么之后您将重新开始使用完全“冷”的缓存。

- cmaster - reinstate monica

---

这听起来很有趣。因此，使用递归填充容器可能比使用简单循环填充要慢得多？另外，我解释错了一些东西，17秒和2秒不是一个函数调用的时间，而是针对完整问题的时间，该问题是检查分支因子为5且深度为10的树，因此每次运行算法生成（并在某些情况下缓存）的矩阵总数为19,531,249个。 - Arne

谢谢提供这些数字，正是我预计的数量级 :-) 是的，我正确地读取了你的17秒，这就是为什么我将这个时间除以100得到170毫秒。 - cmaster - reinstate monica

啊，那我误解你了。谢谢你的时间！ - Arne

Answer 3

严格来说，向量并不需要每次增长都翻倍，它只需要以几何级数增长，以提供所需的摊销常数时间。

在这种情况下，如果您有足够大量的矩阵，增长和所需数据副本仍然可能是问题。或者它可能是交换来分配足够的内存。唯一确定的方法是在您遇到此差异的系统上进行分析。

- Mark B