在处理多维数组时，程序员必须在项目早期做出的一个重要决定是使用何种内存布局来存储数据，以及如何以最有效的方式访问此类数据。由于计算机内存本质上是线性的 - 一种一维结构，因此可以通过多种方式在其上映射多维数据。在本文中，我想详细研究这个主题，讨论各种可用的内存布局及其对代码性能的影响。
行优先与列优先
到目前为止，多维数组数据的两种最常见的内存布局是 行优先 和 列优先 。
使用二维数组（矩阵）时，行优先与列优先很容易描述。矩阵的行优先布局将第一行放在连续的内存中，然后是第二行，然后是第三行，依此类推。列优先布局将第一列放在连续的内存中，然后是第二列，依此类推。
更高的维度更难可视化，所以让我们从一些展示二维布局如何工作的图表开始。
二维行专业
首先，对本文的命名做一些说明。计算机内存将表示为一个线性阵列，左侧是低地址，右侧是高地址。此外，我们将为矩阵使用程序员表示法：行和列从零开始，位于矩阵的左上角。行索引从上到下遍历行；列索引从左到右遍历列。
如上所述，在行优先布局中，矩阵的第一行放在连续的内存中，然后是第二行，依此类推：
描述行优先布局的另一种方式是 列索引变化最快 。通过查看图表底部的线性布局，这应该是显而易见的。如果你从左到右阅读元素索引对，你会注意到列索引一直在变化，而行索引每行只变化一次。
对于程序员来说，另一个重要的观察是给定一个行索引
和一个列索引
，它们在线性表示中表示的元素的偏移量是：
其中 ncols 是矩阵中每行的列数。很容易看出这个等式符合上图中的线性布局。
二维列专业
描述列优先的 2d 布局只是采用行优先的描述并将“行”的每个外观替换为“列”，反之亦然。矩阵的第一列放在连续内存中，然后是第二列，依此类推：
在列优先布局中， 行索引变化最快 。可以使用以下等式找到列优先布局中元素的偏移量：
其中 nrows 是矩阵中每列的行数。
超越二维 - n 维数组的索引和布局
尽管矩阵是程序员处理的最常见的多维数组，但它们绝不是唯一的。多维数组的符号完全可以推广到二维以上。这些实体通常称为“nd 数组”或“张量”。
当我们移动到 3d 及更高版本时，最好将矩阵的行/列符号留在后面。这是因为由于行、列和笛卡尔坐标系之间的 常见混淆 ，这种表示法不容易转换为 3 维。在 4 维及以上，我们无论如何都失去了描述多维实体的任何纯视觉直觉，因此最好坚持使用一致的数学符号。
因此，让我们讨论一些任意数量的维度
d
，编号从 1 到
d
。对于每个维度
,
是维度的大小。另外，维度中元素的索引
是
.例如，在上面最新的矩阵图中（其中显示了列布局），我们有
.如果我们选择维度 1 作为行，维度 2 作为列，那么
, 矩阵左下角的元素有
和
.
在多维数组的行优先布局中， 最后 一个索引变化最快。在矩阵的情况下，最后一个索引是列，所以这等同于前面的定义。
给出一个
维数组，使用上面显示的符号，我们根据其索引计算元素的内存位置：
对于一个矩阵，
，这减少到：
这正是我们在上面看到的行优先布局的公式，只是使用了稍微更正式的符号。
同样，在多维数组的列优先布局中，
第一个
索引变化最快。给出一个
维数组，我们根据其索引计算元素的内存位置：
再一次，对于一个矩阵
这减少到熟悉的：
3d 示例
让我们看看这是如何在 3d 中实现的，我们仍然可以想象它。假设有 3 个维度：行、列和深度。下图显示了 3d 数组的内存布局
，
在行主要
：
请注意最后一个维度（在本例中为深度）如何变化最快而第一个（行）变化最慢。给定元素的偏移量是：
例如，索引为 2,1,1 的元素的偏移量为 22。
作为练习，试着弄清楚这个数组将如何按 列优先 顺序排列。但要注意 - 有一个警告！ column-major 一词可能会让您认为列是变化最慢的索引，但这是错误的。 最后 一个索引是列优先中变化最慢的，这里最后一个索引是深度，而不是列。事实上，列在变化速度方面处于中间位置。这就是为什么在上面的讨论中我建议在超过 2d 时删除行/列符号。在更高的维度上它变得混乱，所以最好参考指数的相对变化率，因为这些是明确的。
事实上，人们可以设想一种混合（或“混合”）布局，其中第二维比第一维或第三维变化得更快。这既不是行优先也不是列优先，但它本身是一种一致且完全有效的布局，可能会使某些应用程序受益。有关为什么我们会选择一种布局而不是另一种布局的更多详细信息，请参阅本文后面的内容。
历史：Fortran 与 C
虽然了解特定数据集使用的布局对于良好的性能至关重要，但对于一般来说哪种布局“更好”的问题没有单一的答案。这与大端与小端的争论没有太大区别；重要的是选择一个一致的标准并坚持下去。不幸的是，就像计算世界中几乎总是发生的那样，不同的编程语言和环境选择了不同的标准。
在今天仍然流行的编程语言中，Fortran 绝对是先驱之一。而 fortran（对于科学计算仍然非常重要）使用列优先布局。我在某处读到，这样做的原因是列向量在线性代数计算中更常用并被认为是“规范的”。我个人不买这个，但你可以做出自己的判断。
许多现代语言都追随 Fortran 的脚步——matlab、r、julia 等等。最强烈的原因之一是他们想使用 lapack——一个用于线性代数的快速 fortran 库，因此使用 fortran 的布局是有意义的。
另一方面，c 和 c++ 使用行优先布局。以他们为榜样的是其他一些流行的语言，例如 python、pascal 和 mathematica。由于多维数组是 c 语言中的一流类型，因此该标准在第 6.5.2.1 节中非常明确地定义了布局。
事实上，如果您考虑 c 中的多维数组是如何索引的，那么让第一个索引变化最慢而最后一个索引变化最快是有意义的。
鉴于声明：
int x[3][5];
那么 x 是一个包含 3 个元素的数组，每个元素都是一个包含 5 个整数的数组。 x[1]是x中包含的第二个5整数数组的地址，x[1][4]是x中第二个5整数数组的第五个整数。这些索引规则意味着行优先布局。
这并不是说 c 不能选择列优先布局。它可以，但是它的多维数组索引规则也必须不同。结果可能与我们现在所拥有的一样一致。
此外，由于 c 允许您操作指针，因此您可以通过自己计算多维数组的偏移量来决定程序中数据的布局。事实上，这就是大多数 C 程序的编写方式。
内存布局示例 - numpy
到目前为止，我们纯粹从概念上讨论了内存布局——使用图表和数学公式进行索引计算。多维数组如何存储在内存中的“真实”示例值得一看。为此，python 的 numpy 库是一个很好的工具，因为它支持两种布局类型，并且很容易在交互式 shell 中使用。
numpy.array 构造函数 可用于创建多维数组。它接受的参数之一是 order，它是 c 风格布局（行优先）的“c”或 fortran 风格布局（列优先）的“f”。 “c”是默认值。让我们看看这看起来如何：
int x[3][5];
在“c”顺序中，行的元素如预期的那样是连续的。现在让我们试试 Fortran 布局：
int x[3][5];
对于更复杂的示例，让我们将以下 3d 数组编码为 numpy.array 并查看其布局方式：
该数组有两行（第一维）、4 列（第二维）和深度 2（第三维）。作为嵌套的 Python 列表，这是它的表示形式：
int x[3][5];
和内存布局，在 c 和 fortran 命令中：
int x[3][5];
请注意，在 c 布局（行优先）中，第一维（行）变化最慢，而第三维（深度）变化最快。在 Fortran 布局（主要列）中，第一个维度变化最快，而第三个维度变化最慢。
性能：为什么值得关注数据的布局
读完这篇文章后，人们可能想知道为什么这些很重要。这不就是标准分歧的另一种方式，a-la endianness 吗？只要我们都同意布局，这不就是无聊的实现细节吗？我们为什么要关心这个？
答案是：性能。我们在这里谈论的是数值计算（大型数据集上的数字运算），其中性能几乎总是至关重要。事实证明，将算法的工作方式与数据布局相匹配可以成就或破坏应用程序的性能。
简短的要点是： 始终按照布局的顺序遍历数据 。如果您的数据以行优先布局存储在内存中，则在转到下一行之前遍历每一行，等等。本节的其余部分将解释为什么会这样，还将提供一个带有一些测量值的基准掩码以了解该决定的后果。
现代计算机体系结构有两个方面对代码性能有很大影响并且与我们的讨论相关：缓存和向量单元。当我们遍历行优先数组的每一行时，我们按顺序访问该数组。这种模式具有 空间局部性 ，这使得代码非常适合缓存优化。此外，根据我们对数据所做的操作，CPU 的矢量单元可以启动，因为它也需要连续访问。
从图形上看，它看起来像下图。假设我们有一个数组：int array[128][128]，我们遍历每一行，当访问了当前行中的所有列时跳转到下一行。每个灰色单元格中的数字是内存地址——它增长 4，因为这是一个整数数组。蓝色编号箭头按访问顺序列举访问：
在这里，缓存和向量指令的最佳使用应该是显而易见的。因为我们总是按顺序访问元素，所以这是 cpu 缓存启动的完美场景——我们 总是会访问缓存 。事实上，我们总是命中最快的缓存 - l1，因为 cpu 正确地提前预取了所有数据。
此外，由于我们总是一个接一个地读取 32 位字，因此我们可以利用 cpu 的矢量单元来加载数据（也许过程会在稍后进行）。紫色箭头显示了如何使用一次获取 128 位块（四个 32 位字）的 sse 矢量加载来完成此操作。在实际代码中，这可以通过内部函数或依靠编译器的自动向量化器来完成（我们很快就会在实际代码示例中看到）。
将此与一次访问一 列行 优先数据进行对比，在移动到下一列之前遍历每一列：
我们在这里失去了空间局部性，除非阵列非常窄。如果列数很少， 则可能 会在缓存中找到连续的行。然而，在更典型的应用程序中，数组很大，当访问 #2 发生时，它访问的内存很可能在缓存中无处可寻。毫不奇怪，我们也丢失了向量单元，因为访问不是对连续内存进行的。
但是如果您的算法 需要 逐列而不是逐行访问数据，您应该怎么办？很简单的！这正是列主要布局的目的。对于列优先数据，这种访问模式将达到我们在连续访问行优先数据时看到的所有相同的架构最佳点。
上面的图表应该足够有说服力，但让我们做一些实际测量，看看这些影响到底有多大。
此处提供了 基准测试的完整代码，因此我将只展示几个选定的片段。我们将从布置在线性内存中的基本矩阵类型开始：
int x[3][5];
矩阵使用行优先布局：使用此 c 表达式访问其元素：
int x[3][5];
这是一个将两个这样的矩阵相加的函数，使用“错误的”访问模式 - 在转到下一列之前迭代每列中的行。查看 c 代码很容易发现访问模式 - 内部循环是变化更快的索引，在这种情况下它是行：
int x[3][5];
这是一个使用更好模式的版本，在转到下一行之前遍历每一行中的列：
int x[3][5];
这两种访问模式如何比较？根据本文中的讨论，我们预计按行访问模式会更快。但是快多少？向量化与缓存的有效使用相比起什么作用？
为了尝试这个，我在各种大小的矩阵上运行了访问模式，并添加了禁用矢量化的按行模式的变体。这是结果；垂直条代表带宽——给定函数处理（添加）了多少亿项（32 位字）。
一些观察：
- 对于大于 64x64 的矩阵大小，按行访问比按列访问快得多（6-8 倍，取决于大小）。在 64x64 的情况下，我相信发生的是两个矩阵都适合我机器的 32-kb l1 缓存，因此按列模式实际上设法找到缓存中的下一行。对于更大的尺寸，矩阵不再适合 l1，因此按列版本必须经常转到 l2。
- 在所有情况下，矢量化版本都比非矢量化版本高出 2-3 倍。在大矩阵上，加速有点小；我认为这是因为在 256x256 及以上的矩阵不再适合 l2（我的机器有 256kb）并且需要更慢的内存访问。所以 cpu 平均花费更多的时间等待内存。
- 向量化逐行访问相对于逐列访问的整体加速是巨大的——对于大型矩阵高达 25 倍。
我不得不承认，虽然我预计按行访问会更快，但我没想到会快 这么多 。显然，为数据的内存布局选择正确的访问模式对于应用程序的性能绝对是至关重要的。
概括
本文从多个角度考察了多维数组布局的问题。主要要点是：知道您的数据是如何布局的并相应地访问它。在基于 C 的编程语言中，即使二维数组的默认布局是行优先的，当我们使用指向动态分配数据的指针时，我们可以自由选择我们喜欢的任何布局。毕竟，多维数组只是线性存储系统之上的逻辑抽象。
由于现代 cpu 架构的奇迹，选择“正确”的方式来访问多维数据可能会导致巨大的加速；因此，在处理大型多维数据集时，这是程序员应该始终牢记的事情。
取自 c11 标准的 n1570 草案。在过去的某个时候，术语“字”显然与 16 位实体相关联（“双字”表示 32 位等），但现在它已经过载了。在各种在线参考资料中，您会发现“字”可以是 16 位到 64 位之间的任何内容，具体取决于 cpu 架构。所以我将通过明确提及单词的位大小来故意回避混淆。有关完整详细信息，包括函数属性和编译器标志，请参阅 基准存储库 。特别感谢 nadav rotem 帮助我思考了我最初遇到的一个问题，因为 g++ 在将函数内联到基准测试时忽略了我的 no-tree-vectorize 属性。我关闭内联来解决这个问题。