4

在写一篇关于欧拉项目第 14 个问题的帖子时，我遇到了 VC9 和 VC10 之间的行为差​​异。

以下代码在 VC9 中运行正常，但在 VC10 中std::unordered_map抛出bad_alloc异常。奇怪的是，如果我从异常中恢复，未来的分配将成功（容器的大小继续增长）。此外，如果我使用boost::unordered_map它在两个编译器中都可以正常工作。

关于实际内存使用情况，我在一台 4GB RAM 的机器上运行，（正在使用 1.7）VC9 版本在完成任务之前获得了约 810MB 的内存，而 VC10 则在约 658MB 时崩溃。

这是VC10中的错误吗？我在同一台机器上运行，当完成的工作量相同时，还有什么可能导致内存在一个版本中持续耗尽，而不是在另一个版本中？

<edit>
更多信息：第一次发生异常是在计算堆栈深度为 1 的 7,718,688 时（没有递归只是 main->length）。之后，添加到缓存中的每个数字似乎都会发生这种情况。在异常发生之前，缓存中有 16,777,217 个元素（根据cache.size()）。有趣的是，即使insert失败，缓存大小也会增加 1，因此它似乎不提供强异常保证（违反 §23.2.1.11）。
</编辑>

代码如下：

#include <iostream>
#include <unordered_map>

typedef std::unordered_map<_int64, int> cache_type;

_int64 collatz(_int64 i)
{
    return (i&1)? i*3+1 : i/2;
}

int length(_int64 n, cache_type& cache)
{
    if (n == 1)
        return 1;

    cache_type::iterator found = cache.find(n);
    if (found != cache.end())
        return found->second;
    int len = length(collatz(n), cache) + 1; 
    cache.insert(std::make_pair(n, len)); // this sometimes throws
    return len;
}

int main(int argc, char** argv)
{
    const int limit = 10000000;
    cache_type cache;
    std::pair<int, int> max = std::make_pair(0, 0);
    for (int i = 2; i <= limit; ++i) {
        int len = length(i, cache);
        if (len > max.second)
            max = std::make_pair(i, len);
    }

    std::cout<< "Number with longest orbit is " << max.first 
        << " with a lenght of " << max.second 
        << " cache size is " << cache.size() << std::endl;
}

<edit>
任何人都可以重现这种行为，有一次它消失了（然后又重新出现了），所以我的配置可能有一些特别之处。
</编辑>

4

5 回答 5

2

这可能是偶然的，但更改 _SECURE_SCL 的值会导致您描述的行为。

即编译：

cl /EHa /MD /D_SECURE_SCL=1 /Ox /c t1.cpp
link /LIBPATH:"c:/Program Files/Microsoft Visual Studio 10.0/VC/lib" /LIBPATH:"C:/Program Files/Microsoft SDKs/Windows/v7.0A/Lib" t1.obj

崩溃，但 _SECURE_SCL=0 的相同命令在我的 XP 32 位机器上运行完成。_SECURE_SCL的msdn页面说它已启用调试构建，但不是发布，如果您在 IDE 下构建，这可能很重要。

于 2010-07-16T08:25:06.897 回答
1

如果需要调整映射的哈希表大小，则插入单个元素可能会导致大量内存分配。地图在运行结束时似乎约为 0.5GB。（见我上面的评论。）

大概有一些启发式方法被用来决定在哈希表需要增长时扩展多少，并且可以想象每次都将它加倍。因此，在复制哈希表时，这将使用 ~1.5GB 的旧数据和新数据。

因此，您的程序可能会达到进程内存大小的限制。（再次参见评论。）如果是这样，可能 VC10 总体上比 VC9 占用更多的内存，并且在程序的不同运行或构建中分配的内存量略有不同，因此 VC10 有时会达到限制而 VC9 没有从来没有打过它。

于 2010-07-11T05:35:10.237 回答
0

_int64 是否有地图在分配时可能不遵守的对齐要求？

尝试改用 long long int 并查看行为是否发生变化。

于 2010-07-07T14:54:02.200 回答
0

您在对length().

于 2010-07-07T15:59:31.740 回答
0

1 - 检查 EventLog 以查看是否有任何事件谈论进程超出其允许的配额。

2 - 如果您使用的是 32 位操作系统，请尝试以 3GB 的用户空间启动它。

3 - 查看是否有不同的分配器可用

4 - 在 9.0 和 10.0 中区分 unordered_map 并且它是内联文件，如果添加了人为的大小限制器（“安全功能”:-)。它很可能位于具有不同 x86 和 x64 构建值的宏中。

5 - 尝试在分配器周围放置一个轻型包装器，并为每个分配打印大小。这也会告诉你它是否真的是分配器，或者它之前的东西。

6 - 如果是分配器，请查看由它发出的实际 WinNT API 调用（并再次与 9.0 进行比较）

7 - 尝试预先分配大块（比如 1 GB）。

于 2010-07-14T11:55:42.110 回答