CPU与代码优化（2）：关于高速缓存命中问题的实验(Unity内)与研究

1，多级缓存结构

由于内存传输信号至CPU的速度过慢（相对于CPU的计算速度），目前在CPU与内存之间都存在着多级缓存（intel core i5和i7是3级缓存，L1,L2,L3），内存，缓存，CPU的结构关系大致如下。

(图1）
L1,L2为每核独享，L3为多核公用。

高速缓存中存储信息的主要单位是组（sets)，每组里有行（associative)，每行里存着固定大小的字节，既是数据块。数据块是各级缓存交换数据的基本单位（图3中的line size既是数据块的大小），每级缓存大小既是sets*assocatives*linesize。

（图2：intel core i5的一些缓存相关信息）

（图3：intel core i5的一些缓存相关信息）

组放置策略：

由于缓存大小是一个金字塔形递减的结构，下级缓存必须根据某个“放置策略”向上层传输数据块。 例如：

（图4：一个假象的Intel core i5的缓存放置策略）

行替换策略：

多级缓存之间传输的数据块是放在组的行中，数据块被定位到应存储的组的位置后，既要决定它所在的行。如图3，Intel Corei5 L1每组8行，L2 8行，L3 12行。

组与行的替换与寻找都有一个译码与寻址的过程，本文跳过此问题。以下测试并探讨几个缓存不命中的情况。

2，冷不命中

当某级缓存为空时，对任何数据的访问都不会命中。这种情况称为冷不命中(cold miss)。

实测：

由于缺乏用C#清除CPU缓存的方法，暂时无法测试。

3，一般不命中

int[,] L3_1 = new int[4, 786432]; //声明一个786432*4*4（数组内全是int随机数，）=12MB的数组，测试前先遍历此数组，将不相关的数据插入缓存，人为的造成之后测试中第一次遍历的缓存不命中。

......
        //为防止编译器优化，遍历此数组的方法将由实时输入触发
        if(Input.GetKeyDown(KeyCode.B)){

            int result = 0;
            for (int i = 0; i < 1; i++)
            {
                result += SumVec2_L1(L3_3);
            }
            UnityEngine.Debug.Log("L3_3:" + result);
        }

被测试数组：

    int[,] L1_2 = new int[768,1024];      //数组内全是int随机数，1024*768*4=3MB 正好是L3的大小。

遍历数组函数：

    //二维数组遍历相加
    public int SumVec2_L1(int[,] vec)
    {
        int i, sum = 0;
        int i_Boundary = vec.GetLength(0);
        int j_Boundary = vec.GetLength(1);

        for (i = 0; i < i_Boundary; i++)
        {
            for (int j = 0; j < j_Boundary; j++)
            {
                sum += vec[i,j];
            }
        }
        return sum;
    }

