感兴趣的可以移步我的知乎专栏:
用心做好工程 - 知乎 (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 进行测量,官方介绍如下:
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、所以,要是没有什么特殊缘故,建议正向遍历,最为稳妥