性能优化——遍历图像的正确姿势

微信公众号：命运探知之魔眼

如有问题或建议，请后台留言，我会尽力解决你的问题。

前言

我是人工智障，一名程序猿。做过嵌入式、爬虫，目前在自学计算机视觉 。注册 「命运探知之魔眼」（名字取自影视作品「命运石之门」）这个公号已有些日子，真正有心将它运营起来是看到朋友狗哥运营它的公号

「一个优秀的废人」

之后。本「性能优化」系列是作为「计算机视觉」系列文章的拓展，主要分享一些代码优化和底层的知识。

任务描述

首先来看一项简单的任务：遍历一个矩阵，获取里面的值，但不需要做任何操作，只是读取。

矩阵是一个二维数组，或者在 Python 中是一个 numpy.array ，遍历这样的一个结构需要两层循环，沿着行方向和列方向的，但是循环的顺序有两种，乍一看似乎哪个在先哪个在后都没有关系，然而我会证明这两种顺序有很大的性能差异。

代码实现

我们分别给行优先访问和列优先访问定义两个函数。

行优先的意思是外层循环是沿行方向的，列优先则反之。

要对比两者的性能，我们定义了一个存放矩阵大小的 list ，让大小递增的矩阵分别用这两种方式访问，比较它们的运行时间。

下面是我使用的矩阵大小 list:

从 500 开始，以 1000 的步进值往 8000 递增。

然后来生成随机方阵，分别运行两种遍历方式：

row_major_time 和 col_major_time 存放了两种遍历方式对应不同矩阵大小的运行时间，把矩阵大小作为横轴，运行时间作为纵轴，我们画一个折线图，使用了 matplotlib 库，有兴趣可以自行查阅使用方法，不作过多介绍，画图的代码也贴在这里：

运行结果

Figure_1.png

可以看到随着矩阵大小增大，行优先跟列优先的运行时间产生了差异，行优先访问要比列优先快。

原因分析

要明白造成差异的原因，我们要了解 4 件事情。

一、内存的排列

内存对于操作系统是线性排列的，内存地址沿着一个方向增加，像数轴一样，如下图：

内存排列

二、图像在内存中的排列

图像是个二维数组，但内存的排列是一维的，因此图像在内存中实际是被展平成一维排列的，至于是沿着列方向还是行方向展，一般的实现都是沿着行方向展的，换句话说，申请图像的内存的时候是一行一行的申请的，numpy 和 C 语言中的 malloc 都是这样的。画图表示就是这样子的：

图像在内存中的排列

因此如果用行优先的方法访问的话，我们对于图像内存的访问是连续的，因为访问的方式跟内存申请的方式是一致的，好好比划一下。

三、高速缓存牛逼

高速缓存就是买电脑的时候看到 CPU 有个参数是 Cache 多少级多少 MB。高速缓存的作用跟内存类似，但是离 CPU 核非常的近，访问速度是内存的 5 ~ 10倍，造价也很高，程序在读取数据的时候总是先从 Cache 中查找有没有这项数据，才到主存中获取。因此，如果能让图像常驻或者部分常驻 Cache 的话，速度的提升是非常明显的。

四、高速缓存抓取数据的策略

Cache 的数据是从主存中拷贝过来的，Cache 对于我们存放的数据有个假设，就是认为短时间内对我们有用的数据，在内存上都是连续分布的。所以 Cache 并不是一个一个数据的从主存拷贝过来的，而是一片一片的拷。因此如果对你有用的数据真的是连续排布的，这样的策略就会大有裨益。正好，我们的图像就是这样的。

总结

现在看回运行结果的折线图，一开始两种访问方式的运行时间相差无几，是因为这时候的 Cache 还能容下整幅图，因此怎么访问速度都不会有太大的差异，到了后面图像越来越大，Cache 是不可能整个装下来的，差异就体现在哪种访问方式会提高缓存命中率了。

后语

我不是大神，不是什么牛人，于 性能优化 的领域我真的是新手，很多知识现学现卖，因此对于我的文章有什么纰漏或者疑问的，欢迎下方留言。