调换循环顺序，矩阵乘法计算耗时从9.4秒降到4.4秒，看懂的人都牛

矩阵相乘是计算机科学中常见的任务之一，而对其进行高效的实现对于性能至关重要。在这篇文章中，我们将探讨如何使用C语言来实现矩阵相乘，并逐步通过优化手段提高其性能，运行时间从9.4秒降到4.4秒，这到底是怎么做到的呢？我们一起来看看！

目标

我们要用C语言实现矩阵的乘法计算，学过线性代数的朋友都知道其计算过程如下：

矩阵乘法计算

简单讲就是矩阵A的某一行各元素与矩阵B对应的列各元素相乘之后累加。

初始实现

那还不好实现吗？定义三个二维矩阵ABC,然后相乘累加就完了，C代码实现如下：

代码很简单，定义三个二维矩阵ABC，矩阵大小是800*800，可以看到二维矩阵算是比较大了。然后随机初始化AB矩阵，重点是中间那个三层for循环那段代码就是矩阵乘法计算过程。然后在这段代码前后使用gettimeofday函数记录计算前后时间，后面做时间差，得到矩阵计算过程的耗时。

编译运行一下代码，看看结果吧！

我们在ubuntu系统下面使用gcc编译，采用默认代码优化等级，可以看到这个矩阵运算

耗时用了9.47秒，耗时非常长，因为我的机器是虚拟机，配置很低，所以需要的时间很长,配置高机器肯定会快很多，但是本文讲的优化思路是通用的。

那么，能不能优化一下呢，缩减一下这个耗时？

改变for循环顺序

我们做个实验，改变一下三个for循环的顺序，把之前i,j,k改成i,k,j，代码如下：

修改for循环顺序

然后在同样的机器上采用同样的编译器编译，运行结果如下：

修改后运行结果

可以看到矩阵运算的耗时从之前的9.47秒到现在的4.46秒。好神奇啊，这是为什么呢？

剖析原因

下面我们来看看具体深层次原因吧。

Cache

如上图，我们知道，计算机CPU旁边是有缓存(Cache)存储介质，CPU每次从主内存(memory)读写数据的时候都会去看cache中是否已经有该数据，如果有就会直接从cache读写，因为Cache的速度远大于memory的速度，所以cache能大大提高数据读写效率。

• 如果CPU要读写的数据在Cache中不存在，那么就必须去下一级缓存或者主内存去读写，此时读写效率很低，这叫缓存未命中。

• 如果CPU要读写的数据在Cache中存在，那么就直接从cache中读写，读写效率大大提高，这叫缓存命中 。

对于C语言，对二维数组(矩阵)数据的存储是采取行优先存储原则 ，如下图：

行优先存储

如上图，也就是矩阵的每一行数据线性地存储在一行，线性排列的，这样的存储方式大大提高缓存命中率。

对于初始实现代码，我们for循环的顺序是i,j,k。那么在做矩阵乘法运算过程中关于ABC三个矩阵对内存的访问布局情况如下图：

i,j,k内存布局

因为外层循环是i和j,内层循环是k，那就相当于给定了i和j，变化的是k。

对于矩阵C而言，就是一直访问一个固定行与列的固定位置数据，这时对于矩阵C的访问效率是极高的。

对于矩阵A ,行不变，列在变化，而且是连续线性地，所以缓存局部性也非常好。

对于矩阵B，给定了列，但是行在变，因为是行优先存储，所以这一列数据成员在内存中是相距甚远的，缓存命中低，数据缓存利用率极低。就是这个矩阵B的访问导致效率极低。

改变for循环次序为i,k,j,那么在做矩阵乘法运算过程中关于ABC三个矩阵对内存的访问布局情况如下图：

i,k,j内存布局

因为外层循环是i和k,内层循环是j，那就相当于给定了i和k，变化的是j。

对于矩阵C而言，行不变，列在变化，而且是连续线性地，所以缓存局部性非常好。

对于矩阵A ,就是一直访问一个固定行与列的固定位置数据，这时对于矩阵A的访问效率是极高的。

对于矩阵B，给定了行，列在变化，而且是连续线性地，缓存局部性也非常好，所以效率也很高。

所以对ABC三个矩阵数据访问都效率很高，自然整个i，k，j顺序循环效率就很高，耗时就一下子降到4.46秒。

总结

在矩阵相乘的实现中，交换for循环的顺序可以提高性能的原因主要与矩阵的存储顺序有关。

在使用行优先存储的情况下，原始的实现中，for循环的顺序是 i->j->k，即按行迭代矩阵 A 的行、矩阵 B 的列，然后对每个元素进行累加。在行优先存储中，这种迭代方式可能导致缓存未命中，因为在内层循环中，矩阵 B 的列元素是相邻的，但在内存中存储位置可能相隔较远，导致缓存行频繁失效。

通过交换循环的顺序，即按照 i->k->j 的顺序迭代，可以更好地利用缓存。这是因为现在矩阵 B 的列元素在内层循环中是相邻的，这有助于提高缓存命中率，减少缓存未命中的影响，从而提高性能。

将矩阵的存储顺序与循环的迭代顺序相匹配，有助于更有效地使用硬件缓存，减少缓存未命中。这对于计算密集型任务，特别是涉及大型矩阵的任务，可以带来显著的性能提升。

当然，还有其他方式可以继续优化矩阵运算的性能，我们留到后续文章继续讲。

后续持续更新系列高质量文章，码字不易，欢迎关注、点赞、收藏以及提问。