std::pair<int, int>与具有两个int的结构体相比，有何优势？

Question

std::pair<int, int>与具有两个int的结构体相比，有何优势？

33

在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秒钟。

这个时间差别如此之大的原因是什么？

- Etan

3

我理解你的意思是ACM ICPC。 - Hosam Aly

3

你是否已经启用优化功能来测试这个？ - jalf

2

如果给Cell添加一个无参构造函数，性能会如何？ - outis

评测服务器启用了优化。（我想我听说过O3） - Etan

1

通过clang（900.0.39.2），使用-O0选项需要0.007秒，使用-O3选项需要2e-07秒。通过gcc（8.1），使用-O0选项需要0.005秒，使用-O3选项需要0秒。随着时间的推移，这个问题是否变得无效？ - Eli4ph

4个回答

29

到目前为止，先前的回答并没有完全解释这个问题的严重程度。正如Sharptooth指出的那样，pair解决方案将值初始化为零。正如Lemurik所指出的那样，pair解决方案不仅仅是初始化一个连续的内存块，而是为表中的每个元素调用pair构造函数。然而，即使这样也无法解释它需要1.5秒的时间。还有其他问题。

我的逻辑是这样的：假设您使用一台古老的机器，比如运行速度为1.33ghz，那么1.5秒就是2e9个时钟周期。你有2e6个要构造的pair，因此每个pair构造函数都要花费1000个周期。但是，调用只将两个整数设置为零的构造函数不需要1000个周期。我看不出缓存失效会导致它耗时那么长。如果数字小于100个周期，我可以相信它。

我认为看看这些CPU周期去了哪里很有趣。我使用了我能找到的最差的、最古老的C++编译器，看看是否可以达到所需的浪费级别。该编译器是VC++ v6。在调试模式下，它执行了我不理解的操作。它有一个大循环，为表中的每个项目调用一次pair构造函数——很公平。那个构造函数将两个值都设置为零——很公平。但就在那之前，它将68个字节区域中的所有字节设置为0xcc。该区域位于大表的开始之前。然后，它使用0x28F61200覆盖该区域的最后一个元素。每次调用pair构造函数都会重复这个过程。这可能是编译器的某种簿记，以便在运行时检查指针错误时知道哪些区域已初始化。我很想知道这到底是什么。

无论如何，这就解释了额外时间去哪里了。显然，其他编译器可能不会这么糟糕。当然，优化后的发布构建也不会这样。

- Andrew Bainbridge

6

这并不是VC++ V6本身的问题。在调试模式下，所有VC编译器都会将栈上分配的所有字节初始化为一个陷阱值（默认为0xCC），并且所有分配的堆内存也将被类似地初始化为0xCD。这样做有两个目的：使任何操作未初始化变量的代码出现大声失败，并让您在内存调试器中看到未初始化的栈。您看到的最后一个值是“栈金丝雀值”，用于检测栈溢出。 - Emily L.

3

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

我建议在1.5秒内随机暂停一下，但您需要非常快速。如果将每个维度增加约3倍，则可以使其需要10多秒钟，这样就更容易暂停了。

或者，您可以在调试器中对其进行调试，在配对构造函数代码中断点，然后单步执行以查看它在做什么。

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

- Mike Dunlavey

1

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

- Ashalynd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sharptooth · Accepted Answer

std::pair<int, int>::pair()构造函数会使用默认值来初始化字段（在int的情况下为零），而你的struct Cell则不会（因为你只有一个自动生成的默认构造函数，什么都不做）。

初始化需要对每个字段进行写入，这需要大量的内存访问，相对来说比较耗时。对于struct Cell，什么都不会发生，什么都不做会更快一些。