为什么Windows中重复的内存分配会减慢？

Question

我想了解为什么以下代码在我的linux和Windows 7机器上表现不同:在linux上,每次迭代需要大约120ms.在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

Answer 1

深入 研究有关Windows 上堆的参考资料（以及一些有关它的信息安全文章），有一些关于常见堆速度减慢的花絮，其中指出了一些

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

这确实有助于解释为什么速度变慢（即频繁的分配和重新分配），但它并不能真正解释为什么速度变慢。

首先应该注意的是sizeof(long) != sizeof(long)，也就是说，在我使用g++Visual Studio 12 进行 64 位构建的测试中，sizeof(long)在 Windows 上为4，在 Linux 上为8。这是分配/释放内存时的一个重要注意事项。如果您将代码从类型更改long为 where 类型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为 say 16666，问题会再次出现；此外，如果您将其更改为并在版本之后立即16668运行迭代，则函数的计时将上升，而的计时将下降，例如：long longlonglong longlong

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，因为new/ malloc（在 Windows 上）调用HeapAlloc。原因与 Windows 如何管理其堆内存和已释放内存的位置有关。当必须删除页面时，需要清理空闲块列表，并且可能需要相应地调整列表。

在从列表中搜索和替换或删除旧内存块的过程中，这种调整可能需要一些时间。如果块没有落在干净的边界上，则可能需要对空闲堆块列表进行额外的调整。

深入了解 Windows 堆管理的方式和原因需要解释 Windows 内核的设计及其内存管理。进入这个问题将超出这个问题/答案的范围，但是，我上面链接的一些文章的概述，并很好地解释了如何和为什么。

然而，你确实问了

如何让代码在windows上稳定运行？

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

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

这是因为 Windows 内存管理器使用单链表来维护堆位置，因此为什么在delete遍历列表时时间会增加，以及为什么与 Linux 相比，Windows 上的时间会更慢（尽管我的测试实际上在进行这些更改时产生了相似的时间）。

我希望这能有所帮助。