std::pair;与具有两个 int 的结构对比
在 ACM 示例中，我必须为动态编程构建一个大表。我必须在每个单元格中存储两个整数，因此我决定使用 std::pair。然而，分配一个巨大的数组花了 1.5 秒：
std::pair<int, int> table[1001][1001];
后来，我把这段代码改为
struct Cell {
int first;
int second;
}
Cell table[1001][1001];
，分配花了 0 秒。
如何解释这种巨大的时间差异？
In an ACM example, I had to build a big table for dynamic programming. I had to store two integers in each cell, so I decided to go for a std::pair<int, int>. However, allocating a huge array of them took 1.5 seconds:
std::pair<int, int> table[1001][1001];
Afterwards, I have changed this code to
struct Cell {
int first;
int second;
}
Cell table[1001][1001];
and the allocation took 0 seconds.
What explains this huge difference in time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
std::pair::pair() 构造函数使用默认值（int的情况下为零）初始化字段和您的struct Cell< /code> 没有（因为你只有一个自动生成的默认构造函数，不执行任何操作）。初始化需要写入每个字段，这需要大量的内存访问，相对耗时。使用
struct Cell什么都不做，而且什么都不做会更快一些。std::pair<int, int>::pair()constructor initializes the fields with default values (zero in case ofint) and yourstruct Celldoesn't (since you only have an auto-generated default constructor that does nothing).Initializing requires writing to each field which requires a whole lot of memory accesses that are relatively time consuming. With
struct Cellnothing is done instead and doing nothing is a bit faster.到目前为止的答案并不能解释问题的全部严重性。
正如 Sharptooth 所指出的，配对解决方案将值初始化为零。正如 Lemurik 指出的，对解决方案不仅仅是初始化连续的内存块，而是为表中的每个元素调用对构造函数。然而，即使这样也没有考虑到花费 1.5 秒的时间。还有其他事情正在发生。
我的逻辑是这样的：
假设你在一台古老的机器上，比如说以 1.33ghz 运行，那么 1.5 秒就是 2e9 个时钟周期。您需要构造 2e6 对，因此每对构造函数都需要 1000 个周期。 调用一个仅将两个整数设置为零的构造函数不需要 1000 个周期。我看不出缓存未命中如何让它花费那么长时间。如果这个数字少于100个周期我会相信。
我认为看看所有这些 CPU 周期都去了哪里会很有趣。我使用了我能找到的最蹩脚、最古老的 C++ 编译器，看看我是否能达到所需的浪费水平。该编译器是 VC++ v6。在调试模式下，它做了一些我不明白的事情。它有一个大循环，为表中的每个项目调用对构造函数 - 足够公平。该构造函数将这两个值设置为零——这很公平。但就在执行此操作之前，它将 68 字节区域中的所有字节设置为 0xcc。该区域就在大牌桌开始之前。然后它用 0x28F61200 覆盖该区域的最后一个元素。对构造函数的每次调用都会重复此操作。据推测，这是编译器进行的某种簿记，因此它知道在运行时检查指针错误时初始化了哪些区域。我很想知道这究竟是做什么用的。
无论如何，这可以解释额外的时间都花在哪里了。显然另一个编译器可能不会这么糟糕。当然，优化的发布版本不会。
The answers so far don't explain the full magnitude of the problem.
As sharptooth has pointed out, the pair solution initializes the values to zero. As Lemurik pointed out, the pair solution isn't just initializing a contiguous block of memory, instead it is calling the pair constructor for every element in the table. However, even that doesn't account for it taking 1.5 seconds. Something else is happening.
Here's my logic:
Assuming you were on an ancient machine, say running at 1.33ghz, then 1.5 seconds is 2e9 clock cycles. You've got 2e6 pairs to construct, so somehow each pair constructor is taking 1000 cycles. It doesn't take 1000 cycles to call a constructor that just sets two integers to zero. I can't see how cache misses would make it take that long. I would believe it if the number was less than 100 cycles.
I thought it would be interesting to see where else all these CPU cycles are going. I used the crappiest oldest C++ compiler I could find to see if I could attain the level of wastage required. That compiler was VC++ v6. In debug mode, it does something I don't understand. It has a big loop that calls the pair constructor for each item in the table - fair enough. That constructor sets the two values to zero - fair enough. But just before doing that, it sets all the bytes in a 68 byte region to 0xcc. That region is just before the start of the the big table. It then overwrites the last element of that region with 0x28F61200. Every call of the pair constructor repeats this. Presumably this is some kind of book keeping by the compiler so it knows which regions are initialized when checking for pointer errors at run time. I'd love to know exactly what this is for.
Anyway, that would explain where the extra time is going. Obviously another compiler may not be this bad. And certainly an optimized release build wouldn't be.
这些都是非常好的猜测，但众所周知，猜测并不可靠。
我想说只是随机暂停它< /a> 在那 1.5 秒内，但你必须非常快。如果将每个维度增加约 3 倍，则可以使其花费 10 秒以上的时间，因此更容易暂停。
或者，您可以在调试器下获取它，在配对构造函数代码中中断它，然后单步查看它在做什么。
无论哪种方式，您都会得到问题的确定答案，而不仅仅是猜测。
These are all very good guesses, but as everyone knows, guesses are not reliable.
I would say just randomly pause it within that 1.5 seconds, but you'd have to be pretty quick. If you increased each dimension by a factor of about 3, you could make it take more like 10+ seconds, so it would be easier to pause.
Or, you could get it under a debugger, break it in the pair constructor code, and then single step to see what it is doing.
Either way, you would get a firm answer to the question, not just a guess.
我猜这是 std::pair 的创建方式。与仅分配内存范围相比，调用对构造函数 1001x1001 次时的开销更多。
My guess it's the way std::pair is created. There is more overhead during invoking a pair constructor 1001x1001 times than when you just allocate a memory range.