std :: pair <int, int> vs两个int的结构

在一个ACM示例中，我必须为动态编程构建一个大表。我必须在每个单元中存储两个整数，所以我决定去找std::pair<int, int>。然而，分配一个巨大的人阵了1.5秒：std :: pair <int, int> vs两个int的结构

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

之后，我改变了这个代码

struct Cell { 
    int first; 
    int second; 
} 

Cell table[1001][1001];

，并分配了0秒。

什么解释了这种巨大的时间差异？

来源

2009-10-22 Etan

我相信你的意思是ACM ** ICPC **。 – 2009-10-22 12:52:44

您是否已启用优化来测试此功能？ – jalf 2009-10-24 08:45:03

如果向'Cell'添加无参数构造函数，性能如何？ – outis 2009-10-24 08:46:22

std::pair<int, int>::pair()构造函数初始化与域的默认值（零中的int情况下），你的struct Cell没有（因为你只能有一个自动生成的默认构造函数，什么也不做）。

初始化需要写入每个字段，这需要大量相对耗时的内存访问。用struct Cell什么都不做，反而更快一点。

来源

2009-10-22 12:35:16 sharptooth

是否需要1.5秒将大约8 MB设置为零？ – Etan 2009-10-22 12:37:40

不要忘记缓存未命中。 – sharptooth 2009-10-22 12:38:39

不，问题是对构造函数的函数调用。如果你的数组是全局的，无论如何它都被初始化为零。编译器可能不会优化构造函数调用。 – 2009-10-22 12:38:48

我的猜测是std :: pair被创建的方式。在调用一个构造函数1001x1001次的时候，比刚刚分配一个内存范围的时候有更多的开销。

来源

2009-10-22 12:45:08 Ashalynd

-1

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

我的项目正在研究一个C++代码级基准测试工具，我们将在其中编写大量代码样本以找出什么是“好”代码，什么是“坏”编码习惯。请参阅http://effodevel.googlecode.com了解更多关于C9B.M.规划。如果你遇到过很多这样的情况，请加入该项目来帮助我们。

来源

2009-10-22 12:47:27 Test

这不是问题的答案 – 2009-10-22 17:44:09

有什么想法吗？是的，你的项目似乎纳入了一个普遍的想法，即优化是关于低级优化*（和大O）的。我认为这个问题比这个问题要大得多，也就是*驰骋的一般性*，你可能会考虑更广泛的范围。 http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773 – 2009-10-24 15:20:31

没有计划做一个更大的目前。 su。一步一步地进步如代码级别，算法级别和体系结构级别等。我们现在正在理解语言和编译器。感谢您的评论 – Test 2009-10-25 05:30:07

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

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

这里是我的逻辑：

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

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

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

来源

2009-10-23 23:49:09

这不是VC++ V6的错。在调试模式下，所有VC编译器都会将堆栈上分配的所有字节初始化为一个陷阱值（默认为0xCC），并将所有分配的堆内存初始化为0xCD。目的有两点：因为任何对未初始化的变量进行操作的代码会大声失败，并让您在内存调试器中看到未初始化的堆栈。您看到的最后一个值是用于检测堆栈溢出（“.com *咯咯”*）的“堆栈金字塔值”。 – 2014-03-31 15:25:41

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

我会说在1.5秒内随机pause it，但你必须非常快。如果将每个维度增加了大约3倍，则可能需要10秒钟以上，因此暂停会更容易。或者，您可以在调试器下获取它，在对构造函数代码中分解它，然后单步查看它在做什么。

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

来源

2009-10-24 15:07:34

std :: pair <int, int> vs两个int的结构

回答

相关问题