1

哪个最快？一个boost::multi_array或一个std::vector？我将（不是恒定的）17.179.869 个元素存储在 3 个维度中，需要在for循环中非常快速且非常频繁地访问这些元素。最有表现力的会是什么？一个std::vector或一个boost::multi_array？

（我不希望它在一秒钟内完成，但我希望它尽可能高效，因为纳秒的差异可以节省大量时间。）

4

3 回答 3

3

Best advice is to benchmark it by yourself.

In any case, since you seem to have constant size there are other solutions:

  • plain C arrays (eg. int data[X][Y][Z])
  • plain one dimensional C array in which you compute indices by yourself, eg X*W*H + Y*W + Z, can be handy in some situations
  • std::array, which is basically a C++ array with some synctactic sugar taken from STL collections
  • std::vector, which I guess is the first solution that can be tried
  • boost::multi_array, which is meant to support N dimensional arrays so it can be overkill for your purpose but probably has a better locality of data compared to a vector.
于 2013-07-26T17:38:45.420 回答
2

唯一确定的方法是同时尝试并分析代码。然而，作为一堆想法，这就是我认为你会发现的。

  1. 对于您正在处理的大量元素（2e10+），对元素的访问不会像将这些元素加载到 cpu 缓存中的缓存压力那么重要。预取器将坐在那里尝试加载这些元素，这将占用大部分时间。
  2. 访问 2（或 3D）非连续 C 数组意味着 CPU 必须四处从内存的不同部分获取内容。boost::multi_array 通过在幕后将其存储为连续块来解决这个问题；但这样做有它自己的开销。正如@Jack 所说，带有索引的普通一维数组是最好的，即使那样你也可以做一些事情来确保索引最小化。（例如记忆）
  3. 您在循环中所做的工作将显着影响您的时间安排。分支预测器将是最大的贡献者。如果这是一个简单的数学运算，没有 if/else 语句，您可能会获得最佳性能，并且编译器可能会将其优化为 SSE 指令。如果您有复合类型（而不是 int/float/char），那么您将不得不正确布置它们以优化访问。
  4. 我几乎会建议，尝试两者，然后返回一个新的 SO 问题，该问题已经编写了您的循环，并询问如何优化该部分。几乎总是可以向编译器提供提示，以确保它知道您的意图。

在一天结束时，试试看

于 2013-07-27T09:05:39.820 回答
2

这些库向量类被设计为易于使用且相对安全。它们在设计范围内尽可能快，但没有什么能比你自己做的更好（除了手工编码的组装）。对于您正在谈论的大小（2e10 个元素），我会更关心效率而不是用户友好性。如果您的最内层循环对每个元素进行的计算很少，您会发现索引计算占主导地位，这建议进行一些展开和指针步进。（也许你可以指望编译器做一些展开，但我不在乎也许。）

于 2013-07-26T21:22:04.700 回答