Question

0x08-C语言效率(下)

注：存储器山就是对于不同步长不同大小文件的读取速率的三维坐标图，形似一座山，z轴为速率，x轴为步长，y轴为文件大小（字节），某些主流的测评软件便是这个原理(将存储器山的图像进行一下简单的变换，就能得到哪些软件呈现的效果图像)。

上文提到过，任何一点小改动，都有可能让程序的性能发生很大的变动，这是为什么？

当时我们并未深究，由于我们惯性的认为计算机的运作方式和人类的运作方式一致，也在过往的经验中认为计算机一定是在任何方面超越人类的存在，但是实际上，计算机除了在重复计算方面比人类的速度要快速以外，其他方面远远落后于人类的大脑，即便是我们最稀疏平常的视觉识别(看东西识别物体)，在计算机看来都是一门极其高深的领域，所以我们现在的时代的计算机还处于起步状态，在这种时代里，程序员的作用是无可替代的，同样程序员的一举一动关乎计算机的命运。

可能在很多的方面，都已经接触了一台计算机的主要组成构造，和程序员最息息相关的便是CPU，主存以及硬盘了，可能到现在为止很多程序员仍然认为编程序和这些存储器有什么关系？然而一个程序员，特别是编写C语言程序的程序员，最大的影响因素便来自于此，在计算机的存储器结构中，分为四种层次:
CPU寄存器 高速缓存器 主存 硬盘

但是有没有想过，为什么计算机存储器系统要分成这四层结构呢？我们知道，上述四种存储器的读写速度依次降低，我们为什么不选择一种速度中庸的，价格也中庸的材料，制造所有层次的存储器呢？

• 有人给出的解释是，一个编写良好的程序总是倾向于访问层次更高的存储器，而对于现在的技术，价格高昂而无法大量制造的高速存储器来说，我们可以选择按层次分配构造，让我们以最低的成本的存储器达到使用最高的速度存储器的效果。
• 就像是在自己的计算机上，当我们打开一个很笨重的应用程序后，会发现，下一次再打开的时候可能会更快，就像以前历史遗留的一个问题 Visual Studio 2008 在 Windows XP 上，第一次打开总是十分卡顿，但是当关闭程序之后第二次打开却是很流畅。在参考书中，提到过两个评价程序速度的关键点：时间局部性和空间局部性 。
  • 时间局部性：在访问过某块存储器之后的不久的将来，很可能会再次访问它
  • 空间局部性：在访问过某块存储器之后的不就的将来，很可能访问其邻近的存储器位置。
  • 良好的局部性改进一般能很好的提升程序的性能。
• 所谓局部性就是当我们使用过某些资源后，这些资源总是以一种形式存储在更高级更方便的存储器当中，让最近一次的存取请求能够更加有效率的进行。
  • 打个不太贴切的比喻，假设计算机是一个家，CPU是一个人，想象一下这个家中的所有物品都是井然有序的，这个人想要工作必然会需要工作物品，所以他需要从某些地方拿来，用完以后再放回去，这些地方就是存储器，但是过了一段时间发现这么做太浪费时间，有时候某些东西太远了，所以，人想把它把它放在离自己更进的地方，这样自己的效率就高很多，如果这个东西一段时间内不再用，则把它放回原处，留出位置给更需要的工作物品，于是形成了越常使用的物品离人越近的现象。这便是计算机存储器的分层结构的意义。
  • 而对于一个有良好局部性的程序而言，我们总能在离自己最近的地方找到我们所需要的数据，回到计算机：我们知道计算机的存储器是分层结构的，即每一层对应着不同的读写速度等级(CPU寄存器 > 高速缓存 > 主存 > 硬盘)，而我们的程序总是按照从左至右的顺序依次查找，每次找到一个所需要数据，不出意外，总是将其移动到上一层次的存储器中存储，以便下次更高速的访问，我们称这种行为叫做 命中 。越好的程序，越能将当时所需的数据放在越靠近左边的地方。这便是局部性的意义所在。
  • 当然，存储器如此分层也是出于无奈，在处理器的速度和存储器的速度实在差距的情况下只有如此做才能让处理器更加充分的利用，而不至于等待存储器读写而空闲，也许某一天，当内存的位价和普通硬盘不相上下或者差距不多的时候，也许内存就是硬盘了。而当今也有人使用某些特殊的软件在实现这个功能，凭着自己计算机上大容量的内存，分割出来当作硬盘使用，存取速度让硬盘望尘莫及。

局部性

