std::pair<int, int> 与具有两个 int 的结构

Question

在 ACM 示例中，我必须为动态编程构建一个大表。我必须在每个单元格中存储两个整数，所以我决定使用 std::pair<int, int>. 。然而，分配一个巨大的数组需要 1.5 秒：

std::pair<int, int> table[1001][1001];

后来我把这段代码改成了

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

并且分配花费了0秒。

如何解释这种巨大的时间差异？

Answer 1

std :: pair＆lt; int，int＆gt; :: pair（）构造函数使用默认值初始化字段（在 int 的情况下为零）和 struct Cell 没有（因为你只有一个不做任何事情的自动生成的默认构造函数）。

初始化需要写入每个字段，这需要大量相对耗时的内存访问。使用 struct Cell ，不会做任何事情而且什么都不做会更快。

Answer 2

到目前为止，答案并没有解释问题的全部重要性。

正如sharptooth指出的那样，对解决方案将值初始化为零。正如Lemurik所指出的那样，对解决方案不仅仅是初始化一个连续的内存块，而是为表中的每个元素调用对构造函数。然而，即使这样也不会占用1.5秒。还有其他事情正在发生。

这是我的逻辑：

假设你是在一台古老的机器上，比如以1.33ghz运行，那么1.5秒是2e9个时钟周期。你有2e6对来构造，所以每对构造函数都需要1000个循环。 调用只将两个整数设置为零的构造函数不需要1000个周期。我无法看到缓存未命中会如何花费这么长时间。如果数字少于100个周期，我会相信它。

我认为看看所有这些CPU周期的其他地方会很有趣。我使用了我能找到的最古老的C ++编译器来查看是否可以达到所需的浪费水平。那个编译器是VC ++ v6。在调试模式下，它做了我不理解的事情。它有一个大循环，为表中的每个项调用对构造函数 - 足够公平。该构造函数将两个值设置为零 - 足够公平。但就在这之前，它将68字节区域中的所有字节设置为0xcc。那个区域就在大桌子开始之前。然后用0x28F61200覆盖该区域的最后一个元素。对构造函数的每次调用都会重复此操作。据推测，这是编译器的某种书籍保存，因此它知道在运行时检查指针错误时初始化了哪些区域。我很想知道这是为了什么。

无论如何，这可以解释额外时间的去向。显然，另一个编译器可能不是这么糟糕。当然，优化的发布版本也不会。

Answer 3

我的猜测是std :: pair的创建方式。调用一对构造函数1001x1001次时的开销比刚分配内存范围时要多。

Answer 4

这些都是非常好的猜测，但众所周知，猜测并不可靠。

我会说只是随机的 暂停一下 在那 1.5 秒内，但你必须非常快。如果将每个维度增加约 3 倍，则可以使其花费 10 秒以上的时间，因此更容易暂停。

或者，您可以在调试器下获取它，在配对构造函数代码中中断它，然后单步查看它在做什么。

无论哪种方式，您都会得到问题的确定答案，而不仅仅是猜测。

Answer 5

这是一个很好的例子，应该编写C ++并仔细使用STL。有什么想法吗？

我的项目正在开发一个C＆amp; C ++代码级基准测试工具，我们将在其中制作大量代码示例以找出“好”的内容。代码和什么是“坏”的编码习惯。请参阅 http://effodevel.googlecode.com 以了解有关C9B.M的更多信息。规划。如果您遇到过很多此类案件，请加入该项目以帮助我们。