结构体数组总是比数组结构体更快吗？

Question

我想知道对于在C/JAVA编写的只适合存储在RAM中的输入问题，数据布局“结构体数组”（SoA）是否总是比“结构体数组”（AoS）或“指针数组”（AoP）更快。

几天前，我正在改进分子动力学算法（使用C语言），简单来说，该算法基于粒子的力和位置计算粒子之间的相互作用力。

原始粒子由一个包含9个不同双精度浮点数的结构体表示，其中3个用于粒子力（Fx，Fy，Fz），3个用于位置，3个用于速度。该算法具有包含所有粒子指针的数组（AoP）。我决定将布局从AoP更改为SoA以提高缓存利用率。

因此，现在我有一个包含9个数组的结构体，每个数组都存储每个粒子的力量、速度和位置(x,y,z)。每个粒子通过其自己的数组索引访问。

我在性能方面获得了约1.9倍的提升（对于只适合存储在RAM中的输入），因此我想知道通常情况下，从AoP或AoS转换为SoA是否总是表现更好，如果不是，在哪些类型的算法中不会发生这种情况。

- dreamcrash

---

这取决于访问模式。如果您通常按顺序访问每个单独的数组，那么使用SoA可能会使您受益，因为您将获得更高的缓存命中率。这基本上是按行或按列存储数据的相同老故事。 - Matteo Italia

Answer 1

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

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

因此，时间序列信息通常存储为列集合。

- Peter Lawrey

Answer 2

这将取决于您如何访问数据。试想一下，当您以SoA或AoS的方式访问数据时，在硬件中会发生什么。

要回答您的问题，您必须考虑以下几点：

1. 如果缓存不存在，则性能应该相同，假设所有元素的内存访问延迟相等。

2. 现在有了缓存，如果您访问连续的地址位置，肯定会获得性能提升。这在您的情况下是完全有效的。当您使用AoS时，位置在内存中不是连续的，因此您必须在那里失去一些性能。

3. 您必须像for(int i=0;i<1000000;i++) Fx[i] = 0这样的循环中访问数据。因此，如果数据量很大，您将很容易看到小的性能优势。如果您的数据很小，这将无关紧要。

4. 最后，您也不知道正在使用的DRAM。当您访问连续数据时，它将带来一些好处。例如，要了解为什么这样，请参阅维基百科。

- Raj