问题起源

问题出自再看bilibili视频时候，（地址https://www.bilibili.com/video/BV12p4y1W7Dz），发现一道对于CPU问题从未思考过，所以就产生了趣味，具体问题是这样的：

上面两段代码fnc1和fnc2(这里我给简化了，成果都一样)，哪段的执行速度更快：

const N = 2000var arr2D [N][N]intfunc fnc1()  {  for i := 0; i < N; i++ {    for j := 0; j < N; j++ {      arr2D[i][j] = 0    }  }}func fnc2()  {  for i := 0; i < N; i++ {    for j := 0; j < N; j++ {      arr2D[j][i] = 0    }  }}

最终答案是fnc1要比fnc2快，这里我把他俩合并用一段代码调试下：

const N = 2000func main() {  //为了避免专用一个二维数组造成影响，这里用两个二维数组，每个办法别离用一个  var arr2D1 [N][N]int  var arr2D2 [N][N]int  //模仿fnc1  start1 := time.Now().UnixNano()  for i := 0; i < N; i++ {    for j := 0; j < N; j++ {      arr2D1[i][j] = 0    }  }  ct1 := time.Now().UnixNano() - start1  //模仿fnc2  start2 := time.Now().UnixNano()  for i := 0; i < N; i++ {    for j := 0; j < N; j++ {      arr2D2[j][i] = 0    }  }  ct2 := time.Now().UnixNano() - start2  //输入工夫  fmt.Println("fnc1 time :",ct1)  fmt.Println("fnc2 time :",ct2)}

输入后果绝大多数fnc1的工夫要小于fnc2的工夫，(偶然偶然会呈现fnc1大于fnc2，猜想起因是过后CPU忙于其余的过程)

$ go run main.gofnc1 time : 3499675fnc2 time : 10823762$ go run main.gofnc1 time : 3475027fnc2 time : 307537210......

过后纳闷这种景象是怎么造成的，毕竟两个办法的工夫复杂度都是雷同的。这就引出了明天的主题，CPU缓存。

CPU架构介绍

咱们在个别买电脑时候都是会先理解下内存(RAM)多大等信息，咱们还晓得Redis为什么快起因之一是基于内存的数据库。好像CPU就是在间接操作内存，内存就是最快的货色。然而对于比内存，还有比他快得多的存储介质，CPU高速缓存。

首先让咱们看下图计算机存储器的层次结构，图片取自《深刻了解计算机系统》。

所有的古代计算机都应用了这种存储构造，越凑近下面，造价越高，容量越小。古代计算机中，最快的就是寄存器存取了，寄存器间隔CPU外围最近，然而可存储数据起码，往往用来放一些函数参数；接下来别离是L1-L3三级缓存，也是明天的重点，他们作为CPU的缓存充当了CPU与主存之间的垫片；而后就是最相熟的主存，就是咱们常说的内存；再次就是磁盘和近程文件存储系统了。

接下来把视角拉近，次要看下CPU的存储架构，上面是一个通用的双核CPU架构图：

简要介绍下各个CPU部件：

管制单元(CU)：是CPU的指挥核心，他依据用户编译好的程序，从存储器中取出各种指令，用来指挥CPU工作

计算单元(ALU)：用于执行算术运算与逻辑运算，全副操作服从由管制单元指挥

寄存器：紧挨着管制单元与计算单元，速度是最快的，然而容量也是最小，32位CPU大多数寄存器能够存储4个字节,64位大多数为8字节。

L1-Cache：每个CPU都有一个L1-Cache，实际上L1-Cache又分为两个，一个指令缓存(i-cache)，一个数据缓存(d-cache)，这是因为两个缓存的更新策略不同，所以离开，通常L1-Cache大小在几十Kb到几百Kb之间，Linux下能够通过上面命令获取，一次拜访须要须要 2~4 个时钟周期。

# 数据缓存 d-cache$ cat /sys/devices/system/cpu/cpu0/cache/index0/size# 指令缓存 i-cache$ cat /sys/devices/system/cpu/cpu0/cache/index1/size

L2-Cache：每个CPU也有一个L2-Cache，大小要大于L1-Cache，因为地位比L1-Cache间隔CPU外围更远，所以速度稍慢于L1-Cache，须要10~20 个时钟周期。

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size

L3-Cache：L3-Cache是被所有CPU共享的，大小也更大，访问速度也稍慢与L2-cache，须要20~60 个时钟周期。

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size

CPU取数据过程

当CPU须要读取某些数据时候，如果寄存器中有，就间接用寄存器数据；如果没有，就去L1-cache中读取，L1-cache中没有，就去L2-cache，L2没有查问L3，L3没有去主存获取，获取到后顺次填充三级缓存。

CPU缓存上的数据就是主存上的数据，读取数据的规定并不是依照单个元素来读取，它是一块一块读取数据的，比方当我取出一个很小的数据时，他会把所在的那块内存块加载到缓存上。这样，当咱们拜访这个数据相邻的数据时候，也就能够间接通过CPU Cache来获取了，这样大小的内存块被称为Cache Line。在Linux上能够通过上面命令看到：

# cpu0的L1-d-cache的cache Line，我的机器是64字节$ cat /sys/devices/system/cpu/cpu0/cache/index1/coherency_line_size64

案例联合

咱们回到下面的案例，咱们首先定义了二维数组，在内存中的存储的间断形式是这样的：

var arr [2][2]int

在内存中是间断散布的，程序是 0_0, 0_1, 1_0, 1_1，每个元素占用8个字节

咱们能够通过取地址得出这个论断

func main() {  var arr [2][2]int  fmt.Println(uintptr(unsafe.Pointer(&arr[0][0])))  fmt.Println(uintptr(unsafe.Pointer(&arr[0][1])))  fmt.Println(uintptr(unsafe.Pointer(&arr[1][0])))  fmt.Println(uintptr(unsafe.Pointer(&arr[1][1])))}-----------//能够看到内存地址顺次加8824634298096824634298104824634298112824634298120

所以，对应到咱们的案例，当咱们应用i_j形式赋值时候，取出第一个元素0_0的时候，就会从内存中取出一块64字节的Cache Line，也就是取出了0_0到0_7放到了CPU缓存中，当下次迭代到0_1时候，就会间接应用CPU缓存中的数据，这充分利用了CPU缓存。

const N = 2000var arr2D [N][N]intfunc fnc1() {  for i := 0; i < N; i++ {    for j := 0; j < N; j++ {      arr2D[i][j] = 0    }  }}

然而当应用j_i形式赋值时候，第二次迭代要取用1_0的数据，这时候CPU要从新去主存加载数据到缓存，造成了CPU缓存穿透，天然也就影响了性能。所以造成了fnc2的工夫长于fnc1的工夫。

延长浏览

  • 《如何写出让CPU执行更快的代码》链接
  • 《开发内功修炼》链接
  • 《深刻了解计算机系统》第六章：存储器层次结构