测试过程：

        //为了防止编译器进行优化，测试方法将会由实时输入触发
        if(Input.GetKeyDown(KeyCode.A)){
            //计时变量
            int pTime;
            int cTime;
            DateTime pTime_F;
            DateTime cTime_F;
            TimeSpan begin;
            TimeSpan end;
            //为防止编译器优化，遍历叠加结果将由Debug.log输出
            int result = 0;

            //第一次遍历前缓存中已经被插满不相关数据，因此测出的结果为全不命中的情况。
            pTime = System.Environment.TickCount;
            pTime_F = System.DateTime.UtcNow;
            begin = Process.GetCurrentProcess().TotalProcessorTime;
            for (int i = 0; i < 1; i++)
            {
                result += SumVec2_L1(L1_2);
            }
            cTime = System.Environment.TickCount;
            cTime_F = System.DateTime.UtcNow;
            end = Process.GetCurrentProcess().TotalProcessorTime;
            UnityEngine.Debug.Log("L1_1:Time:1-Process:" + (end - begin).TotalMilliseconds +".2-UtcNow:"+(cTime_F-pTime_F).TotalMilliseconds+".3-TickCount:"+(cTime - pTime)+ "{" + result + "}");
            result = 0;

            //第二次遍历前，会运行SumVec3_L1函数进行“热身”，SumVec3函数内容与SumVec2相同，只是会正好遍历至数组的256KB处为止，因此理论上来说第二次遍历时，L3，L2缓存内容为最优化状态，都缓存着相关数据
            for (int i = 0; i < 1; i++)
            {
                result += SumVec3_L1(L1_2);
            }
            UnityEngine.Debug.Log("warm" + result);
            result = 0;

            //第二次遍历前，L3缓存着L1_2内所有的int（理论上，如果其他进程/线程没有占用），L2缓存着0-128列的int
            pTime = System.Environment.TickCount;
            pTime_F = System.DateTime.UtcNow;
            begin = Process.GetCurrentProcess().TotalProcessorTime;
            for (int i = 0; i < 1; i++)
            {
                result += SumVec2_L1(L1_2);
            }

            cTime = System.Environment.TickCount;
            cTime_F = System.DateTime.UtcNow;
            end = Process.GetCurrentProcess().TotalProcessorTime;
            UnityEngine.Debug.Log("L1_1:Time:1-Process:" + (end - begin).TotalMilliseconds + ".2-UtcNow:" + (cTime_F - pTime_F).TotalMilliseconds + ".3-TickCount:" + (cTime - pTime) + "{" + result + "}");
            result = 0;

            //第三轮遍历前，同样进行热身 warm up
            for (int i = 0; i < 1; i++)
            {
                result += SumVec3_L1(L1_2);
            }
            UnityEngine.Debug.Log("warm" + result);
            result = 0;

            //第三轮遍历，L1，L2，L3缓存内内容应与第二次遍历前相同（理论上，如果L3没有被其他进程/线程使用）
            pTime = System.Environment.TickCount;
            pTime_F = System.DateTime.UtcNow;
            begin = Process.GetCurrentProcess().TotalProcessorTime;
            for (int i = 0; i < 1; i++)
            {
                result += SumVec2_L1(L1_2);
            }
            cTime = System.Environment.TickCount;
            cTime_F = System.DateTime.UtcNow;
            end = Process.GetCurrentProcess().TotalProcessorTime;
            UnityEngine.Debug.Log("L1_1:Time:1-Process:" + (end - begin).TotalMilliseconds + ".2-UtcNow:" + (cTime_F - pTime_F).TotalMilliseconds + ".3-TickCount:" + (cTime - pTime) + "{" + result + "}");
            result = 0;
        }
    }

因此，第一轮遍历速度应该是最慢的，第二，三轮遍历的时间应该相同。
测试结果:

（图5：测试结果）

结论：平均多次测试结果，第一次遍历相比第二，三次遍历慢0.1–0.3毫秒。

4，冲突不命中

根据图4的放置策略，这种映射规则里有一个关键的问题，既是下一级缓存里的有若干个位置的数据必须存在同一个位置的上级缓存中，例如L2高速缓存的组1，65，129，193，257，321，385，449，513内的数据必须存在L1的组1中，换句话说L1无法同时缓存这些组中的数据。当L1的组1被反复的读取，而其他组为相对闲置状态时，这种不命中称为冲突不命中(conflict miss)。

实测：

被测试数组：

    int[,] L1_M = new int[512, 128];//[8, 8192];      //根据L2大小设置的数组，L2 512组, 每组128个int，512B，正好等于8行*64B

测试函数：

    //高速缓存非友好版本，依次访问数组的0，64，128，192，256，320，384，448列，也既是L2的0，64，128，192，256，320，384，448组，这8组中的数据很有可能被放置策略限制而必须存在L1的同一组中。
    public int SumVec4_L1(int[,] vec)
    {
        int i, sum = 0;
        int i_Boundary = vec.GetLength(0);
        int j_Boundary = vec.GetLength(1);


        for (i = 0; i < i_Boundary; i += 64)
        {
            for (int j = 0; j < j_Boundary; j++)
            {
                sum += vec[i, j];
            }
        }

        return sum;
    }
    //高速缓存友好版本，依次访问数组/L2的0-7列/组。
    public int SumVec5_L1(int[,] vec)
    {
        int i, sum = 0;
        int i_Boundary = vec.GetLength(0);
        int j_Boundary = vec.GetLength(1);

        for (i = 0; i < 8; i += 1)
        {
            for (int j = 0; j < j_Boundary; j++)
            {
                sum += vec[i, j];
            }
        }

        return sum;
    }

