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

用心做好工程 - 知乎 (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在用芯片的缓存替换策略。目前假设其为黑盒，进行验证。

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

二、验证平台

软硬环境

测量方法

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，完全避免系统将全部数据替换到了缓存中。

单位微秒：

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

四、结论

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

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

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