为什么在Windows中反复进行内存分配会导致减速？

Question

我想了解为什么以下代码在我的Linux和Windows 7机器上表现不同： 在Linux上，每次迭代需要大约120毫秒。 在Windows 7上，第一次迭代就需要0.4秒，后续的迭代时间更长。第8次迭代已经需要大约11秒，第22次迭代需要大约1分钟。

我在不同的硬件上观察到了这种行为。它似乎与Windows有关。

#include <iostream>
#include <time.h>
#include <chrono>

void iteration() {
  int n = 25000;
  // Allocate memory
  long** blocks = new long*[n];
  for( int i = 0; i<n; ++i )
  {
    blocks[i] = new long[100008];
  }
  // Free all allocated memory
  for( int i = 0; i<n; ++i )
  {
    delete[] blocks[i];
  }
  delete[] blocks;
}

int main(int argc, char **argv) {
  int nbIter = 30;
  for( int i = 0; i < nbIter; ++i )
  {
    auto start = std::chrono::system_clock::now();
    iteration();
    auto end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "Iteration #" << i << ": time=" << elapsed.count() << "ms" << std::endl;
  }
  return 0;
}

有人能告诉我这里发生了什么，并且如何让代码在Windows上稳定运行吗？

编辑：我在Windows上使用VS2013进行了发布构建，我从VS之外执行了程序。 以下是一些更精确的运行时间（以秒为单位）：

Iteration #0: time=0.381000
Iteration #1: time=0.391000
Iteration #2: time=0.451000
Iteration #3: time=1.507000
Iteration #4: time=1.711000
Iteration #5: time=2.938000
Iteration #6: time=4.770000
Iteration #7: time=7.840000
Iteration #8: time=10.563000
Iteration #9: time=14.606000
Iteration #10: time=20.732000
Iteration #11: time=24.948000
Iteration #12: time=30.255000
Iteration #13: time=34.608000
Iteration #14: time=38.114000
Iteration #15: time=43.217000
Iteration #16: time=39.926000
Iteration #17: time=43.506000
Iteration #18: time=43.660000
Iteration #19: time=45.291000
Iteration #20: time=50.003000

- user6234011

---

堆实现将是编译器特定的，而不是平台特定的。在Windows上使用不同的工具链可能会产生不同的结果。事实上，有许多项目承诺通过提供自定义operator new和operator delete实现来改善受堆限制的应用程序的性能。 - Chris Becke

你确定 iteration 没有被编译掉吗？它没有任何作用或产生任何副作用，所以编译器应该可以自由地将整个东西丢弃。 - user4581301

我检查了发布版本和调试版本的构建。在Linux上，它们之间的差异几乎不存在，这可能暗示着它已被编译掉了。然而，如果所有内容都被编译掉了，那么什么都不做需要120毫秒似乎太长了。我报告了在Windows上手动启动应用程序时发布版本的运行时间，而不是从VS中启动。 - user6234011

这可能是由于Linux在内存分配后并不会立即使用该内存，而是在需要时才进行分配。如果你正在Windows上使用VS进行编译，这可能是由于释放内存回操作系统的策略不同造成的。（我猜测你在Windows上的物理内存不足。） - molbdnilo

@molbdnilo 不，100008并不重要，然而奇怪的运行时间只有在分配足够的内存时才会显示。对于更小的数字（可能取决于机器），我得到了一致的运行时间。我也不认为我用完了物理内存。我在Windows上有16GB（相比Linux的4GB），任务管理器在执行期间声称有超过1GB的可用内存。 - user6234011

Answer 1

挖掘有关Windows上引用计数的堆（以及一些关于信息安全的文章），其中有一些关于常见堆缓慢的小贴士，其中几个是

• 由于分配操作而导致的减速。
• 由于释放操作而导致的减速。
• 由于频繁的分配和重新分配而导致的减速。

这解释了为什么会出现减速（即频繁的分配和重新分配），但它并没有真正解释为什么会出现减速。

首先应该注意的是，sizeof(long) != sizeof(long)，也就是说，在我使用g++和Visual Studio 12进行64位构建的测试中，在Windows上，sizeof(long)是4，而在Linux上是8。这在分配/释放内存时是一个重要的注意点。如果您将代码从long类型更改为sizeof(T)==8的类型（如long long），则问题就会消失，并且时间在迭代之间保持一致。例如：

