为什么C++中的多维数组的这些计算速度不同？

Question

这可能是一个重复的问题.所以,如果你愿意,请随时将其标记下来.在C++中,我了解到数组维度连续存储在内存中如何将3D数组存储在C中？所以我做了一个小实验,将自然数分配给大小为1600000000x1和1x1600000000的矩阵(请matsize根据您的记忆将代码更改为较小的值).下面的代码为矩阵a(其尺寸为1x1600000000)分配1到1600000000的自然数,并计算所有元素的立方体总和.相反的情况只是通过更改xdim为matsize和ydim1 来反转矩阵的维度,并重新编译代码并再次运行它.矩阵是[xdim][ydim]

#include <iostream>
#include <time.h>
using namespace std;
int main()
{
long int matsize, i, j, xdim, ydim;
long double ss;
double** a;
double time1, time2, time3;
clock_t starttime = clock();    
matsize=1600000000;
xdim=1;
ydim=matsize;   
ss=0.0;    
a= new double *[xdim];
for(i=0;i<xdim;i++)
{
    a[i]= new double[ydim];
}

time1= (double)( clock() - starttime ) / (double)CLOCKS_PER_SEC;    
cout << "allocated. time taken for allocation was " << time1 <<" seconds. computation started" << endl;    
for(i=0;i<xdim;i++)
{
    for(j=0;j<ydim;j++)
    {
        a[i][j]=(i+1)*(j+1);
        ss=ss+a[i][j]*a[i][j]*a[i][j];
    }
}
cout << "last number is " << a[xdim-1][ydim-1] << " . sum is " << ss << endl;
time2= ((double)( clock() - starttime ) / (double)CLOCKS_PER_SEC) - time1;
cout << "computation done. time taken for computation was " << time2 << " seconds" << endl;    
for(i=0;i<xdim;i++)
{
    delete [] a[i];
}
delete [] a;   
time3= ((double)( clock() - starttime ) / (double)CLOCKS_PER_SEC) - time2;
cout << "deallocated. time taken for deallocation was " << time3 << " seconds" << endl;    
cout << "the total time taken is " << (double)( clock() - starttime ) / (double)CLOCKS_PER_SEC << endl;
cout << "or " << time1+time2+time3 << " seconds" << endl; 
return 0;
}

我对两个案件的结果是 -

情况1:xdim = 1和ydim = 1600000000

分配.分配时间为4.5e-05秒.计算开始的最后一个数字是1.6e + 09.总和是1.6384e + 36计算完成.计算所用的时间是14.7475秒已取消分配.取消分配所需时间为0.875754秒,所用时间为15.6233或15.6233秒

情况2:xdim = 1600000000和ydim = 1

分配.分配时间为56.1583秒.计算开始的最后一个数字是1.6e + 09.总和是1.6384e + 36计算完成.计算所用的时间是50.7347秒已取消分配.解除分配所需的时间为270.038秒,所用时间为320.773或376.931秒

两种情况下的输出总和相同.我可以理解,在两种情况下分配和释放内存所花费的时间都不同,但是如果内存分配是连续的,为什么计算时间也会有很大不同呢？这段代码有什么问题？

如果重要的话,我在Mountain Lion上使用g ++并使用g ++ -std = c ++ 11,i7四核处理器,16 GB RAM进行编译

Answer 1

每个单独的向量连续存储内容,包括指向向量的指针向量,但是您对new进行的连续调用的地址不是连续的,也没有调用向量在内部创建其缓冲区.因此,如果你有一个指向微小向量的巨大指针向量,你的内存实际上是非连续的,你将无法获得良好的缓存命中率.如果你有一个单元素向量到一个巨大的向量,那么内存是连续的,缓存将很好地工作.

在视觉上,快速/连续的布局是:

*a--[0]
.    |
.   [0][1][2][3][4][5][...]

你的慢选择是:

.        [0]     [0]
.         \       /
*a--[0][1][2][3][4][5][...]
.    |   \    |     \
.   [0]   \[0][0]   [0]

可以使用例如在堆栈上创建多维数组

int x[10][20];

在这种情况下,存储器将是连续的,其中每个x [0],x [1]等中的存储器是连续的.(所以x [0] [0]在x [0] [1]之前,而不是在x [1] [0]之前.)

要在堆上有效地拥有连续的多维数组,您应该使用预期维度的乘积新建一个向量,然后编写一个包装类,它可以方便地将维度乘以查找特定元素.