C++数组与向量

Question

当使用C++向量时,花费的时间是718毫秒,而当我使用Array时,时间几乎是0毫秒.

为什么这么大的性能差异？

int _tmain(int argc, _TCHAR* argv[])
{
const int size = 10000; 
clock_t start, end; 
start = clock();
vector<int> v(size*size); 
for(int i = 0; i < size; i++)
{  
    for(int j = 0; j < size; j++)
    {   
        v[i*size+j] = 1;  
    } 
} 
end = clock();
cout<< (end - start)
    <<" milliseconds."<<endl; // 718 milliseconds

int f = 0;
start = clock(); 
int arr[size*size]; 
for(int i = 0; i < size; i++)
{  
    for(int j = 0; j < size; j++)
    {   
        arr[i*size+j] = 1;  
    } 
} 
end = clock();
cout<< ( end - start)
    <<" milliseconds."<<endl; // 0 milliseconds
return 0;
}

Answer 1

您的数组arr在堆栈上分配,即编译器在编译时计算了必要的空间.在该方法的开头,编译器将插入一个汇编语句

sub esp, 10000*10000*sizeof(int)

这意味着堆栈指针(esp)减少了10000 * 10000 * sizeof(int)字节,以便为10000 ^2个整数的数组腾出空间.这个操作几乎是即时的.

向量是堆分配的,堆分配要贵得多.当向量分配所需的内存时,它必须向操作系统询问连续的内存块,并且操作系统必须执行大量工作才能找到这块内存.

正如安德烈亚斯在评论中所说的那样,你所有的时间都花在这一行上:

vector<int> v(size*size); 

访问循环内的向量与数组一样快.

有关其他概述,请参阅例如

• [ 堆栈和堆的内容和位置是什么？

• [ http://computer.howstuffworks.com/c28.htm] [2 ]

• [ http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html] [3 ]

编辑:

在关于性能优化和编译器设置的所有评论之后,我今天早上做了一些测量.我必须设置size=3000所以我用大约十分之一的原始条目进行测量.在2.66 GHz Xeon上执行的所有测量:

1. 使用Visual Studio 2008中的调试设置(无优化,运行时检查和调试运行时),矢量测试花费了920 ms,而阵列测试则为0 ms.

   占用总时间的98,48%vector::operator[],即确实花费在运行时检查上的时间.

2. 通过完全优化,矢量测试需要56 ms(具有原始条目数的十分之一),而阵列的测试时间为0 ms.

   vector ctor需要61.72%的总应用程序运行时间.

所以我想根据所使用的编译器设置,每个人都是正确的.OP的时序表明优化的构建或STL没有运行时检查.

与往常一样,士气是:配置文件优先,优化第二.

Answer 2

如果您使用Microsoft编译器进行编译,为了使其公平比较,您需要通过定义_SECURE_SCL = 0和_HAS_ITERATOR_DEBUGGING = 0来关闭迭代器安全检查和迭代器调试.

其次,您使用的构造函数将每个向量值初始化为零,并且在填充之前您不会将数组memset为零.所以你要遍历矢量两次.

尝试:

vector<int> v; 
v.reserve(size*size);