C++ 数组与 vector

Question

当使用 C++ vector 时，花费的时间是 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< 的数组腾出空间/sup> 整数。这个操作几乎是即时的。}

vector 是堆分配的，堆分配的开销要大得多。当 vector 分配所需的内存时，它必须向操作系统请求一 block 连续的内存，而操作系统将不得不执行大量工作来找到这 block 内存。

正如 Andreas 在评论中所说，你所有的时间都花在了这一行上:

vector<int> v(size*size); 

访问循环内的 vector 与访问数组一样快。

有关其他概述，请参见例如

• [ What and where are the stack and heap?

• [ 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 中的调试设置(无优化、运行时检查和调试运行时)， vector 测试耗时 920 毫秒，而数组测试耗时 0 毫秒。

   总时间的 98.48% 花在了 vector::operator[] 上，也就是说，时间确实花在了运行时检查上。

2. 在完全优化的情况下， vector 测试需要 56 毫秒(原始条目数的十分之一)，而数组需要 0 毫秒。

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

所以我猜每个人都是对的，这取决于所使用的编译器设置。 OP 的计时建议优化构建或没有运行时检查的 STL。

一如既往，士气是:配置文件第一，优化第二。