哪种存储方案是最优的，很大程度上取决于访问模式。您已经说过一次访问一个粒子，但是您是要按顺序访问粒子，还是随机访问？这个问题的另一个传统名称是 struct-of-arrays 与 array-of-structs。

这里的关键是了解内存层次结构如何在 CPU 上工作（参见例如 https://www.scss.tcd.ie/Jeremy.Jones/CS3021/5%20caches.pdf以及许多问题关于堆栈溢出的这个主题）。从主内存读取有非常大的延迟，这将导致执行中的长时间停顿，除非通过预取来缓解这种情况。每次从主内存读取都会读取一个缓存行的数据，将其放入缓存中，并且从缓存中读取是相对空闲的。

因此，例如，如果您有一个矩阵，并且它在内存中以列主要顺序存储为 然后读取（或 ) 将从到 的所有八个元素放入缓存中（假设正确对齐和典型的 64 字节缓存行和 8 字节的元素大小），使它们可以自由使用权。$(a_{ij})_{1\leq i,j\leq 3}$

$$a_{11}, a_{21}, a_{31}, a_{12}, a_{22}, a_{32}, a_{13}, a_{23}, a_{33},$$ $a_{11}$ $a_{11},\ldots,a_{23}$$a_{11}$$a_{23}$

如果你有几个不同的数组，一个 struct-of-arrays，像 你读，您将有效地读取每个数组的前八个元素。如果您最终立即使用接下来的七个元素，那很好。如果不是，那么通过读取 24 个元素而不是 3 个元素，这浪费了 7/8 的内存带宽，这是低效的。

$$x_{1}, \ldots, \qquad y_{1}, \ldots, \qquad z_{1}, \ldots$$ $x_1, y_1, z_1$

相反，如果您将它们存储为结构数组， 那么读取将读取前八个元素。如果您使用接下来的那些元素，则没有太大区别，否则您会浪费 5/8（读取 8 而不是 3）的内存带宽 - 请注意，这仍然比读取 24 个元素（如上一个示例）要好。

$$x_1, y_1, z_1, x_2, y_2, z_2, \ldots$$ $x_1,y_1,z_1$

有九个 8 字节的元素，如果你知道你会连续访问它们，那么任何一种方式都应该没有太大的区别，如上所述。如果您以随机顺序访问它们，则读取一组九个元素将导致元素（如果存储为数组结构）或 元素（如果存储为结构数组） - 这可能是一个非常大的性能提升。$9\times 8 = 72$$\lceil \frac{9}{8}\rceil\times 8 = 16$

我觉得列优先和行优先之间的区别在这里有点红鲱鱼 - 关键是了解访问模式，并确保数据布局与访问模式匹配。下一个最重要的事情是预取，这是一种隐藏相对较大的内存访问延迟的技术。

另一个需要考虑的相关问题是您如何访问您之前已经读取的数据，以及它是否可能仍保留在缓存中，或者是否已清除它以便为其他数据让路，从而导致缓存未命中 - 数组字节是，很可能完全适合 L2 或 L3 缓存。$5000\times 9\times 8$$360\,\mathrm{KB}$

如果您的程序涉及在不同内核上运行的多个线程，并且每个内核可能具有单独的较低级别缓存，则情况会变得更加复杂。

请注意，顺便提一下，对于非顺序访问模式，如果高速缓存行是 8 个元素，那么每个粒子有 9 个元素本身效率有点低，因为读取 9 个元素本质上等同于读取 16 个元素 - 一种技术是拆分数据将经常使用的部分与很少使用的部分进行区分，以便经常使用的部分更适合。

拥有多行或多列不会受到惩罚。不确定“许多内存地址”的惩罚是什么意思，但没有这样的惩罚。

我所说的一些事情取决于你的程序将运行的架构的确切属性。使用像 R 或 Matlab 这样的解释性语言也会严重影响这一点——对于 C++ 来说，它应该成立。一般来说，最好使用结构数组模式，除非您有特定的理由不这样做。

R、Matlab 和 Armadillo（Mat类）矩阵使用列优先顺序，因此您应该创建 3xN 矩阵，以便每组 3 个值连续存储在内存中。

更多信息：
您应该存储矩阵，以便一起访问的元素按顺序存储在内存中。矩阵存储的内存顺序取决于语言、数据结构，甚至可能取决于实现。用于矩阵的两种存储顺序称为“行优先”或“列优先”顺序。在行优先顺序中，同一行中的元素连续存储在内存中，反之亦然。

选择正确排列的好处是减少高速缓存未命中和减少内存延迟。高效的缓存使用有时会导致大幅加速。

最后一点：C 和 C++ 2D 数组是行优先的，但 Armadillo 的 Mat 类是列优先的，因为存储布局被设计为与使用 Fortran 的列优先存储顺序的 BLAS 和 LAPACK 兼容。Matlab 的大部分基础和语法都来自 Fortran，因此它自然地使用列优先存储顺序。我不确定 R 存储顺序背后的历史，但也许有人会对这些信息发表评论。

资料来源：
Wikipedia
R for Programmers
MATLAB 文档
Armadillo 文档 (pdf)

列优先顺序似乎更自然。例如，假设您想将电影逐张保存到文件中，那么您使用的是列顺序，这非常直观，没有人会以行优先顺序保存它。

如果你是 C/C++ 程序员，你应该使用一些更高级别的矩阵库（Eigen，Armadillo，...），默认列优先顺序。尽管 C/C++ 提供了一些提醒矩阵索引的东西，但只有疯子才会使用具有行优先顺序的原始 C 指针。

为简单起见，所有具有行优先顺序的东西都应该被认为至少是奇怪的形式。逐片切片只是自然顺序，它意味着列优先顺序（如 Fortran）。我们的父亲/母亲选择它有一个很好的理由。

不幸的是，在它变得清晰之前，可能由于缺乏经验，以行优先顺序创建了几个有趣的库。

为了澄清行主顺序的定义，其中右索引在内存中一步变化得更快，例如 A(x,y,z) 它是 z-index，这意味着在内存中来自不同切片的像素是相邻的，我们会不想。对于电影 A(x,y,t)，最后一个索引是时间 t。不难想象，以行优先模式保存电影根本不可能。