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

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

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

前言

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

「一个优秀的废人」

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

任务描述

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

矩阵是一个二维数组,或者在 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 是不可能整个装下来的,差异就体现在哪种访问方式会提高缓存命中率了。

后语

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180725G14DZV00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券