void iteration() {
    int n = 25000;
    // Allocate memory
    long long** blocks = new long long*[n];
    for (int i = 0; i < n; ++i) {
        blocks[i] = new long long[100008];
    }
    // Free all allocated memory
    for (int i = 0; i < n; ++i) {
        delete[] blocks[i];
    }
    delete[] blocks;
}
// sizeof(long long) == 8 on my Linux/Unix and Windows 64-bit machines

需要注意的是，时间问题只在这段代码中才会消失。

如果你保持long long类型，但将100008调整为16666，问题又会出现；此外，如果你将其改为16668，并立即运行long long迭代，然后紧接着运行long版本，时间会先增加，然后减少，例如：

template < typename T >
void iteration() {
    int n = 25000;
    // Allocate memory
    T** blocks = new T*[n];
    for (int i = 0; i < n; ++i) {
        blocks[i] = new T[16668];
    }
    // Free all allocated memory
    for (int i = 0; i < n; ++i) {
        delete[] blocks[i];
    }
    delete[] blocks;
}

for (int i = 0; i < nbItrs; ++i) {
    iteration<long long>(); // time goes UP
}
for (int i = 0; i < nbItrs; ++i) {
    iteration<long>(); // time goes DOWN
}

此外，使用 malloc/free、LocalAlloc/LocalFree 和/或 HeapAlloc/HeapFree 也会产生类似的结果，因为在 Windows 上，new/malloc 调用了 HeapAlloc。原因是 Windows 如何管理堆内存以及释放内存的位置有关。当需要删除页面时，需要对空闲块列表进行清理，并相应地调整列表。

这个调整可能需要时间，在搜索和替换或从列表中移除旧内存块时。如果块不落在干净的边界上，则可能需要对自由堆块列表进行其他调整。

深入了解Windows堆管理的如何和为什么将涉及到Windows内核和其内存管理的设计。 进一步讨论超出了这个问题/答案的范围，但是我链接的 某些 文章 中有很好的概述，并且非常清楚地解释了如何以及为什么。

然而，您确实问了：

如何使代码在Windows上稳定运行？

如上所述，更改类型将允许更一致的计时，此外，正如另一个 答案 中所述，按相反顺序删除列表也将实现更一致的计时；

for (int i = n; i > 0; --i )
{
    delete[] blocks[i-1];
}

由于Windows内存管理器使用单向链表来维护堆位置，所以在进行delete操作时时间会增加，因为需要遍历该列表，这也是为什么Windows比Linux慢的原因之一（尽管我的测试实际上在两者之间进行这些更改时产生了类似的时间）。

希望这可以帮到您。

- txtechhelp

---

感谢您的彻底研究。我会再等几天看看是否有其他答案出现，否则我将接受您的答案。 - user6234011

Answer 2

有趣的问题。我能够重现。

通过按照分配顺序的相反顺序delete[]块，我可以获得持续但仍然有些缓慢的性能：

for( int i = 0; i<n; ++i )
    delete[] blocks[n - 1 - i];

我怀疑这可能与合并开销有关-引用自MSDN：

由于释放操作导致的减速。释放操作消耗更多循环，特别是在启用合并的情况下。在合并期间，每个释放操作都应该“找到”它的邻居，将它们拉出来构建一个更大的块，并重新将更大的块插入到空闲列表中。在查找期间，内存可能以随机顺序被访问，导致缓存未命中和性能减慢。

但是还有一些奇怪的事情：

• 我的测量结果表明，在前三次迭代中，delete[]占用约80％的时间，但经过更多次迭代后，new[]占用的时间也几乎同样长。

• 当我从new long[91134]转移到...91135时，问题突然出现：这几乎是356kb，但我没有找到任何相关的信息。

- Tony Delroy

---

我可以确认，按相反的顺序释放内存可以提高运行时间：现在每次迭代大约需要1.3秒，多次迭代也没有明显的减速，但仍然比Linux慢得多。 - user6234011

Answer 3

非常有趣的问题。我无法在Windows 10上使用MS Visual Studio Community 2013重现它，但是如果您正在分配/释放大量具有固定大小的内存块，则可以尝试使用固定大小内存块分配算法（也称为内存池）替换new/delete。它的速度更快且速度恒定。在这里，您可以找到一个基于BSD许可证的示例：https://github.com/intelmm/FixMemAlloc/blob/master/Sources/MemoryPool.h。也许那能帮助到你。

- no one special