正序/逆序遍历数组,速度有多大区别

感兴趣的可以移步我的知乎专栏:

用心做好工程 - 知乎 (zhihu.com)正序/逆序遍历数组,速度有多大区别https://www.zhihu.com/column/c_1453489378207571968

一、问题背景

前几天遇到一个问题:遍历一个数组,正序或者逆序处理的速度有区别吗?具体来说,就是下面的两个函数 func1() 与 func2() 的速度一样吗?如果不一样,什么原因?

func1():

void func1(int * srcA, int * srcB, int * dst, int length)
{
    int i;
    for(i = 0; i < length; ++i)
    {
        dst[i] = srcA[i] * srcB[i];
    }
}

func2():

void func2(int * srcA, int * srcB, int * dst, int length)
{
    int i;
    for(i = length - 1; i >= 0; --i)
    {
        dst[i] = srcA[i] * srcB[i];
    }
}

刚开始想的是应该速度一样,只是写法习惯,但随即意识到由于缓存机制的存在,即局部性,应该正向func1()快点,引用《深入理解计算机系统》的阐释:

局部性通常有两种不同的形式:时间局部性(temporal locality)和空间局部性(spatial locality)。在一个具有良好时间局部性的程序中,被引用过一次的内存位置很可能在不远的将来再被多次引用。在一个具有良好空间局部性的程序中,如果一个内存位置被引用了一次,那么程序很可能在不远的将来引用 附近的一个内存位置。

可以先留意“附近”这两个字,后面会讲到,和自己预期的基本差不多。

二维数组的遍历问题同理,由于步长对缓存的影响,会对访问速度产生很大的影响。

具体相关概念网上有很多讲述的,本文不再赘述,我只对具体的差别数值感兴趣,特来验证分析。

有时间再研究下自己PC在用芯片的缓存替换策略。目前假设其为黑盒,进行验证。

避免系统性能振荡,用相对时间进行衡量。


二、验证平台

软硬环境

项目
编译器 MSVC
系统 Windows 10
芯片 Intel
内存 8GB
支持指令 CPUZ 实测支持 SSE、SSE2等
线程 单线程

测量方法

1、以微妙级别统计时间函数 QueryPerformanceCounter 进行测量,官方介绍如下:

QueryPerformanceCounter function - Win32 apps​docs.microsoft.com/zh-cn/windows/win32/api/profileapi/nf-profileapi-queryperformancecounter?redirectedfrom=MSDN正在上传…重新上传取消​正序/逆序遍历数组,速度有多大区别https://link.zhihu.com/?target=https%3A//docs.microsoft.com/zh-cn/windows/win32/api/profileapi/nf-profileapi-queryperformancecounter%3Fredirectedfrom%3DMSDN

2、每次循环 10000 次,取均值进行对比;

3、为了避免不同时间段测量引起的误差,每次取两者的比值进行对比,每次观察比值变化;


三、验证

具体的函数如下所示,缓存相关的处理,必须引入步长 stride 的影响

func1():

void func1(int * srcA, int * srcB, int * dst, int length, int stride)
{
    int i;
    for(i = 0; i < length; i+=stride)
    {
        dst[i] = srcA[i] * srcB[i];
    }
}

func2():

void func2(int * srcA, int * srcB, int * dst, int length, int stride)
{
    int i;
    for(i = length - 1; i >= 0; i-=stride)
    {
        dst[i] = srcA[i] * srcB[i];
    }
}

自己的PC只有两级缓存,一级数据缓存32KB,二级数据缓存4MB,令每个数组长度为1310720,大小即为5MB,完全避免系统将全部数据替换到了缓存中。

单位微秒:

stride 正向 func1() 逆向 func2() 正向/逆向
1 1967 2094 0.9394
2 1781 1918 0.9286
4 1741 1863 0.9345
8 1684 1802 0.9345
16 1712 1957 0.8748
32 1620 1712 0.9432
64 932 957 0.9739
128 437 457 0.9562
256 241 248 0.9718
512 180 172 1.0465
1024 154 147 1.0476
2048 91 90 1.0111
4096 55 56 0.9821

绘制趋势图,以相对速度比值为衡量基准,避免不同时间测量值的振荡:

正序/逆序遍历数组,速度有多大区别


四、结论

1、可以发现,当步长为256时,即每次为1KB,两者的速度几乎一致了,缓存没有为正向遍历带来优势;

2、当步长为16时,即64个字节,正向相比逆向最快,应该是缓存策略的影响;推荐了解下“存储器山”;

3、所以,要是没有什么特殊缘故,建议正向遍历,最为稳妥

上一篇:【原创】浅谈指针(六)字符串相关


下一篇:Android OpenCV(三十一,《Android面试题及解析》分享