（图6：根据函数模拟L1，L2映射关系（假想））

测试结果：

（图7：测试结果。第一轮遍历为SumVec4，第二轮为SumVec5。）

结论：高速缓存优化的遍历方式要比非友好版本快1倍左右。

5，容量不命中

比较好理解，就是反复被访问的数据集过大，超过了缓存大小

被测试数组：

    int[,] L1_M = new int[512, 128];//一个等于L2大小的数组
    int[,] L1_L = new int[1024, 128];//一个等于L2两倍大小的数组

测试函数:

    //对等于L2大小的数组更新随机数遍历叠加并重复200次
    public int SumVec6_L1(int[,] vec)
    {
        int i, sum = 0;
        int j = 0;
        int i_Boundary = vec.GetLength(0);
        int j_Boundary = vec.GetLength(1);

        for (int i2 = 0; i2 < 200; i2++)
        {
        //为防止编译器优化进行随机数更新
            for (i = 0; i < i_Boundary; i++)
            {
                for (j = 0; j < j_Boundary; j++)
                {
                    vec[i, j] = UnityEngine.Random.Range(1, 5);
                }
            }

            for (i = 0; i < i_Boundary; i += 1)
            {
                for (j = 0; j < j_Boundary; j++)
                {
                    sum += vec[i, j];
                }
            }
        }

        return sum;
    }
    //对等于L2大小两倍的数组更新随机数遍历叠加并重复100次
    public int SumVec7_L1(int[,] vec)
    {
        int i, sum = 0;
        int j = 0;
        int i_Boundary = vec.GetLength(0);
        int j_Boundary = vec.GetLength(1);

        for (int i2 = 0; i2 < 100; i2++)
        {
        //为防止编译器优化进行随机数更新
            for (i = 0; i < i_Boundary; i++)
            {
                for (j = 0; j < j_Boundary; j++)
                {
                    vec[i, j] = UnityEngine.Random.Range(1, 5);
                }
            }

            for (i = 0; i < i_Boundary; i += 1)
            {
                for (j = 0; j < j_Boundary; j++)
                {
                    sum += vec[i, j];
                }
            }
        }

        return sum;
    }

以上，两个函数进行了同等数量的叠加操作。从L2，L3之间的数据块传递角度来看。SumVec6中L3向L2进行了512次数据块传递， SumVec7中则是512*10=5120次数据块传递。
测试结果：

（图8:测试结果。第一轮遍历时间为SumVec6，第二轮为SumVec7）

结论：那么，结合理论与实测结果，5120-512=4608次L3向L2传递数据块的时间，既是容量不命中的惩罚，约为2~10毫秒。

6，总结

如何避免缓存不命中以提高程序局部的运行速度：
1，一般不命中/冷不命中
可以通过缓存预热进行适当优化，根据本机各级缓存大小预先对关键数据进行读操作，将其插入缓存中。
2，冲突不命中
在循环中尽量以1为步长对数据进行遍历，尽量避免以等距且跨度大（特别是2^n）的步长对数据进行遍历。
3，容量不命中
对于大型数据，可根据本机L3缓存大小，对需遍历数据进行分段处理，每次L3同等大小数据，减少L3向内存调数据块的次数。对于循环量比较大，优化需求更高的情况，可根据L2，L1大小对需遍历数据进行分段处理，减少各级缓存调用数据块的次数。

————————————————————————————————————
参考：
深入理解计算机系统—Randal E.Bryant, David R.O’Hallaron

维护日志：