为何二维C风格数组的矩阵乘法比一维std::array更快？

最近出于学习目的编写并优化线性代数相关代码，测试不同矩阵存储方式的差异。原本认为std::array和C风格数组的运行时性能应该几乎无差异，且mult1和mult2的时间复杂度也看不出明显区别，但实际运行结果差距极大：

测试代码：

#include <iostream>
#include <array>
#include <random>
#include <chrono>
using namespace std;
void setRandomValues(std::array<float, 10000>& arr1D) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0, 1);

    for (auto& element : arr1D) {
        element = static_cast<float>(dis(gen));
    }
}
void setRandomValues(float(&array)[100][100]) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0, 1);

    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            array[i][j] = static_cast<float>(dis(gen));
        }
    }
}
void mult1(array<float, 10000>& mat1, array<float, 10000>& mat2, array<float, 10000>& mat3)
{
    int rowsize = 100;
    for (size_t row = 0; row < 100; row++)
    {
        for (size_t col = 0; col < 100; col++)
        {
            float sum = 0;
            for (size_t k = 0; k < 100; k++)
            {
                int index1 = (row * rowsize) + k;
                int index2 = (k * rowsize) + col;
                sum += mat1[index1] * mat2[index2];
            }
            int index3 = (row * rowsize) + col;
            mat3[index3] = sum;
        }
    }
}
void mult2(float(&mat1)[100][100], float(&mat2)[100][100], float(&mat3)[100][100])
{
    for (size_t i = 0; i < 100; i++)
    {
        for (size_t x = 0; x < 100; x++)
        {
            float sum = 0;
            for (size_t k = 0; k < 100; k++)
            {
                sum += mat1[i][k] * mat2[k][x];
            }
            mat3[i][x] = sum;
        }
    }
}

int main()
{
    float mat1[100][100];
    float mat2[100][100];
    float mat3[100][100];
    std::array < float, 10000> mat4;
    std::array < float, 10000> mat5;
    std::array < float, 10000> mat6;
    setRandomValues(mat1);
    setRandomValues(mat2);
    setRandomValues(mat4);
    setRandomValues(mat5);

    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < 100000; i++)
    {
        mult1(mat4, mat5, mat6);
    }

    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);

    std::cout << "Using std::array in row major order " << duration.count() << std::endl;

    start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < 100000; i++)
    {
        mult2(mat1, mat2, mat3);
    }

    stop = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);

    std::cout << "Using C style nested array " << duration.count() << std::endl;

    return 0;

}

运行结果：

Using std::array in row-major order 711461
Using C style nested array 53742

核心问题分析 #

• 编译器优化力度差异：C风格二维数组float[100][100]携带明确的编译期维度信息，编译器能精准识别矩阵访问模式，进行常量折叠、循环展开、向量化等深度优化；而std::array<float,10000>是一维数组，手动计算的下标(k * rowsize) + col无法让编译器直接关联到矩阵列访问模式，优化空间被限制。

• 缓存局部性利用不足：mult1中mat2[index2]的访问是跨步式的——k每递增1，下标跳步100，属于非连续内存访问，会频繁触发缓存失效；而mult2的写法让编译器能自动识别这种低效访问，可能通过循环变换（比如调整循环顺序）提升缓存命中率，大幅减少缓存 miss 次数。

• 常量识别差异：mult1里的rowsize是局部变量，即使赋值为100，编译器默认不会将其视为编译期常量，导致下标计算中的乘法无法被完全优化；而mult2的数组维度是编译期常量，下标计算mat2[k][x]可直接优化为*(mat2 + k*100 + x)，乘法操作提前在编译期完成。

优化方案 #

1. 将mult1中的rowsize改为编译期常量：

   constexpr int rowsize = 100;
   

   让编译器能对下标计算做完全优化。

2. 调整mult1的循环顺序，优先访问连续内存：
   交换col和k的循环，把列遍历放到最内层，让内存访问变成连续模式，提升缓存命中率。

3. 开启最高等级编译器优化（如-O3）：
   默认优化等级下，不同数组类型的优化差异会被放大，开启-O3后，编译器会对两种写法做更均衡的深度优化，性能差距会明显缩小。

内容的提问来源于stack exchange，提问作者baguettio