说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C9-ARM64/matrices.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
9.8. Matrices
矩阵是一个二维数组。C 中的矩阵可以静态分配为二维数组(M[n][m]),可以通过一次 malloc 调用动态分配,也可以动态分配为一个「数组的数组」。我们来考虑数组的数组这种实现。第一个数组包含 n 个元素(M[n]),矩阵中的每个元素 M[i] 又包含一个由 m 个元素组成的数组。下面的代码片段各自声明了一个 4 × 3 的矩阵:
A matrix is a two-dimensional (2D) array. A matrix in C can be statically allocated as a 2D array (
M[n][m]), dynamically allocated with a single call tomalloc, or dynamically allocated as an array of arrays. Let’s consider the array of arrays implementation. The first array containsnelements (M[n]), and each elementM[i]in our matrix contains an array ofmelements. The following code snippets each declare matrices of size 4 × 3:
1 | //statically allocated matrix (allocated on stack) |
在动态分配矩阵的情况下,主数组包含一个连续的 int 指针数组,每个整型指针指向内存中一个不同的数组。图 1 展示了我们通常如何直观地想象这两种矩阵。
In the case of the dynamically allocated matrix, the main array contains a contiguous array of
intpointers. Each integer pointer points to a different array in memory. Figure 1 illustrates how we would normally visualize each of these matrices.

图 1. 静态分配(M1)和动态分配(M2)的 3×4 矩阵示意图
Figure 1. Illustration of a statically allocated (M1) and dynamically-allocated (M2) 3×4 matrix
对于这两种矩阵声明,都可以用双下标语法 M[i][j] 访问元素 (i,j),其中 M 是 M1 或 M2。不过,这两个矩阵在内存中的组织方式不同。尽管两者都把各自主数组中的元素连续存放在内存中,但我们的静态分配矩阵还把所有的行也连续存放在内存中:
For both of the these matrix declarations, element (i,j) can be accessed using the double-indexing syntax
M[i][j], whereMis eitherM1orM2. However, these matrices are organized differently in memory. Even though both store the elements in their primary array contiguously in memory, our statically allocated matrix also stores all the rows contiguously in memory:

图 2. 矩阵 M1 按行主序的内存布局
Figure 2. Matrix M1’s memory layout in row-major order
对于 M2,并不能保证这种连续的排列。回想一下,要在堆上连续地分配一个 n × m 的矩阵,应当用一次 malloc 调用分配 n × m 个元素:
This contiguous ordering is not guaranteed for
M2. Recall that to contiguously allocate an n × m matrix on the heap, we should use a single call tomallocthat allocates n × m elements:
1 | //dynamic matrix (allocated on heap, memory efficient way) |
回想一下,对于 M3 这样的声明,不能用 M[i][j] 记法访问元素 (i,j),而必须用 M3[i*cols + j] 的格式来索引元素。
Recall that with the declaration of
M3, element (i,j) cannot be accessed using theM[i][j]notation. Instead, we must index the element using the format:M3[i*cols + j].
9.8.1. 连续的二维数组
9.8.1. Contiguous Two-Dimensional Arrays
考虑一个函数 sumMat,它的第一个参数是指向一个连续分配的(静态分配的或以节省内存的方式动态分配的)矩阵的指针,另外两个参数是行数和列数,它返回矩阵中所有元素的和。
Consider a function
sumMatthat takes a pointer to a contiguously allocated (either statically allocated or memory-efficient dynamically allocated) matrix as its first parameter, along with a number of rows and columns, and returns the sum of all the elements inside the matrix.
在下面的代码片段中,我们使用按比例计算下标的方式,因为它同时适用于静态分配和动态分配的连续矩阵。回想一下,语法 m[i][j] 不适用于前面讨论的节省内存的连续动态分配。
We use scaled indexing in the code snippet that follows because it applies to both statically and dynamically allocated contiguous matrices. Recall that the syntax
m[i][j]does not work with the memory-efficient contiguous dynamic allocation previously discussed.
1 | int sumMat(int *m, int rows, int cols) { |
下面是对应的汇编,每一行都加上了英文注解:
Here is the corresponding assembly. Each line is annotated with its English translation:
1 | Dump of assembler code for function sumMat: |
局部变量 i、j 和 total 分别存放在栈位置 sp + 20、sp + 24 和 sp + 28 处。输入参数 m、row 和 cols 分别存放在位置 sp + 8、sp + 4 和 sp(栈顶)处。有了这些知识,我们来放大只负责访问矩阵中元素 (i,j) 的那部分代码(0x8a8 到 0x8d8):
The local variables
i,j, andtotalare stored at stack locationssp + 20,sp + 24andsp + 28, respectively. The input parametersm,row, andcolsare stored at locationssp + 8,sp + 4, andsp(top of stack), respectively. Using this knowledge, let’s zoom in on the component that just deals with the access of element (i,j) in our matrix (0x8a8 to 0x8d8):
1 | 0x8a8 <+36>: ldr w1, [sp, #20] // w1 = i |
第一组指令计算值 cols * i,并把它放到寄存器 w1 中。回想一下,对于某个名为 matrix 的矩阵,matrix+i*cols 等价于 &matrix[i]。
The first set of instructions calculates the value
cols * iand places it in registerw1. Recall that for some matrix calledmatrix,matrix+i*colsis equivalent to&matrix[i].
1 | 0x8b4 <+48>: ldr w0, [sp, #24] // w0 = j |
下一组指令计算 (cols*i + j) * 4。编译器把下标 cols * i + j 乘以四,是因为矩阵中的每个元素都是四字节的整数,这次乘法让编译器能算出正确的偏移量。<sumMat+56> 这一行的 sxtw 指令把 w0 的内容符号扩展为 64 位整数,因为这个值要用于地址计算。
The next set of instructions computes
(cols*i + j) * 4. The compiler multiplies the indexcols * i + jby four because each element in the matrix is a four-byte integer, and this multiplication enables the compiler to compute the correct offset. Thesxtwinstruction on line<sumMat+56>sign-extends the contents ofw0into a 64-bit integer, since that value is needed for address calculation.
接下来这组指令把算出的偏移量加到矩阵指针上,并对它解引用,得到元素 (i,j) 的值:
The following set of instructions adds the calculated offset to the matrix pointer and dereferences it to yield the value of element (i,j):
1 | 0x8c4 <+64>: ldr x1, [sp, #8] // x1 = m |
第一条指令把矩阵 m 的地址加载到寄存器 x1 中。add 指令把 (cols * i + j) * 4 加到 m 的地址上,正确算出元素 (i,j) 的偏移位置,并把结果放到寄存器 x0 中。第三条指令对 x0 中的地址解引用,把值(m[i * cols + j])放入 w0。注意这里使用 w0 作为目标组成部分寄存器;由于我们的矩阵包含的是整数,而整数占四个字节,所以这里同样使用组成部分寄存器 w0 而不是 x0。
The first instruction loads the address of matrix
minto registerx1. Theaddinstruction adds(cols * i + j) * 4to the address ofmto correctly calculate the offset of element (i,j) and then places the result in registerx0. The third instruction dereferences the address inx0and places the value (m[i * cols + j]) intow0. Notice the use ofw0as the destination component register; since our matrix contains integers, and integers take up four bytes of space, component registerw0is again used instead ofx0.
最后三条指令把 total 的当前值加载到寄存器 w1 中,把 total 与 m[i * cols + j] 相加,然后用得到的和更新 total。
The last three instructions load the current value of
totalinto registerw1, addtotalwithm[i * cols + j], and then updatetotalwith the resulting sum.
我们来考虑矩阵 M1 中的元素 (1,2) 是如何被访问的(下面重新给出这张图)。
Let’s consider how element (1,2) is accessed in matrix M1 (figure reproduced below).

图 3. 矩阵 M1 按行主序的内存布局
Figure 3. Matrix M1’s memory layout in row-major order
元素 (1,2) 位于地址 M1 + 1 * cols + 2 处。由于 cols = 3,元素 (1,2) 对应于 M1 + 5。要访问这个位置上的元素,编译器必须把 5 乘以 int 数据类型的大小(四个字节),得到偏移位置 M1 + 20,它对应于图中的字节 a20。对这个位置解引用,得到元素 5,它确实是矩阵中的元素 (1,2)。
Element (1,2) is located at address
M1 + 1 * cols + 2. Sincecols= 3, element (1,2) corresponds toM1 + 5. To access the element at this location, the compiler must multiply 5 by the size of theintdata type (four bytes), yielding the offsetM1 + 20, which corresponds to byte a20 in the figure. Dereferencing this location yields element 5, which is indeed element (1,2) in the matrix.
9.8.2. 不连续的矩阵
9.8.2. Noncontiguous Matrix
不连续矩阵的实现要稍微复杂一些。图 4 直观地展示了 M2 在内存中可能的布局。
The noncontiguous matrix implementation is a bit more complicated. Figure 4 visualizes how
M2may be laid out in memory.

图 4. 矩阵 M2 在内存中的不连续布局
Figure 4. Matrix M2’s noncontiguous layout in memory
注意,M2 中的指针数组是连续的,M2 的某个元素所指向的每个数组(例如 M2[i])也是连续的。但是,各个数组彼此之间并不连续。由于 M2 是一个指针数组,M2 的每个元素占八个字节。与之不同,由于每个 M2[i] 都是一个 int 数组,每个 M2[i] 数组中的元素相隔四个字节。
Notice that the array of pointers in
M2is contiguous, and that each array pointed to by some element ofM2(e.g.,M2[i]) is contiguous. However, the individual arrays are not contiguous with one another. SinceM2is an array of pointers, each element ofM2takes eight bytes of space. In contrast, because eachM2[i]is anintarray, the elements of everyM2[i]array are four bytes apart.
下面例子中的 sumMatrix 函数以一个整型指针数组(称为 matrix)作为第一个参数,以行数和列数作为第二、第三个参数:
The
sumMatrixfunction in the follow example takes an array of integer pointers (calledmatrix) as its first parameter, and a number of rows and columns as its second and third parameters:
1 | int sumMatrix(int **matrix, int rows, int cols) { |
尽管这个函数看起来与前面的 sumMat 函数几乎一模一样,但这个函数接收的矩阵由一个连续的指针数组构成。每个指针存放着一个单独的连续数组的地址,这个数组对应于矩阵中单独的一行。
Even though this function looks nearly identical to the
sumMatfunction shown earlier, the matrix accepted by this function consists of a contiguous array of pointers. Each pointer contains the address of a separate contiguous array, which corresponds to a separate row in the matrix.
下面是 sumMatrix 对应的汇编,每一行都加上了英文注解。
The corresponding assembly for
sumMatrixfollows. Each line is annotated with its English translation.
1 | Dump of assembler code for function sumMatrix: |
同样,变量 i、j 和 total 分别位于栈地址 sp + 20、sp + 24 和 sp + 28 处。输入参数 matrix、row 和 cols 分别位于栈地址 sp + 8、sp + 4 和 sp(栈顶)处。我们来放大专门负责访问元素 (i, j),即 matrix[i][j] 的那部分代码,它位于指令 0x944 到 0x970 之间:
Again, variables
i,j, andtotalare at stack addressessp20,sp + 24, andsp + 28, respectively. The input parametersmatrix,row, andcolsare located at stack addressessp + 8,sp + 4, andsp(top of stack), respectively. Let’s zoom in on the section that deals specifically with an access to element (i, j), ormatrix[i][j], which is between instructions 0x944 and 0x970:
译注
原书网页此处的 sp + 20 排版出错,显示成了 sp、反斜杠和换行后的 20。
1 | 0x944 <+36>: ldrsw x0, [sp, #20] // x0 = signExtend(i) |
这个例子中的五条指令计算 matrix[i],即 *(matrix+i)。由于 matrix[i] 存放的是一个指针,i 先被转换成 64 位整数。然后,编译器用移位操作把 i 乘以八,再把结果加到 matrix 上,得到正确的地址偏移(回想一下,指针的大小是八个字节)。随后,<sumMatrix+52> 处的指令对算出的地址解引用,得到元素 matrix[i]。
The five instructions in this example compute
matrix[i], or*(matrix+i). Sincematrix[i]contains a pointer,iis first converted to a 64-bit integer. Then, the compiler multipliesiby eight by using a shift operation, and then adds the result tomatrixto yield the correct address offset (recall that pointers are eight bytes in size). The instruction at<sumMatrix+52>then dereferences the calculated address to get the elementmatrix[i].
由于 matrix 是一个 int 指针数组,位于 matrix[i] 的元素本身就是一个 int 指针。matrix[i] 中的第 j 个元素位于 matrix[i] 数组中偏移 j × 4 处。
Since
matrixis an array ofintpointers, the element located atmatrix[i]is itself anintpointer. The jth element inmatrix[i]is located at offsetj × 4in thematrix[i]array.
下一组指令取出数组 matrix[i] 中的第 j 个元素:
The next set of instructions extract the jth element in array
matrix[i]:
1 | 0x958 <+56>: ldrsw x0, [sp, #24] // x0 = signExtend(j) |
这段代码中的第一条指令把变量 j 加载到寄存器 x0 中,同时进行符号扩展。然后,编译器用左移(lsl)指令把 j 乘以四,并把结果存放在寄存器 x0 中。最后,编译器把得到的值加到位于 matrix[i] 中的地址上,得到元素 matrix[i][j] 的地址,即 &matrix[i][j]。随后,<sumMatrix+68> 处的指令对这个地址解引用,得到 matrix[i][j] 处的值,并存入寄存器 w0。最后,<sumMatrix+72> 到 <sumMatrix+80> 的指令把 total 与 matrix[i][j] 相加,并用得到的和更新变量 total。
The first instruction in this snippet loads variable
jinto registerx0, sign-extending it in the process. The compiler then uses the left shift (lsl) instruction to multiplyjby four and stores the result in registerx0. The compiler finally adds the resulting value to the address located inmatrix[i]to get the address of elementmatrix[i][j], or&matrix[i][j]. The instruction at<sumMatrix+68>then dereferences the address to get the value atmatrix[i][j], which is then stored in registerw0. Lastly, the instructions from<sumMatrix+72>through<sumMatrix+80>addtotaltomatrix[i][j]and update the variabletotalwith the resulting sum.
我们来考虑访问 M2[1][2] 的例子(下面重新给出这张图)。
Let’s consider an example access to
M2[1][2](figure reproduced below).

注意,M2 从内存位置 a0 开始。编译器先计算 M2[1] 的地址:把 1 乘以 8(sizeof(int *)),再加到 M2 的地址(a0)上,得到新地址 a8。对这个地址解引用,得到与 M2[1] 关联的地址,即 a36。然后,编译器把下标 2 乘以 4(sizeof(int)),把结果(8)加到 a36 上,得到最终地址 a44。对地址 a44 解引用,得到值 5。果然,上图中与 M2[1][2] 对应的元素的值是 5。
Note that
M2starts at memory location a0. The compiler first computes the address ofM2[1]by multiplying 1 by 8 (sizeof(int *)) and adding it to the address ofM2(a0), yielding the new address a8. A dereference of this address yields the address associated withM2[1], or a36. The compiler then multiplies index 2 by 4 (sizeof(int)), and adds the result (8) to a36, yielding a final address of a44. The address a44 is dereferenced, yielding the value 5. Sure enough, the element in [DynamicMatrix6a64repro] that corresponds toM2[1][2]has the value 5.