前方提到了局部性，局部性体现在了，当步长越大，空间局部性越低，大多数情况下会造成性能降低，比如最常见的多维数组循环(我鲜少使用多维数组的原因之一便在于此)，前面说过多维数组实际上只是数个一维数组的包装而已，C语言中并没有真正的多维数组，而是将其解读成内存中的一维的连续内存，但是当我们遍历它的时候，C语言为了不让我们被底层实现所困扰，所以生成了多维数组遍历的假象：

让我们重温一遍"多维数组"：

#include <stdio.h>    
int main(void)
{
    int dim_1_arr[4]    = {1, 2, 3, 4};
    int dim_2_arr[2][2] = { {1, 2}, {3, 4} };
    int result_1 = 0;
    int result_2 = 0;

    for(int i = 0;i < 4;++i)
        result_1 += dim_1_arr[i];
    return 0;
}

此例中，对一维数组进行步长为 1 遍历求和，假设内存中数组的起始位置是 0

0 => 4 => 8 => 12

for(int j = 0;j < 3;++j){
    for(int i = 0;i < 3;++i){
        result_2 += dim_2_arr[i][j];
    }
}

此例中，我们的步长是多少呢？我们来看一下

0 => 8 => 4 => 12

可以很清晰的看出两段不同代码之间的跳跃，为什么？观察到多维数组的遍历中我们和平时的做法有些不同，是先对i进行遍历，再对j进行遍历，这就导致了程序必须在内存块中无规律的跳动，这里的无规律是计算机认为的无规律，虽然在我们看来的确是有迹可寻，优秀的编译器能够对它进行优化处理。就事论事，即这段程序的空间局部性比较差，对于一个在内存中大幅度跳跃，无规律跳跃的程序都将影响程序的性能。这个判定对于一个连续的内存块来说是很重要的，比如C语言中的结构体。

实际上C语言也是能够面向对象的，但是十分复杂，就像拿着棒子织衣服一样。而C语言的机构体能够让我们在一定程度上初步理解对象这个概念，因为它是一个完整的个体，虽然对外界毫不设防。

对于结构体

#define VECTOR 4
typedef struct{
        double salary;
        int    index[4];
}test_data;

int main(void)
{
    int result_1 = 0;
    int result_2 = 0;
    test_data dim_1_arr[VECTOR];
    /* ...填充数据 */

    for(int i = 0;i < VECTOR;++i)
    {    
        for(int j = 0;j < 4;++j)
            result_1 += dim_1_arr[i].index[j];
    }/* for loop 1 */

    for(int j = 0;j < 4;++j)
    {
        for(int i = 0;i < VECTOR;++i)
            result_2 += dim_1_arr[i].index[j];
    }/* for loop 2 */
    return 0;
}    

还是和上方一样，假设 dim_1_arr 起始位置为 0

for loop 1：

8 => 12 => 16 => 20 ==> 32 => 36 => 40 => 44 ==> ...

for loop 2：

8 => 32 => 56 => 80 ==> 12 => 36 => 60 => 84 ==> ...

从上方不完整的比较来看，loop 1 相对于 loop 2 来说有更好的空间局部性，很明显在 loop 2 中，CPU读取是在无规律的内存位置跳跃，而 loop 1 则是以单调递增的趋势向前(这里的向前指的是直观上的向前)读取内存。

• 在此处回顾一下C语言的结构体性质与知识：
  • 对于任意一个完整定义的结构体，每一个对象所占有的内存大小都符合内存对齐的规则。
  • 对于结构体内的各个成员而言，其相对于对象存储地址起始的距离，称为偏移量。

• 解释：

  • 内存对齐便是对于一个结构体而言，其所占内存大小总是最大成员的整数倍，其中最大成员指的是最基本成员，即：

      typedef struct{
          test_data test_1;
          int       test_2;
      }test_data_2;
    
      /*...*/
      printf("The size of test_data_2 = %d\n",sizeof(test_data_2));
      /*...*/
    

    输出： The size of test_data_2 = 32

      typedef struct{
              int index[4];
              int store_1;
              int store_2;
      }test_data_3;
      typedef struct{
              test_data_3 test_3;
              int         test_4;
      }test_data_4;
    
      /*...*/
      printf("The size of test_data_4 = %d\n",sizeof(test_data_4));
      /*...*/
    

    输出： The size of test_data_2 = 28

    仔细对比test_data_3与test_data的差异，可以发现不同处，在前者的内部包含了一个double类型的成员，在我的机器上它的长度为 8 ，后者的内部包含了两个int类型的成员，每个长度为 4，但是他们的长度在直观上是一样的！但是真正在使用的时候我们才能察觉到其中的差异，这就是我所说的最基本成员的意义所在。虽然我们在使用结构体的时候，能够将其当作一个整体，但是实际上他们与内建(build-in)的类型还是有一些差异的。

  • 偏移量通俗地说，就是该成员起始地址距离起始位置的长度，在结构体中，C语言是怎么为结构体分配设定大小的呢？除了内存对齐外，还需要考虑定义结构体时，其中成员的声明顺序，换句话说，谁首先声明，谁的位置就靠前。而某个成员的偏移量代表着其起始位置减去其所属对象的起始位置，(此处需要注意的是，两个毫不相干的指针相减所得到的结果是无意义的，只有当两个指针同在一个作用域内时，减法才是有意义的，为了避免潜在的错误，我们要谨慎使用指针减法操作)。

