C++ 多维数组 - 夜羽的小作坊

多维数组是 C++ 里最容易被”误解”的东西之一。很多人用了好几年，却从没想过 int arr[3][4] 和 int** pp 到底有什么本质区别。搞 AI Infra 的话，这个问题直接关系到你写出来的矩阵乘法快不快、CUDA kernel 会不会 cache miss 爆炸。

今天把这件事彻底说清楚。

二维数组的本质#

先问一个问题：int arr[3][4] 在内存里是什么样的？

答案很简单：连续的 12 个 int。

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

这 12 个元素在内存里是紧挨着放的，行与行之间没有任何间隔。这就是 row-major（行主序），C 和 C++ 都遵循这个约定。

arr[i][j] 的地址计算：

1
address(arr[i][j]) = base + (i * 4 + j) * sizeof(int)

编译器在编译时就知道每行有 4 个元素，所以能算出正确的偏移。这一点非常关键——编译器需要知道列数，这也是为什么传二维数组给函数时必须指定列数。

指针与二维数组：`int (*p)[4]` vs `int**`#

这是最容易搞混的地方，也是面试常考点。

1
int arr[3][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12} };
2

3
// 正确：指向"长度为 4 的 int 数组"的指针
4
int (*p)[4] = arr;
5
// p[1][2] 等价于 arr[1][2]，地址计算完全一致
6

7
// 错误：int** 是指针的指针，和 arr 完全不是一回事
8
int** pp = arr;  // 编译报错或 UB

int (*p)[4] 的类型是”指向 int[4] 的指针”。p + 1 会跳过整整一行（16 字节），这和 arr 的内存布局完美匹配。

int** 是”指向 int* 的指针”。pp[0] 应该是一个 int*，但 arr[0] 其实是 {1, 2, 3, 4}——这里存的是 int 数据，不是指针。所以 pp[0] 会把那 4 个 int 的原始字节解释成一个地址，然后去解引用，直接 segfault。

函数参数传二维数组：

1
// 这两种写法完全等价
2
void process(int arr[][4], int rows);
3
void process(int (*arr)[4], int rows);
4

5
// 调用
6
process(arr, 3);

列数 4 必须写死，因为编译器要用它来计算行偏移。如果列数是运行时确定的，就需要换一种方式。

动态二维数组的三种姿势#

姿势一：`int**`——能用，但别用#

1
int rows = 3, cols = 4;
2

3
int** arr = new int*[rows];
4
for (int i = 0; i < rows; i++) {
5
    arr[i] = new int[cols];
6
}
7

8
// 使用
9
arr[1][2] = 42;
10

11
// 释放（容易忘）
12
for (int i = 0; i < rows; i++) {
13
    delete[] arr[i];
14
}
15
delete[] arr;

内存布局：

1
arr ──► [ptr0] [ptr1] [ptr2]
2
           │      │      │
3
           ▼      ▼      ▼
4
         [行0]  [行1]  [行2]

每行都是独立分配的，在内存里可能相差几百 KB。每次访问 arr[i][j] 需要两次解引用：先读指针 arr[i]，再读数据 arr[i][j]。对 cache 来说是灾难。

姿势二：`vector<vector<int>>`——方便，但同样不连续#

1
std::vector<std::vector<int>> arr(rows, std::vector<int>(cols, 0));
2

3
arr[1][2] = 42;  // 语法很友好

内存同样不连续，每个内层 vector 独立在堆上分配。在矩阵运算场景下，性能问题和 int** 一样。

姿势三：一维数组模拟——推荐，性能最好#

1
std::vector<int> arr(rows * cols, 0);
2

3
// 访问 [i][j]
4
arr[i * cols + j] = 42;
5

6
// 封装成 lambda 更易用
7
auto at = [&](int i, int j) -> int& {
8
    return arr[i * cols + j];
9
};
10
at(1, 2) = 42;

内存完全连续，12 个 int 紧挨着放，和 int arr[3][4] 的布局完全一样。这是在 AI Infra 里处理矩阵的标准做法。

Row-major vs Column-major#

C/C++ 用行主序（row-major）：元素按行存储，同一行的元素在内存里相邻。

Fortran、MATLAB、NumPy 默认用列主序（column-major）：元素按列存储，同一列的元素在内存里相邻。

用 3×3 矩阵举例：

1
逻辑矩阵：
2
| 1  2  3 |
3
| 4  5  6 |
4
| 7  8  9 |
5

6
Row-major（C/C++）内存：1 2 3 4 5 6 7 8 9
7
Col-major（Fortran）内存：1 4 7 2 5 8 3 6 9

这个差异在矩阵乘法里会造成巨大的性能差异。

Cache 友好性：行主序的代价#

