多维数组 & Row-major Order：深入探讨

I’m happy to translate the article for you, but I’ll need the full text you’d like translated. Could you please paste the content (excluding the source line you’ve already provided) here? Once I have the article, I’ll translate it into Simplified Chinese while preserving the original formatting, markdown, and any code blocks.

多维数组与行主序

概念视图

int matrix[3][4];

把它看作一个二维网格：

[0][0]  [0][1]  [0][2]  [0][3]
[1][0]  [1][1]  [1][2]  [1][3]
[2][0]  [2][1]  [2][2]  [2][3]

物理视图

内存是线性的（单维的）。CPU 只能顺序寻址内存，所以编译器把多维数组映射到一块连续的内存块上。

行主序 按行存储元素；最右侧的下标变化最快。

地址计算

对于数组 type array[ROWS][COLS]：

address = base_address + (i * COLS + j) * sizeof(type)

• i * COLS – 跳过 i 整行。
• + j – 在当前行内移动 j 个元素。
• * sizeof(type) – 按字节扩展。

示例 – int matrix[3][4] 位于 0x1000，元素 matrix[2][3]：

address = 0x1000 + (2 * 4 + 3) * 4
        = 0x1000 + 11 * 4
        = 0x102C

三维数组

对于 type array[D1][D2][D3]：

address = base + (i * D2 * D3 + j * D3 + k) * sizeof(type)

• i * D2 * D3 – 跳过 i 整个“平面”。
• j * D3 – 在当前平面内跳过 j 行。
• k – 行内的位置。

通用 N 维公式

对于 array[i1][i2]...[iN]，维度为 [D1][D2]...[DN]：

offset = i1 * (D2*D3*...*DN) +
         i2 * (D3*D4*...*DN) +
         ...
         i(N‑1) * DN +
         iN
address = base + offset * sizeof(type)

编译器翻译示例

int arr[3][4][5];
int x = arr[1][2][3];   // becomes
int x = *(arr + (1*4*5 + 2*5 + 3));

衰减为指针

• arr + 1 → 前进一个完整的行（4 个 int = 16 字节）。
• *(arr + 1) + 2 → 指向 arr[1][2]。

汇编 (x86‑64) 对于 arr[i][j]

; Assume:
;   RAX = base address of arr
;   RBX = i
;   RCX = j
;   COLS = compile‑time constant

mov    rdx, rbx           ; rdx = i
imul   rdx, COLS          ; rdx = i * COLS
add    rdx, rcx           ; rdx = i * COLS + j
shl    rdx, 2             ; rdx = (i*COLS + j) * 4   ; sizeof(int)=4
add    rdx, rax           ; rdx = base + offset
mov    eax, [rdx]         ; load arr[i][j]

现代编译器常用 LEA 把算术合并：

lea    rdx, [rbx + rbx*4]   ; rdx = i * 5   (if COLS = 5)
lea    rdx, [rdx*4 + rax]   ; combine scaling and base
mov    eax, [rdx + rcx*4]   ; load arr[i][j]

行主序 vs 列主序 遍历

行主序（在 C 中最优）：

int main(void) {
    int arr[2][3] = {
        {1, 2, 3},
        {4, 5, 6}
    };

    printf("Base address: %p\n", (void *)arr);

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            printf("arr[%d][%d] = %d at address %p\n",
                   i, j, arr[i][j], (void *)&arr[i][j]);
        }
    }

    /* Treat as a flat 1‑D array */
    int *flat = (int *)arr;
    printf("\nAs

> **Source:** ...

```c
flat array:\n");
    for (int k = 0; k < 6; ++k) {
        printf("flat[%d] = %d at address %p\n",
               k, flat[k], (void *)&flat[k]);
    }

    return 0;
}

示例输出

Base address: 0x7ffc8b3e1a40
arr[0][0] = 1 at address 0x7ffc8b3e1a40
arr[0][1] = 2 at address 0x7ffc8b3e1a44
arr[0][2] = 3 at address 0x7ffc8b3e1a48
arr[1][0] = 4 at address 0x7ffc8b3e1a4c
arr[1][1] = 5 at address 0x7ffc8b3e1a50
arr[1][2] = 6 at address 0x7ffc8b3e1a54

As flat array:
flat[0] = 1 at address 0x7ffc8b3e1a40
flat[1] = 2 at address 0x7ffc8b3e1a44
flat[2] = 3 at address 0x7ffc8b3e1a48
flat[3] = 4 at address 0x7ffc8b3e1a4c
flat[4] = 5 at address 0x7ffc8b3e1a50
flat[5] = 6 at address 0x7ffc8b3e1a54

请注意，地址会以 sizeof(int)（4 字节）为步长顺序递增，验证了行主序布局。

一维访问快捷方式

int rows = 3, cols = 4;
int *arr = malloc(rows * cols * sizeof(int));

/* Access arr[i][j] as a flat array */
int value = arr[i * cols + j];

动态二维数组分配

/* Separate rows – each row is its own allocation */
int **arr = malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    arr[i] = malloc(cols * sizeof(int));
}

/* Access naturally: arr[i][j] */

/* Contiguous block – one allocation for the whole matrix */
int **arr = malloc(rows * sizeof(int *));
arr[0] = malloc(rows * cols * sizeof(int));   /* one big chunk */
for (int i = 1; i < rows; i++) {
    arr[i] = arr[0] + i * cols;                /* point to the start of each row */
}

/* Cleanup */
free(arr[0]);   /* free the big data block */
free(arr);      /* free the array of row pointers */

内存布局与寻址

• 多维数组在内存中是 线性化 的。

• 行主序（C 语言的默认方式）意味着最右侧的索引变化最快。

• arr[i][j] 的地址计算公式为

  base_address + (i * COLS + j) * sizeof(element_type)

缓存、TLB 与访问模式

• 现代 CPU 采用分层缓存（L1、L2、L3）。顺序访问可以最大化缓存命中率。
• 缓存行 示例（64 字节）：
  • int = 4 字节 → 每行 16 个 int。
  • 访问 arr[0][0] 会把 arr[0][0] … arr[0][15] 加载到缓存中。
• TLB 缓存虚拟地址到物理地址的转换。跨距或随机访问可能导致 TLB 抖动。
• CPU 在检测到顺序模式时会预取后续缓存行。以 行主序（内部循环遍历列）的方式遍历矩阵，可让硬件高效预取。

关键要点

• 线性化：多维数组存储为单个连续块。
• 行主序：最右侧的索引变化最快。
• 地址公式：base + (i * COLS + j) * sizeof(type)。
• 遍历顺序很重要：按存储顺序迭代可获得最佳性能。
• 真数组 vs. 指针的指针：布局不同 → 取舍不同（连续性 vs. 灵活的行大小）。
• 编译器魔法：arr[i][j] 会自动转换为指针算术。
• 缓存局部性：顺序访问比随机访问快 10–100 倍。
• 理解这些底层细节可以帮助你：
  • 编写更快的代码，
  • 调试内存相关的错误，
  • 与硬件或其他语言进行清晰的接口。