c++ - 解释两种几乎相同算法的性能差异

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。我没有包含在代码中的所有内容在两种算法中都是相同的。我猜 vector 中的存储一直在吃掉，但如果我没记错的话，C++ vector 的大小每次被溢出时都会加倍，所以重新分配不应该经常发生。 有什么想法吗？

Answer 1

我猜额外的时间是由于在 vector 中复制矩阵造成的。根据您提供的时间，一次遍历数据需要 20 或 170 毫秒，这对于大量复制来说是正确的数量级。

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

现在你可能会说:但是当我将它们传递给递归调用时我也在复制矩阵，我不应该期望第一个算法最多花费第二个算法的三倍时间吗？
答案是，如果堆上数据的缓存利用率不受阻碍，任何递归体面的缓存都非常友好。因此，几乎所有在递归体面中完成的复制甚至都没有到达 L2 缓存。如果您不时通过执行 vector 重新分配来破坏整个缓存，之后您将使用完全冷的缓存恢复。