13

在C语言程序中，为什么二维数组赋值的顺序会影响效率？

 4 years ago
source link: https://blog.popkx.com/%E5%9C%A8c%E8%AF%AD%E8%A8%80%E7%A8%8B%E5%BA%8F%E4%B8%AD-%E4%B8%BA%E4%BB%80%E4%B9%88%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E8%B5%8B%E5%80%BC%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%BC%9A%E5%BD%B1%E5%93%8D/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

在C语言程序中，为什么二维数组赋值的顺序会影响效率？

发表于 2019-08-27 20:08:55   |   已被 访问: 531 次   |   分类于:   C语言   |   暂无评论

学习C语言最有效的方法就是多做实验，很多初学者深知这一点。小明在学到二维数组时，尝试写了一段给二维数组赋值的代码，他发现一个奇怪的现象：交换赋值顺序，效率是不同的。请看下面这两段C语言代码：

int test1 ()
{
    int i,j;
    static int x[4000][4000];

    for (i = 0; i < 4000; i++) {
        for (j = 0; j < 4000; j++) {
            x[j][i] = i + j;
        }
    }

    return 0;
}

int test2 ()
{
    int i,j;
    static int x[4000][4000];

    for (j = 0; j < 4000; j++) {
        for (i = 0; i < 4000; i++) {
            x[j][i] = i + j;
        }
    }

    return 0;
}
48b8a399160065b85f0560a1d57b6371.png

这两个版本的C语言代码几乎完全相同，唯一的不同点在于交换了 i 和 j 变量，但是编译成C语言程序执行后，消耗的时间却是不同的，这是怎么回事呢？

可能有读者认为这两段C语言代码产生效率上的差异，是因为编译器处理这两段代码时，产生的指令不同。其实不是的，这两段“对称”的C语言代码产生的指令是一致的，请看：

499c22735b601b53752992fb4a792918.png

267ccd65d75974e795766dcb461d05b3.png

仔细对比 test1() 和 test2() 对应的指令，我们很难发现二者有什么不同。事实上，二者运行的效率差异主要来自于“缓存命中率”。简单来说，就是连续操作C语言中的多维数组的最后一个维度最快，因此 test1() 中的赋值操作几乎每次都会错过缓存，而 test2() 中的赋值操作缓存命中率更高一些，因此 test2() 执行所消耗的时间更少。

在很多C语言初学者的脑海里，二维数组各个元素在内存中的分布可能是下面这样的：

但是计算机中的内存地址始终是一维的，因此在计算机眼中，二维数组仍然是按照一维排列的：
c3fcd034ab194ec5c902fb173c2495ad.png
test2() 中的赋值操作先遍历第二维，这一过程是下图这样的：

ec3cec933154993058a34e6ff71eb596.png

此时C语言程序每次访问数组元素，在内存中都是顺序进行的，这对于缓存命中率的提升很有帮助。再来看 test1() 中的赋值操作，它优先遍历第一维，因此访问数组元素的过程是下图这样的：
a511019febf0d866f7c740f539747590.png

显然，此时C语言程序访问数组元素在内存中是“跳跃式”的，但是，计算机访问内存各个地址的效率不是都一样的吗？那为什么 test1() 和 test2() 的效率不同呢？

答案就是 test1() 和 test2() 的缓存命中率不同。计算机 CPU 一般都有更加高速的缓存（称为“缓存线（cache line）”，常是 64 字节），访问这一缓存的速度比访问内存的速度要高的多（读者可以对比想象计算机访问内存的速度比访问硬盘数据的速度快得多）。

小明的C语言代码中赋值的元素是 int 型的（常常是 4 字节），因此 64 字节的缓存线可以容纳 16 个连续的整数，CPU 访问这 16 个数据要比访问内存里的 16 个数据快得多，并且 CPU 在加载缓存线数据的时间内，处理相当多的工作。

CPU 在处理 test2() 中的赋值时，可以获取 16 个连续的整数块，然后赋值给数组，重复 4000*4000/16 次，这样的操作在缓存线的支持下相当快，因为 CPU 没有被闲置，总是在处理事务。

再考虑 test1() 中的赋值，缓存线加载了 16 个整数块，但是接着值修改了其中一个整数，因此它需要重复 4000*4000 次，相比于 test2() 中的赋值，需要 16 倍的内存“回迁”次数。而 CPU 实际上需要花时间坐着干等内存操作完成，因此 test1() 的效率要低一些。

本节主要讨论了一个看似“灵异”的C语言二维数组赋值问题，这无关指令差异，更多的是缓存命中差异带来的效率差异。但是读者应该明白，并不是所有的计算机程序都如此，例如 Fortran 语言中，test1() 中的赋值效率要高于 test2() 中的赋值效率，因为它将二维数组在内存中展开时，是按照“列”优先排列的（C语言是按“行”优先排列的）。

阅读更多:   C语言


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK