Java教程

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

本文主要是介绍正序/逆序遍历数组,速度有多大区别,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

用心做好工程 - 知乎 (zhihu.com)icon-default.png?t=LA92https://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正在上传…重新上传取消​icon-default.png?t=LA92https://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()正向/逆向
1196720940.9394
2178119180.9286
4174118630.9345
8168418020.9345
16171219570.8748
32162017120.9432
649329570.9739
1284374570.9562
2562412480.9718
5121801721.0465
10241541471.0476
204891901.0111
409655560.9821

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


四、结论

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

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

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

这篇关于正序/逆序遍历数组,速度有多大区别的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!