• 就此回过头去再看看上方的 loop 解释，应该能够理解到，那些数字是通过偏移量来进行计算得到的。

• 之所以没有详细的介绍时间局部性是因为，对于时间局部性而言，其最大的影响因素便是操作区域的大小，比如我们操作的数组或者文件的大小，越小时间局部性越好，试想一下对于一个小的文件和大的文件，我们更容易操作到同一块地方多次的，必定是小的文件。而操作文件的大小有时候并不能很好得成为我们的操作因素，故只能多关注空间局部性。

高速缓存器

1. 在前方提到了，一般情况下，局部性好的程序能够让程序比局部性差的程序更有效率，而对于局部变量而言，一个好的编译器总是尽可能的将之优化，使其能充分使用CPU寄存器,那么寄存器的下方,也就是速度最接近寄存器的,便是所谓的高速缓存器了，对于高速缓存器而言，其最大的功效便是缓冲，缓冲有两层意思：

   • 缓存数据，使下一次需要的数据尽可能的“靠近”CPU，此处的靠近并不是物理意义上的距离靠近。
   • 缓冲一下CPU于存储器巨大的速度差距，防止CPU空闲浪费。

2. 对于现在的计算机而言，CPU基本都是三层缓存：一级缓存(L1),二级缓存(L2),三级缓存(L3)，可以通过 CPU-Z(Windows) / Mac OS系统报告 来查看自己的CPU缓存，在软件中我们能够看到，在一级缓存中会分为两个部分 ：一级数据，一级指令，这代表着只读写数据，只读写指令，这样分开的意义在于处理器能够同时处理一个数据和一个指令，上述所说的都是对于一个CPU核而言的，也就是说当CPU是多核的时候，那就有多个这种“功能集合(L1+L2)”。二级缓存则与一级缓存同在一个核中，每个核都拥有自己的二级缓存，最后所有核共享唯一一个(L3)

   • 总的来说，对于高速缓存器来说，一般分为三层，第一层比较特殊由独立的两个部分组成，第二层第三层则是各自独立一体并未区分功能(既存数据又存指令)，而第一层和第二层则是每个核单独享有不同的缓存器，第三层则是各个核共享一个层，所以我们经常看见在个人计算机上，L3的大小经常是以MB为单位的，而第一层则多以KB甚至是Byte为单位。
   • 在实际中，喜欢研究计算机的人经常会在一些专业软件中看见自己的CPU配置，在缓存一栏的一级和二级中总能看见2 x 32 KBytes之类的参数，32代表的就是某级的缓存大小，而前方的2则是核数，即有几个核便有乘多少，和之前所说的一致，具体可参见下方的缓存器图示

1. 高速缓存器的各个层依然遵守逐步降速的规律，即读取周期 L1 < L2 < L3，而影响较大的便是上文提到的的命中率，我们知道越上层的高速缓存器总是将下层的存储器映射在自己的存储器中，而按照逻辑推断，上层的实际空间比下层的要小，因为上层的空间更加宝贵速度更快，这就导致我们无法将下层的空间一一对应的映射到上层里，那么我们就想到一个办法，并不是将下层存储器的内容完全映射到上层，而是上层有选择性的将下层的部分内容抽取到上层，这便是不命中之后的操作。

