4

我想知道数据布局Structs of Arrays( SoA ) 是否总是比Array of Structs( AoS ) 或Array of Pointers( AoP ) 快于只适合RAM编程输入的问题C/JAVA。

几天前，我正在改进分子动力学算法（用 C 语言）的性能，总结在这个算法中，它是根据粒子的力和位置计算粒子之间的力相互作用。

原始粒子由包含 9 个不同双精度值的结构体表示，3 个表示粒子力 (Fx,Fy,Fz) ，3 个表示位置，3 个表示速度。该算法有一个数组，其中包含指向所有粒子 ( AoP ) 的指针。我决定将布局从AoP更改为SoA以改善缓存使用。

所以，现在我有一个包含 9 个数组的 Struct，其中每个数组存储每个粒子的力、速度和位置 (x,y,z)。每个粒子都通过它自己的数组索引来访问。

我获得了大约1.9x的性能增益（对于仅适合 RAM 的输入），所以我想知道通常从AoP或AoS更改为SoA是否总是会表现更好，如果不是在哪种类型的算法中这样做不会发生。

4

2 回答 2

8

很大程度上取决于所有领域的有用程度。如果您有一个数据结构，其中使用一个字段意味着您可能会使用所有字段，那么结构数组会更有效，因为它将您可能需要的所有东西放在一起。

假设您有时间序列数据，您只需要选择一小部分可能的字段。你可能有关于一个事件或时间点的各种数据，但你只需要说其中的 3-5 个。在这种情况下，数组结构更有效，因为 a) 你不需要缓存你不使用的字段 b) 你经常按顺序访问值，即缓存一个字段，它的下一个值和它的下一个是有用的。

出于这个原因，时间序列信息通常存储为列的集合。

于 2012-10-30T16:02:18.880 回答
3

这将取决于您访问数据的方式。试着想象一下，当您在 SoA 或 AoS 中访问数据时，硬件中究竟发生了什么。

要推理您的问题，您必须考虑以下事项 -

  1. 如果没有缓存，性能应该是相同的，假设所有数据元素的内存访问延迟是相等的。
  2. 现在有了缓存，如果你访问连续的地址位置，你肯定会得到性能提升。这在您的情况下完全有效。当你有 AoS 时，这些位置在内存中是不连续的，所以你必须在那里失去一些性能。
  3. 您必须在 for 循环中访问您的数据，例如for(int i=0;i<1000000;i++) Fx[i] = 0. 因此，如果数据量很大，您将很容易看到小的性能优势。如果您的数据很小，这无关紧要。
  4. 最后，您也不知道您正在使用的 DRAM。当您访问连续数据时，它将有一些好处。例如，要了解为什么会这样，您可以参考wiki。
于 2012-10-30T16:09:03.363 回答