C++ 向量与数组(时间) [英] C++ Vector vs Array (Time)

问题描述

我有两个程序，它们都在做完全相同的任务.他们只是将布尔数组/向量设置为 true 值.使用向量的程序运行需要 27 秒，而涉及大小为 5 倍的数组的程序需要不到 1 秒.我想知道为什么会有如此大的差异的确切原因?是向量真的那么低效吗?

I have got here two programs with me, both are doing exactly the same task. They are just setting an boolean array / vector to the value true. The program using vector takes 27 seconds to run whereas the program involving array with 5 times greater size takes less than 1 s. I would like to know the exact reason as to why there is such a major difference ? Are vectors really that inefficient ?

使用向量编程

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main(){
 const int size = 2000;
 time_t start, end;
 time(&start);
 vector<bool> v(size);
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

运行时间 - 27 秒

Runtime - 27 seconds

使用数组编程

#include <iostream>
#include <ctime>

using namespace std;

int main(){
 const int size = 10000; // 5 times more size
 time_t start, end;
 time(&start);
 bool v[size];
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

运行时 - <1秒

Runtime - < 1 seconds

平台 - Visual Studio 2008操作系统 - Windows Vista 32 位 SP 1处理器 Intel(R) Pentium(R) 双 CPU T2370 @ 1.73GHz内存 (RAM) 1.00 GB

Platform - Visual Studio 2008 OS - Windows Vista 32 bit SP 1 Processor Intel(R) Pentium(R) Dual CPU T2370 @ 1.73GHz Memory (RAM) 1.00 GB

谢谢

阿玛尔

推荐答案

您使用的是 std::vector of bool 而不是您认为的那样！

bool 的向量是一个混蛋子模板特化，它不应该存在并且实际上在每个位中存储 1 个 bool.由于屏蔽和移位逻辑，访问更复杂，因此肯定会慢一些.

vector of bool is a bastard child template specialization that should never have existed and actually stores 1 bool in each bit. Accesses into it are more complicated due to masking and shifting logic, so will definitely be somewhat slower.

单击此处了解有关 bool 向量的一些信息.

此外，您可能正在运行未优化的构建(几乎可以肯定，考虑到您列出的时间，27 秒对于 400 万次迭代来说是离谱的).标准模板库非常依赖优化器来执行内联函数调用和 elide 临时文件等操作.缺少这种优化会导致 bool 向量的性能下降特别严重，因为它在索引时必须返回一个代理对象，因为不能取位的地址，所以 operator [] 不能返回引用.

Also, you may be running an unoptimized build (almost certainly given the times you listed, 27 seconds is outrageous for 4 million iterations). The Standard Template Library relies very heavily on the optimizer to do things like inline function calls and elide temporaries. Lack of this optimization causes an especially heavy performance degradation for vector of bool because it has to return a proxy object when you index into it, because you can't take the address of a bit, so operator [] can't return a reference.

单击此处了解有关代理容器的更多信息(后半部分是关于布尔)

Click here for more info on proxied containers (The last half is about vector of bool)

此外，许多 STL 实现具有有用的调试位，这些位不是标准的一部分，可帮助您捕获错误，但确实会降低性能.您需要确保在优化构建中禁用这些功能.

In addition many STL implementations have helpful debugging bits that are not part of the standard which help you catch bugs, but really drag performance down. You'll want to make sure those are disabled in your optimized build.

一旦您打开优化器，进行正确的设置(即没有打开 STL 调试)，并且实际上在两个循环中测试相同的东西，您几乎看不到任何区别.

Once you turn on the optimizer, have the right settings (i.e. no STL debugging turned on), and are actually testing the same thing in both loops, you will see almost no difference.

为了在我的机器上进行测试，我不得不让你的循环变得更大，但这里有你的 bool 循环向量在我的机器上的两个构建，显示了优化器标志对 STL 代码的影响

I had to make your loop much larger to test on my machine, but here's two builds of your vector of bool loop on my machine, showing the impact of optimizer flags on STL code

$ g++ main.cpp 
$ ./a.out 
17 seconds.
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds.

这篇关于C++ 向量与数组(时间)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！