5

我刚开始从事一个速度非常重要的科学项目 (HPC)。我目前正在设计数据结构。该项目的核心是双值的 3D 网格,用于求解偏微分方程。

由于这里的速度可能比代码的简单性更受关注,我想知道与通常的 C 样式数组相比,STL 的性能如何。在我的例子中,因为它是一个 3D 网格,所以我在考虑 a) 具有线性索引的一维向量 b) 3 个向量的向量或 c) 一维 c 样式数组或 d) 三维 c 样式大批。

我查找了较旧的问题,但我只发现了有关构造/破坏的问题(这在这里并不重要,因为数据结构仅在程序启动时创建一次 - 快速索引和计算很重要)或不同 STL 容器的比较。

感谢帮助

4

4 回答 4

7

很难(甚至不可能)提前说相对表现会是什么。通常,在现代机器上,使用平面向量,并计算其中的索引,将优于向量的向量的向量;在较旧的机器上,情况正好相反。(在现代机器上,由于局部性差,乘法通常比页面丢失便宜。在旧机器上,乘法很昂贵,而且没有缓存,所以局部性没有影响。)

此外,根据机器和库的实现,std::vector对这个平面向量使用 an 可能比使用指向内存的简单指针更昂贵(或者它可能不是——你无法提前知道)。我仍然会先选择向量,将所有内容小心地包装在控制类中,如果仍然存在性能问题,请切换到指针。

于 2013-02-20T20:00:28.483 回答
3

1D 和 3D 阵列的内存布局将相同,并且类似于线性std::vector. 我会采用这种方法:一个一维向量和一个内联函数来映射到适当的位置。

另一方面,向量的向量具有完全不同的布局,因为向量中的数据不存储在对象内部,而是动态分配和引用。这意味着 a 中的两个不同行std::vector<std::vector<int>>可能位于内存中完全不相关的位置。

于 2013-02-20T19:49:24.020 回答
2

向量将在内部执行您需要手动执行的操作以处理单独大小的原始数组,因此只要正确使用它们,向量应该执行与执行相同任务的原始数组相同的操作。

例如,单个向量的性能应该与一维 c 数组相同,向量向量的性能应该与使用原始指针数组大致相同,其中每个元素都指向一个数组。

但是,如果 3d 数组具有统一的维度大小(即,不是参差不齐的数组),那么向量会支付额外的成本来单独管理它们的大小(例如,它们必须单独存储它们的大小)。如果在编译时已知任何维度大小,那么最好使用“STL”容器“std::array , because it won't have that unnecessary overhead. You can even have multi-dimentionalstd::arrays”:

template<typename T, int Planes, int Rows, Cols>
using Matrix = std::array<std::array<std::array<T,Cols>,Rows>,Planes>;

虽然没有严格要求,但这应该与 相同T arr[Planes][Rows][Cols];,但没有原始 c 数组的问题。

于 2013-02-20T19:50:24.370 回答
0

在 HPC 中广泛使用的动态分配静态(就分配后的不变维度而言)数组对象是平面数组和涂料向量的组合。基本上,这个想法是分配一大块平坦的内存,然后在其中构建一个指针树。对于二维数组,树只是指向每行开头的指针的简单线性列表。对于 3D 数组,树有两个级别,每个第二级元素都指向对应于第一级的 2D 切片中的一行。将涂料向量树放在分配内存的开头允许您直接应用[]索引运算符,例如A[i][j][k],但必须小心,因为它&A[i]不是i第 -th 2D 切片的开头。

这种方法的一个问题是涂料向量树的大小可能会变得非常大。例如,对于 64 位机器上的 1000x1000x1000 数组,此数据结构的大小为 1000x1000x8 字节或几乎 8 MiB。对于某些数据访问模式,这可能会占用宝贵的缓存空间。

于 2013-02-22T13:46:17.793 回答