2. 对于CPU从存储器中读取数据这个操作，如果我们使用了高速缓存以及内存这两个概念，那么就会有一个延伸概念，命中。而对于这个概念只有两种情况，命中或者不命中。而对于一个初始化的高速缓存器，它一定是空的，也许在物理意义上它并不是空，但是实际上在程序看来它的确是空的，为了区分这个，高速缓存器专门使用了一个位(bit)来表示此组是否有效(即是否为空)，既然它是空的那么，我们第一次无论如何都无法命中数据，这时候该层的高速缓存器就会向下一层，在该层中寻找所要的数据，每次要向下一层申请寻找的行为一般称为惩罚，而当我们从存储器中将所需的数据加载到高速缓存器中的时候，我们便开始了运算，而一切关于高速缓存器效率的改进都集中在命中率的提升。

   • 假设有一个数组需要操作，由于数组是一个连续的内存空间，对其进行步长为1的操作拥有很好的空间局部性，那么可以当成一个很好的例子，在高速缓存器看来读取一个有n(n>N)个元素的数组vector并不是一次性读完，而是分次读取，如果读取了k次那么至少有k次不命中，这是不可避免的，而对于读取的数据也不一定是我们需要的，用书上的例子来说：
     vector:|[0]|[1]|[2]|[3]|[]|[]|[]|[]|[]|[]|[]|
     假设操作数组的每一个元素，我们一次读取三个内存的值，类型为int，因为原理都一样。那么在初始化时候，高速缓存器为空，在第一次操作的时候，读取了四个(如上所示)，此时一定经过了一次 不命中 。

     很好理解，因为缓存器空，所以第一次操作必然不命中，所以我们需要向下级存储器读取我们需要的数据，那么第二访问高速缓存的时候，可以命中vector[0]，依次命中后续两个，直到需要vector[4]，出现了不命中，那么我们就需要重复上一步，再次读取三个数据，依次类推直到结束。
     vector:|[0]|[1]|[2]|[3]|[4]|[5]|[6]|[7]|[]|[]|[]|

     现在我们能够从一定层面上解释为什么局部性好的程序比局部性差的程序要有更好的效率了，原因就在对于高速缓存器的利用，首先反复利用本地临时变量能够充分的调用高速缓存器的功能做到读写的最优化，其次步长为越小也越能尽最大的能力发挥高速缓存器读取的数据，在这点上再回过头思考多维数组的遍历并进行操作，如果没有考虑空间局部性(即先操作大块，再操作小块)，那么在高速缓存器中，它的不命中率令人发指，这也是操作不当效率低的原因。

   • 另一方面，对于不同步长而言，其影响的也是高速缓存器的命中率，还是上方的vector

       步长       | 1 | 2 | 3 | 4 | 5 |
       不命中/命中 |1/4|1/2|2/3|1/1|1/1|
     

     可以看出来，对于步长而言，当到了一定的上限以后，每次的请求都会不命中，那么这时候本层的高速缓存器相当于作废，时间全都耗费在下层数据传送到上层的时间，因为每次读取都是不命中，可以利用上方的例子自己试着推理一下。

   • 以上所说的每次读取下一级别存储器数据的时候，都是按照内存对齐，来读取的，如果你的内存数据，例如读取结构体时，没有放在内存对齐的位置(此处所说的内存对齐位置是以每次该级别存储器读取的大小为对齐倍数，而不是结构体在内存中存储时的内存对齐位置)，那么会将该位置的前后补齐倍数的起始位置来读取

       下一级别存储器     0 1 2 3 4 5 6 7 8 9 A B C D E F
       结构体数据存放位置在 4~F
       每次该级别的存储器读取 12个数据
       那么本次由于结构体存放的没有对齐到提取的内存位置，所有提取的可能会是 0~B
     

     也就意味着，并不是每次缓存读取都是如此的完美，恰好都从内存中数据的首部开始读取，而是整片根据内存倍数进行读取。

3. 在参考文献中提到了一种优化程序的技巧，便是充分的利用高速缓存器，并且不受缓存器大小的限制，做法是当所操作的数据过大的情况下，通过构造循环来创建一个有一个大块，这些块能够被高速缓存器容纳，那么我们就能够充分利用高速缓存器来实现功能。

缓存器示意图

----------------------------------------------
|  CPU某个核                                  |  ......其他核
| ----------  ----------  ------------------ | 
| |        |  |        |  |                | |  
| |   L1   |  |   L1   |  |   L2高速缓存器  | | 
| | 一级数据|  | 一级指令|   |    二级缓存器   | |
| ----------  ----------  ------------------ |
----------------------------------------------

------------------------------------------------------------------------------------
|                                                                                  |
|                                   L3高速缓存器                                    |
|                                    三级缓存器                                     |
------------------------------------------------------------------------------------

参考:[1]深入理解计算机系统--Randal E.Bryant / David O'Hallaro