在C++中使用std::vector会有什么性能损失?

9

通常,我想了解标准模板库在数值/科学计算代码中是否会产生性能/速度开销。

例如,将一个数组声明为

double 2dmatrix [10][10]

升级将为我带来更好的性能。

std::vector<std::vector<double> > 2dmatrix(10,std::vector<double>(10,0.0))

我也希望您能提供一些普遍的想法,例如C语言在科学计算方面是否比C++更具有性能优势。我以非常面向对象的方式使用STL编写代码,并广泛使用C++11。我开始考虑是否应该开始研究纯C语言,以便获得更快的运行速度。

欢迎分享您的想法。


1
如果您提前知道边界,并且它们不会改变,那么是的,数组比std::vector更具性能。Vector是用于动态数组的容器。它使用调整大小策略,通过分配越来越大的块来增加向量的大小,从而牺牲内存以节省内存分配。 - crush
数组更好,但如果您不熟悉动态分配,则向量更容易实现随机数量的数据项。 - Chemistpp
3
向量的向量更像是动态分配的指针数组,每个指针指向动态分配的数组。数据不是连续的。这可能会产生后果,需要进行测量。此外,如果您的向量很小,存在小的大小开销可能很重要。真正的等价物应该是std::array<std::array<double,10>, 10> - juanchopanza
7
通常在类似愚蠢的“性能”问题中,正确的答案是不使用任何一种,而是使用专门的矩阵数据类型(“为什么”留给读者自己思考——提示:它将更好地处理您的数据;还会充分利用CPU)。请参阅 Eigen 或 Armadillo 或类似的库。 - Cat Plus Plus
需要注意的是,向量在随机访问时有一定的开销,因为它会检查边界以便于抛出异常。 - adrian.budau
显示剩余3条评论
7个回答

14

考虑到其提供的抽象性,C++ 的 std::vector 是效率最高的:在堆栈上有 3 个指针,并动态分配数据,在线性增长场景下,每个元素平均进行一次重新分配(因为重新调整大小扩展了容量,比例因子为 1.5 到 2)。

使用 malloc()realloc() 的 C 语言版本至少也同样昂贵,而且更加繁琐(手动调整大小等)。此外,std::vector 允许通过特殊的分配器(基于池、堆栈分配等)进行用户定义的性能调优,在 C++11 中使用起来不像在 C++98 中那么困难。

如果您不需要动态调整大小,则可以在 C 和 C++ 中编写静态数组(或者使用 C++ 中的 std::array)。

总的来说,对于高性能计算,C++ 具有更多的优化潜力,尤其是通过使用可内联的函数对象(与常规的 C 函数指针相反)进行优化。 典型的例子是排序

int comp( const void* a, const void* b ) {
    return /* your comparison here */;
}

// C style sorting
qsort( arr, LARGE_SIZE, sizeof( int ), comp ); 
                                       ^^^^ <---- no-inlining through function pointer

// C++11 style sorting (use hand-made function object for C++98
std::sort(std::begin(arr), std::end(arr), [](auto a, auto b) { 
    return comp(&a, &b);
           ^^^^ <----- C++11 lambdas can be fully inlined
});

3
关于C++11的东西要点赞。内联很重要,而且std::array厉害。 - SteveLove
公平地说,std::vector 留给实现足够的空间,以使用不太优化的解决方案。例如,如果 be 是随机访问迭代器,则 insert(end(), b,e) 不能保证执行最小数量的 resize/reserves(只有摊销是保证的)。 - Yakk - Adam Nevraumont
@Yakk 当然,那个老掉牙的自己踢自己的脚和炸掉自己的腿的故事。但是 std::vector 的 member range-insert 保证是高效的,而不仅仅是非成员的 std::insert 算法的摊销。 - TemplateRex

9

std::vector的开销包括:

  • 堆栈上的3个指针
  • 动态分配(懒惰地,即在需要时才分配)

在某些情况下,使用堆栈分配的数组可能更快(对于少量数据)。为此,您可以使用std::array<T, Length>

如果您需要一个二维网格,我建议将数据分配到单个向量中:std::vector<T>(width * height);。然后,您可以编写一些帮助函数通过x和y坐标获取元素。(或者您可以编写一个包装类。)


1
为什么一定要使用堆栈?vector<vector<int>>是最简单的反例。 - sasha.sochka
2
你为什么说“对于小量数据”?那么std::array的性能是否与“double 2dmatrix [10][10]”相当? 我实际上操作的是非常大的矩阵。 - atmaere
3
如果你有大量的数据,就不应该在栈上分配它,因为这可能会导致堆栈溢出。此外,随着 std::array 越来越大,其性能优势也会降低。 - StackedCrooked
1
@atmaere:std::array是一个非常薄的包装器,用于封装原始数组,因此在优化构建中性能应该是相同的。 - Mooing Duck
@MooingDuck 实际上,使用 -O1 或更高级别编译时生成的汇编代码是相同的。 - StackedCrooked
2
@StackedCrooked:这就是我说的:D - Mooing Duck

3

人们会说:“这取决于你在做什么。”

他们是正确的。

