我创建了一个小的性能测试,比较了三种流行的动态分配技术的设置和访问时间:原始指针、std::unique_ptr和std::deque。
编辑:根据@NathanOliver,添加std::vector
:EDIT 2:根据最新开发人员的,分配有std::vector(n)和std::deque(n)构造函数第3版:根据@BaummitAugen,将分配移动到计时循环中,并编译了一个优化版本。第4版:根据@PaulMcKenzie的评论,设置为2000。
结果:这些变化使事情变得更加紧张。Deque和Vector在分配和分配方面仍然较慢,而Deque在访问方面要慢得多:
pickledEgg$g++-std=c++11-o sp2-O2 sp2.cpp
Average of 2000 runs:
Method Assign Access
====== ====== ======
Raw: 0.0000085643 0.0000000724
Smart: 0.0000085281 0.0000000732
Deque: 0.0000205775 0.0000076908
Vector: 0.0000163492 0.0000000760
只是为了好玩,下面是-Oast结果:
pickledEgg$g++-std=c++11-o sp2-Ofast sp2.cpp
Average of 2000 runs:
Method Assign Access
====== ====== ======
Raw: 0.0000045316 0.0000000893
Smart: 0.0000038308 0.0000000730
Deque: 0.0000165620 0.0000076475
Vector: 0.0000063442 0.0000000699
原创:为子孙后代;注意缺少优化器-O2标志:
pickledEgg$g++-std=c++11-o sp2 sp2.cpp
Average of 100 runs:
Method Assign Access
====== ====== ======
Raw: 0.0000466522 0.0000468586
Smart: 0.0004391623 0.0004406758
Deque: 0.0003144142 0.0021758729
Vector: 0.0004715145 0.0003829193
更新代码:
#include <iostream>
#include <iomanip>
#include <vector>
#include <deque>
#include <chrono>
#include <memory>
const int NUM_RUNS(2000);
int main() {
std::chrono::high_resolution_clock::time_point b, e;
std::chrono::duration<double> t, raw_assign(0), raw_access(0), smart_assign(0), smart_access(0), deque_assign(0), deque_access(0), vector_assign(0), vector_access(0);
int k, tmp, n(32768);
std::cout << "Average of " << NUM_RUNS << " runs:" << std::endl;
std::cout << "Method " << 't' << "Assign" << "tt" << "Access" << std::endl;
std::cout << "====== " << 't' << "======" << "tt" << "======" << std::endl;
// Raw
for (k=0; k<NUM_RUNS; ++k) {
b = std::chrono::high_resolution_clock::now();
int* raw_p = new int[n]; // run-time allocation
for (int i=0; i<n; ++i) { //assign
raw_p[i] = i;
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
raw_assign+=t;
b = std::chrono::high_resolution_clock::now();
for (int i=0; i<n; ++i) { //access
tmp = raw_p[i];
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
raw_access+=t;
delete [] raw_p; // :^)
}
raw_assign /= NUM_RUNS;
raw_access /= NUM_RUNS;
std::cout << "Raw: " << 't' << std::setprecision(10) << std::fixed << raw_assign.count() << 't' << raw_access.count() << std::endl;
// Smart
for (k=0; k<NUM_RUNS; ++k) {
b = std::chrono::high_resolution_clock::now();
std::unique_ptr<int []> smart_p(new int[n]); // run-time allocation
for (int i=0; i<n; ++i) { //assign
smart_p[i] = i;
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
smart_assign+=t;
b = std::chrono::high_resolution_clock::now();
for (int i=0; i<n; ++i) { //access
tmp = smart_p[i];
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
smart_access+=t;
}
smart_assign /= NUM_RUNS;
smart_access /= NUM_RUNS;
std::cout << "Smart: " << 't' << std::setprecision(10) << std::fixed << smart_assign.count() << 't' << smart_access.count() << std::endl;
// Deque
for (k=0; k<NUM_RUNS; ++k) {
b = std::chrono::high_resolution_clock::now();
std::deque<int> myDeque(n);
for (int i=0; i<n; ++i) { //assign
myDeque[n] = i;
// myDeque.push_back(i);
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
deque_assign+=t;
b = std::chrono::high_resolution_clock::now();
for (int i=0; i<n; ++i) { //access
tmp = myDeque[n];
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
deque_access+=t;
}
deque_assign /= NUM_RUNS;
deque_access /= NUM_RUNS;
std::cout << "Deque: " << 't' << std::setprecision(10) << std::fixed << deque_assign.count() << 't' << deque_access.count() << std::endl;
// vector
for (k=0; k<NUM_RUNS; ++k) {
b = std::chrono::high_resolution_clock::now();
std::vector<int> myVector(n);
for (int i=0; i<n; ++i) { //assign
myVector[i] = i;
// .push_back(i);
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
vector_assign+=t;
b = std::chrono::high_resolution_clock::now();
for (int i=0; i<n; ++i) { //access
tmp = myVector[i];
// tmp = *(myVector.begin() + i);
}
e = std::chrono::high_resolution_clock::now();
t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b);
vector_access+=t;
}
vector_assign /= NUM_RUNS;
vector_access /= NUM_RUNS;
std::cout << "Vector:" << 't' << std::setprecision(10) << std::fixed << vector_assign.count() << 't' << vector_access.count() << std::endl;
std::cout << std::endl;
return 0;
}
从结果中可以看出,原始指针在这两个类别中都是明显的赢家。为什么会这样?
因为。。。
g++ -std=c++11 -o sp2 sp2.cpp
。。。您没有启用优化。调用为非基本类型(如std::vector
或std::unique_ptr
)重载的运算符涉及函数调用。使用基本类型的运算符(如原始指针)不涉及函数调用。
函数调用通常比没有函数调用慢。经过几次迭代,函数调用的小开销会成倍增加。然而,优化器可以内联扩展函数调用,从而消除非基本类型的缺点。但前提是执行了优化。
std::deque
还有一个较慢的原因:访问双端队列的任意元素的算法比访问数组更复杂。虽然std::deque
具有不错的随机接入性能,但它并没有阵列那么好。std::deque
的一个更合适的用例是线性迭代(使用迭代器)。
此外,您使用了std::deque::at
,它进行边界检查。下标运算符不进行边界检查。边界检查增加了运行时开销。
原始数组在std::vector
上的分配速度似乎有轻微的优势,这可能是因为std::vector
零初始化了数据。
std::deque
是一个双链表。myDeque.at(i)
必须在每次调用中遍历前i个元素。这就是为什么访问deque如此缓慢的原因。
std::vector
的初始化很慢,因为您没有预先分配足够的内存。std::vector
然后从少量元素开始,并且通常在尝试插入更多元素时将其加倍。这种重新分配涉及到为所有元素调用move构造函数。尝试构建这样的向量:
std::vector<int> myVector{n};
在矢量访问中,我想知道你为什么不使用tmp = myVector[i]
。您不调用索引运算符,而是实例化迭代器,调用其+运算符,并在结果上调用解引用运算符。由于您没有进行优化,函数调用可能不会内联,这就是为什么std::vector访问比原始指针慢的原因。
对于std::uniqe_ptr
,我认为它与std::vector
有类似的原因。您总是在唯一指针上调用索引运算符,这也是一个函数调用。作为一个实验,你能试着在为smart_p
分配内存后立即调用smart_p.get()
并使用原始指针进行其余操作吗。我想,它将和原始指针一样快。这可以证明我的假设,那就是函数调用。那么简单的建议是,启用优化并重试。
kmiklas编辑:
Average of 2000 runs:
Method Assign Access
====== ====== ======
Raw: 0.0000086415 0.0000000681
Smart: 0.0000081824 0.0000000670
Deque: 0.0000204542 0.0000076554
Vector: 0.0000164252 0.0000000678