c++ - std::set fast and slow，这是怎么回事？

Question

我遇到了 std::set 的一个奇怪行为。

代码如下:

#include <cstdio>
#include <windows.h>
#include <stdlib.h>

#include <vector>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
    set<int> b[100];

    for (int o=0; o<10; o++)
    {
        int tt = GetTickCount();

        for (int i=0; i<5000000; i++)
        {
            b[o].insert(i);
        }

        tt = GetTickCount() - tt;

        b[o].clear();

        printf("%d\n", tt);
    }

    return 0;
}

我在 Windows XP 上运行。

这是有趣的部分:第一次打印时间约为 3500 毫秒，而接下来的打印时间都超过 9000 毫秒!为什么会这样？

哦，这只发生在发布版本上(-O2 优化)。

它不会发生在 Linux 上(在更改代码以在那里编译之后)。

还有一件事:当我在使用 Intel VTune 进行分析时运行它时，它总是需要大约 3000 毫秒，所以它应该是这样的。

更新:这是一些新代码:

#include <cstdio>
#include <windows.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
const int count = 10000000;
int **a = new int*[count];

for (int o=0; o<10; o++)
{
    int ttt = GetTickCount();

    for (int i=0; i<count; i++)
    {
        a[i] = new int;

        *a[i] = i;
    }

    int ttt2 = GetTickCount();

    for (int i=0; i<count; i++)
    {
        int r1 = rand() * 10000 + rand();
        int r2 = rand() * 10000 + rand();
        r1 = r1%count;
        r2 = r2%count;

        int *e = a[r1];
        a[r1] = a[r2];
        a[r2] = e;
    }

    int ttt3 = GetTickCount();

    for (int i=0; i<count; i++)
    {
        delete a[i];
    }

    int ttt4 = GetTickCount();

    printf("%d %d\n", ttt2-ttt, ttt4-ttt3);
}

return 0;
}

这是同样的问题。发生的事情是我分配了许多小对象，然后以随机顺序删除它们——所以它类似于它在 std::set 中的样子。所以这是 Windows 内存管理问题。它不能很好地处理许多小的分配和删除。

Answer 1

我无法准确解释为什么会这样，但我可以提出一个解决方案。当我在调试器下运行发布版本时(使用 F5)，我已经能够在我的 PC 上重现这个。当我从命令行或使用 Ctrl-F5 运行构建时，我没有得到那种行为。

这与在调试器下启动时默认打开的调试堆有关。描述的很详细here .为了防止这种情况发生

1. 从命令行或使用 Ctrl-F5(调试 -> 不调试开始)运行。
2. 转到项目 -> 属性 -> 调试 -> 环境并添加 _NO_DEBUG_HEAP=1。

如果非要我猜的话，我会说它与 Windows/VS 运行时中内存分配跟踪的实现有关。可能一些内部列表已填满并重新分配或按照这些思路进行其他操作。