std :: pair <int,int> vs struct with two int's

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<int, int>::pair()构造函数使用默认值初始化字段(如果是,则为零int),而struct Cell不是(因为您只有一个自动生成的默认构造函数,不执行任何操作).

初始化需要写入每个字段,这需要大量相对耗时的存储器访问.有了struct Cell什么都不做,而不是和什么都不做是有点快.

Answer 2

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

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

这是我的逻辑:

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

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

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