现代 CPU 的 cache line 通常是 64 字节，也就是一次能加载 16 个 int。当你访问 arr[i][j] 时，CPU 会把 arr[i][j] 附近的元素一起加到 cache 里。

对于行主序的数组，哪种遍历方式快？

1
// 按行遍历：cache 友好
2
// 每次访问的元素和上一次相邻，cache hit 率极高
3
for (int i = 0; i < N; i++) {
4
    for (int j = 0; j < N; j++) {
5
        sum += arr[i * N + j];  // 顺序访问内存
6
    }
7
}
8

9
// 按列遍历：cache 不友好
10
// 每次访问跳过整整一行（N * sizeof(int) 字节）
11
for (int j = 0; j < N; j++) {
12
    for (int i = 0; i < N; i++) {
13
        sum += arr[i * N + j];  // 每次跳 N 个元素
14
    }
15
}

实测对比（N = 4096，int 矩阵，约 64MB）：

1
#include <vector>
2
#include <chrono>
3
#include <iostream>
4
#include <numeric>
5

6
int main() {
7
    const int N = 4096;
8
    std::vector<int> arr(N * N);
9
    std::iota(arr.begin(), arr.end(), 0);
10

11
    volatile long long sum = 0;
12

13
    // 行遍历
14
    auto t0 = std::chrono::high_resolution_clock::now();
15
    for (int i = 0; i < N; i++)
16
        for (int j = 0; j < N; j++)
17
            sum += arr[i * N + j];
18
    auto t1 = std::chrono::high_resolution_clock::now();
19

20
    // 列遍历
21
    sum = 0;
22
    auto t2 = std::chrono::high_resolution_clock::now();
23
    for (int j = 0; j < N; j++)
24
        for (int i = 0; i < N; i++)
25
            sum += arr[i * N + j];
26
    auto t3 = std::chrono::high_resolution_clock::now();
27

28
    auto row_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count();
29
    auto col_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();
30

31
    std::cout << "Row-major traversal: " << row_ms << " ms\n";
32
    std::cout << "Col-major traversal: " << col_ms << " ms\n";
33
    std::cout << "Slowdown: " << (float)col_ms / row_ms << "x\n";
34

35
    return 0;
36
}

典型结果：列遍历比行遍历慢 5x 到 20x，具体取决于矩阵大小和 CPU cache 大小。当矩阵大到装不进 L3 cache 时，差距最为明显。

矩阵转置的 Cache 问题#

朴素转置：

1
// 朴素实现：O(n²) 操作，但 cache 行为很差
2
void naive_transpose(float* A, float* B, int N) {
3
    for (int i = 0; i < N; i++)
4
        for (int j = 0; j < N; j++)
5
            B[j * N + i] = A[i * N + j];  // 写 B 时列跳跃
6
}

问题在于：读 A 是行主序（友好），写 B 是列跳跃（不友好）。每次写 B[j * N + i]，j 在变，步长是 N，远超一个 cache line。

分块转置（Tiled Transpose）：

1
// 分块转置：每次处理 TILE×TILE 的小块，局部性好
2
void tiled_transpose(float* A, float* B, int N, int TILE = 32) {
3
    for (int i = 0; i < N; i += TILE) {
4
        for (int j = 0; j < N; j += TILE) {
5
            // 处理当前块
6
            int imax = std::min(i + TILE, N);
7
            int jmax = std::min(j + TILE, N);
8
            for (int ii = i; ii < imax; ii++) {
9
                for (int jj = j; jj < jmax; jj++) {
10
                    B[jj * N + ii] = A[ii * N + jj];
11
                }
12
            }
13
        }
14
    }
15
}

TILE 大小通常选 32 或 64，使得一个块正好能装进 L1 cache。在这个尺度上，读 A 和写 B 的访问都局限在一个小区域里，cache miss 大幅减少。

这个技巧在 CUDA 里几乎是必学内容，因为 GPU 的 shared memory 就是用来做这种 tiling 的。

GEMM 的访问模式#

矩阵乘法 C = A × B，朴素实现：

1
void gemm_naive(float* A, float* B, float* C, int M, int N, int K) {
2
    for (int i = 0; i < M; i++) {         // C 的行
3
        for (int j = 0; j < N; j++) {     // C 的列
4
            float sum = 0.0f;
5
            for (int k = 0; k < K; k++) { // 内积
6
                sum += A[i * K + k] *     // A 按行访问：友好
7
                       B[k * N + j];      // B 按列访问：不友好！
8
            }
9
            C[i * N + j] = sum;
10
        }
11
    }
12
}

最内层循环里，A[i * K + k] 随 k 增加步长为 1（行主序，友好），而 B[k * N + j] 随 k 增加步长为 N（列方向，不友好）。这就是朴素 GEMM 慢的根本原因之一。

解决方案之一：预先转置 B：

