STL容器速度与数组比较

Question

我刚开始参与一个科学项目，速度非常重要（HPC）。目前我正在设计数据结构。该项目的核心是一个双精度值的3D网格，用于解决偏微分方程。

由于速度在这里比代码的简洁性更重要，所以我想知道STL和通常的C风格数组相比表现如何。在我的情况下，由于它是一个三维网格，我考虑了a）具有线性索引的一维向量b）三个向量的向量或c）一维C风格数组或d）三维C风格数组。

我查找了旧问题，但我只发现关于构建/销毁的问题（这对于此处不重要，因为数据结构仅在程序启动时创建一次 - 快速索引和计算很重要），或者关于不同STL容器的比较。

感谢您的帮助

- Chris

---

你应该看一下boost::multi_array - 在这种情况下，它很可能在性能和设计方面都非常出色。 - Joseph Mansfield

如果您想要处理偏微分方程，请查看Numerical Recipes，http://www.nr.com/，它已经更新为C++。 - QuentinUK

一个向量的向量可能是最糟糕的选择(你会得到碎片化的内存)。你可能想要的是基本上这个扩展到3维。在实际使用中，这通常与数组的速度相同。 - Jerry Coffin

HPC通常与MPI一起使用，而MPI不喜欢遵循指针，因此您最有可能需要为数组使用平坦内存布局。这排除了像vector<vector<...>>这样的结构。 - Hristo Iliev

Answer 1

事先很难（甚至不可能）预测相对性能。一般来说，在现代计算机上，使用一个平面向量，并计算其索引，将优于使用一个向量的向量；在旧计算机上，情况正好相反。（在现代计算机上，由于缺乏局部性而导致的页面错误通常比乘法更便宜。在旧计算机上，乘法是昂贵的，并且没有缓存，因此局部性不会产生影响。）

此外，根据机器和库实现的不同，对于这种平面向量，使用std::vector可能比使用指向内存的简单指针更昂贵（或者可能不是-你不能事先知道）。我仍然会首选vector，仔细包装所有内容在一个控制类中，如果仍有性能问题，则切换到指针。

- James Kanze

Answer 2

1D和3D数组的内存布局将相同，并且与线性std::vector的内存布局类似。我的建议是采用一个一维向量并使用内联函数映射到适当的位置。

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

- David Rodríguez - dribeas

---

值得一提的是，对于您的三个维度（行、列、'sheet'），内部维度将被存储为一个向量，并且将具有同样良好的访问时间，这可能是可以接受的。对于此向量的访问将非常好，但对于其他向量，您将在1D结构上遇到性能问题。您还需要使用std::vector<std::vector<std::vector<T>>>来获取您的三个维度。 - thecoshman

@thecoshman，你还面临着嵌套向量结构变得混乱的风险。使用平坦向量并计算索引可能是最安全的选择。然后，一旦一切正常运行，你可以更改类的内部以找出哪种解决方案最好。 - James Kanze

确实，但是没有统一可能是所期望的东西。不过，我认为将其封装在接口中并不是一个坏主意，至少在测试期间是这样。这将使得很容易交换实现细节，以确定哪种方法最有效。然后，如果你真的想要，你可以删除那个接口。 - thecoshman

Answer 3

一个向量可以在内部完成你需要手动处理的个体大小原始数组的工作，因此只要它们被正确使用，向量应该执行与执行相同任务的原始数组相同。

例如，单个向量应该像单维C数组一样执行，向量的向量应该大致与使用指向数组的每个元素的原始数组的指针的原始数组执行相同的操作。

但是，如果3D数组具有统一的尺寸（即不规则的数组），则向量会支付额外的成本来单独管理它们的尺寸（例如，它们必须单独存储它们的尺寸）。如果任何维度大小在编译时已知，则最好使用`std :: array `这个'STL'容器，因为它不会有那种不必要的开销。您甚至可以使用多维`std :: 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 数组的问题。

- bames53

---

只有在向量调整大小时才需要支付成本，如果不改变它们的大小，则没有成本。 - thecoshman

@thecoshman 我所指的成本是单独存储每个向量长度所需的内存。 - bames53

哦，呸！那只是几个字节。在那开始成为一个问题之前，你需要增加一个数量级的维度。 - thecoshman

请纠正我，但矩阵不是简单的二维结构吗？我不确定这种三维结构的正确术语是什么。 - thecoshman

在数学中，“矩阵”通常意味着二维，但其他用法允许更高的维度。在数学中，我认为更高维度的矩阵被称为“张量”。 - bames53

啊，张量让我想起了痛苦乏味的数学课。祝您好运，先生。 - thecoshman

Answer 4

在HPC中广泛使用的动态分配静态（在分配后维度不可更改）数组对象是平面数组和dope向量的组合。基本上，想法是分配一个大的平坦内存块，然后在其中构建指针树。对于二维数组，该树仅是指向每行开头的指针的简单线性列表。对于三维数组，该树有两个级别，第二级元素的每个元素都指向与第一级对应的2D切片中的一行。将dope向量树放置在分配的内存开头允许您直接应用[]索引运算符，例如A [i] [j] [k]，但需要注意的是&A [i]不是第i个2D切片的开头。

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

- Hristo Iliev