有一个例子在这里,其中一个使用标准库std::vector的传统设计程序通过六个阶段的性能调优,将其执行时间从每个单位工作的2700微秒减少到3.7微秒,加速比达到了730倍。

首先要做的是注意到大量时间都花费在了数组扩展和删除元素上。

所以使用了不同的数组类,大大减少了时间。

其次要注意到仍然有大量时间花费在数组相关的活动上。

所以完全消除了数组,改用链表,再次产生了大量加速。

然后其他活动也占用了剩余时间的很大一部分,例如创建和删除对象。

因此,这些对象被回收到空闲列表中,产生了另一个巨大的加速。

经过几个阶段后,决定停止尝试,因为越来越难找到改进的地方,而且速度提升已经足够。

关键是,不要仅仅选择高度推荐的东西,然后希望一切顺利。 相反,先构建它,然后像这样进行性能调优,并愿意根据你看到大部分时间花费在哪里来进行重大的数据结构设计更改。 并且要迭代它。 你可能会将存储方案从A更改为B,然后再从B更改为C。 这完全没问题。


3
这是多久之前的事情?因为你必须有一个非常具体的问题,才能让链表在使用不够优化的数组的情况下击败它,而我非常难以相信你可以用自己的空闲列表缓存击败malloc实现的空闲列表缓存。 - Puppy
@DeadMG:1)多久之前无关紧要。2)每个问题都是具体的。3)可以理解为难以相信。幸运的是,这并不重要,因为源代码(在所有迭代中)都在here。如果您尝试调整方法,并对一个适度大的程序进行优化,则可能会发现自己获得惊人的大幅加速,假设速度是目标,因为(IME)大多数规模较好的程序都有多个瓶颈,不同大小,总体上占用了几乎所有执行时间。 - Mike Dunlavey
1
@PeterCordes:你说得完全正确,一旦软件经过了我一直试图解释的一系列调整步骤,除了小玩具程序外,软件很容易因为作者从未想到的原因而变得极其低效。相反,他们立即开始担心他们学到的最新问题,比如指令流水线。例如:我向一些(非常好的)程序员展示了如何获得4个数量级的加速比。(他们不相信我。 :-) 一旦完成这个步骤,硬件层面的问题当然很重要。 - Mike Dunlavey
1
@PeterCordes:如果你好奇这个4个数量级的加速是从哪里来的,那么背景是生理代谢和药物化合物及其代谢产物的排泄模拟。这些都是以相当直接和通用的方式编写的,具有详细的胃、肠、肝脏和肾脏模型、皮肤模型、肺部模型等,所有这些都有微分方程。对于任何特定情况来说都过度了。我展示了如何生成特定问题的代码,即时编译并运行它。从几天到几秒的加速。 - Mike Dunlavey
1
哈哈,我之前从未听说过因为担心让自己过去的工作看起来不好而不进行优化(直到竞争压力出现)。 :P - Peter Cordes
显示剩余3条评论

3
如果您没有调整数组大小的必要,并且在编译时知道其大小(就像第一个示例中一样),则STL模板的更好选择是std::array模板。它为您提供了与C语言风格数组相同的所有优点。
double 2dmatrix[10][10];

// would become

std::array<std::array<double, 10>, 10> 2dmatrix;

3
如果您事先知道大小并且性能是瓶颈 - 请使用C++11的std::array。它的性能与C风格数组完全相同,因为内部看起来像:
template<typename T, int N>
struct array {
  T _data[N];
};

这是使用现代C++中栈分配数组的首选方式。 如果您有现代编译器,请不要使用C风格数组。

1
@JustinMeiners:std::array 是通过一个 T arr[N] 成员实现的。 - Xeo
请记住,只有在已知大小很小的情况下才适用,例如64kiB是合理的上限。在C++中,大小被强制为编译时常量,不像C99 VLAs或alloca,在这些语言中很容易意外地允许漏洞,如堆栈冲突(其中巨大的大小可以将堆栈指针跳转到其他内存区域,超过了保护页)。 - Peter Cordes

1
In scientific computing, bugs and sub-optimal code are especially frustrating because large amounts of data are incorrectly processed and precious time is wasted.
Depending on your knowledge of its inner workings, std::vector may be your bottleneck or your best performer. Pay special attention to reserve(), insert(), and erase(); consider learning about alignment and processor caching if your program is threaded.
If you try to do all the memory management by yourself, particularly when you are progressively adding features to your software, think about the time you will have to spend ensuring consistency and later hunting for bugs. At the end of the day, the overhead of std::vector will be the least of your problems.

0

对于科学计算,使用专用的 C++ 矩阵库(例如 Armadillo)会更好。这不仅可以让你快速处理数组,还有许多已经经过彻底调试的线性代数运算。

除了性能原因外,使用专用的 C++ 矩阵库还可以极大地减少代码的冗长,减少错误,从而加快开发速度。其中一个例子是,在 C++ 矩阵库中,您无需担心内存管理。

最后,如果您真的需要进入底层(即通过指针直接使用内存),C++ 允许您“降级”到 C 级别。在 Armadillo 中,这是通过 .memptr() 成员函数实现的。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接