1
void gemm_with_transpose(float* A, float* B, float* C, int M, int N, int K) {
2
    // 先转置 B，得到 B^T，shape 是 N×K
3
    std::vector<float> BT(N * K);
4
    for (int k = 0; k < K; k++)
5
        for (int j = 0; j < N; j++)
6
            BT[j * K + k] = B[k * N + j];
7

8
    // 现在用 BT[j * K + k] 访问，随 k 步长为 1，cache 友好
9
    for (int i = 0; i < M; i++) {
10
        for (int j = 0; j < N; j++) {
11
            float sum = 0.0f;
12
            for (int k = 0; k < K; k++) {
13
                sum += A[i * K + k] * BT[j * K + k];  // 两个都友好
14
            }
15
            C[i * N + j] = sum;
16
        }
17
    }
18
}

实际的高性能 GEMM（比如 OpenBLAS、cuBLAS）用的是更复杂的 tiling 策略，同时对 A 和 B 做分块，配合向量化指令和寄存器复用，才能达到接近理论峰值的性能。

CUDA 中的矩阵#

在 GPU 上，这个问题更加复杂，因为 GPU 的内存访问有 coalescing 要求：同一个 warp 里的 32 个线程最好同时访问连续的内存地址，否则会触发多次内存事务，带宽利用率暴跌。

cuBLAS 的列主序约定#

cuBLAS 是 Fortran legacy 的产物，默认使用列主序。如果你的矩阵是行主序的，有两种处理方式：

1
// 方式一：利用转置等价关系
2
// C = A × B  (row-major)
3
// 等价于：C^T = B^T × A^T  (col-major)
4
// 所以把 A 当成 B^T，把 B 当成 A^T 传给 cuBLAS 即可
5
cublasSgemm(handle,
6
    CUBLAS_OP_N, CUBLAS_OP_N,
7
    N, M, K,        // 注意维度顺序也要交换
8
    &alpha,
9
    d_B, N,         // B 当 A^T 用
10
    d_A, K,         // A 当 B^T 用
11
    &beta,
12
    d_C, N);

这个技巧初看反直觉，但数学上完全等价。

CUDA 内核中的二维矩阵访问#

在自己写的 kernel 里，通常用一维数组配合行偏移：

1
__global__ void matmul_kernel(float* A, float* B, float* C,
2
                               int M, int N, int K) {
3
    int row = blockIdx.y * blockDim.y + threadIdx.y;
4
    int col = blockIdx.x * blockDim.x + threadIdx.x;
5

6
    if (row < M && col < N) {
7
        float sum = 0.0f;
8
        for (int k = 0; k < K; k++) {
9
            // A[row][k]：同一 warp 的线程 row 相同，k 相同，访问同一元素
10
            // 这里没有 coalescing，因为线程按 col 分布
11
            sum += A[row * K + k] * B[k * N + col];
12
        }
13
        C[row * N + col] = sum;
14
    }
15
}

上面这个实现写 C 时是 coalesced 的（同一 warp 里 col 连续），但读 A 时每个线程读同一行不同 k，不同线程读不同行，也不太 coalesced。实际的优化需要用 shared memory 做 tiling，这是 CUDA 矩阵乘法的标准套路。

`cudaMallocPitch`：对齐问题#

GPU 对内存地址有对齐要求。cudaMallocPitch 会在每行末尾添加 padding，使得每行的起始地址满足对齐要求：

1
float* d_A;
2
size_t pitch;  // 实际的行字节数（包含 padding）
3
cudaMallocPitch(&d_A, &pitch, cols * sizeof(float), rows);
4

5
// 访问 [i][j]
6
float* row_ptr = (float*)((char*)d_A + i * pitch);
7
float val = row_ptr[j];

pitch 通常是 512 字节的倍数。代价是内存浪费，收益是每行都对齐，global memory 访问效率更高。

总结#

几个核心结论：

int arr[3][4] 是连续内存，行主序；int** 是指针的指针，两者完全不同，不能互换。
动态二维数组优先用一维数组模拟（vector<int> + i * cols + j），保证内存连续。
行主序下，按行遍历是 cache 友好的；按列遍历会大量 cache miss，实测慢 5-20x。
矩阵乘法的内层循环对 B 的访问是列方向的，这是朴素 GEMM 性能差的根源；高性能实现通过转置或 tiling 解决。
cuBLAS 是列主序，利用 C = A×B 等价于 C^T = B^T × A^T 可以避免显式转置。
CUDA kernel 里，coalescing 要求同 warp 的线程访问连续内存，矩阵乘法的优化必须配合 shared memory tiling。

内存布局不是底层细节，是性能的核心。在 AI Infra 里，一个错误的遍历顺序可能让你的矩阵乘法慢十倍，而这十倍不是算法问题，纯粹是内存访问模式的问题。