這篇主要是利用局部性原理優(yōu)化程序性能，以前也寫過一篇優(yōu)化程序性能，這篇主要是結(jié)合perf工具，量化比較程序性能的優(yōu)化前后使用。
一 存儲體系
1.1 存儲層組成
計算機的存儲是由多級存儲組成的存儲體系，原因是越快的存儲成本越高，越慢的存儲成本越低。利用多級存儲，可以讓計算機在擁有一個成本和底層最便宜的存儲相當，但是卻以接近頂層存儲存儲的告訴速度向程序提供數(shù)據(jù)讀寫。存儲體系中每一層都會作為下一層存儲的緩存，如下圖
1.2 存儲訪問速度
存儲體系中各層存儲中越接近CPU的位置速度越快，L1 緩存訪問的速度為1-5個時鐘周期，L2緩存訪問速度為12個時鐘周期，L3 緩存大約30個時鐘周期；一般來說L1和L2是每個CPU核心都具有的，L3是多個CPU核心共享的。
2GHZ的cpu上速度如下：
1.3 linux中緩存查看
不同的cpu 上的L1、L2 和L3的大小是不同的，在Linux上可以通過以下命令查詢：
[root@localhost ~]# tree /sys/devices/system/cpu/cpu0/cache
/sys/devices/system/cpu/cpu0/cache
├── index0
│ ├── coherency_line_size
│ ├── id
│ ├── level
│ ├── number_of_sets
│ ├── physical_line_partition
│ ├── shared_cpu_list
│ ├── shared_cpu_map
│ ├── size
│ ├── type
│ └── ways_of_associativity
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/type
Data
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
8
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/shared_cpu_list
0
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/physical_line_partition
1
[root@localhost ~]# cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
64
說明：
size： 緩存大小32K
coherency_line_size: cache line size 對齊大小，64 字節(jié)。
number_of_sets： 緩存0中的組數(shù)；
ways_of_associativity : 組中的行數(shù)；
shared_cpu_list ：可以被哪些cpu共享；
type： Data 數(shù)據(jù)緩存(Instruction指令緩存、Unified 通用指令)
更簡單的查詢辦法：
[root@localhost ~]# lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Xeon(R) CPU E3-1220 v3 @ 3.10GHz
Stepping: 3
CPU MHz: 3106.417
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 6186.09
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0-3
二 cache和內(nèi)存
2.1 緩存優(yōu)點和局限性
上面我們知道，L1和L2緩存數(shù)據(jù)是以cache line為單位的，一般都是64字節(jié)為一個cache line。也就是每次緩存數(shù)據(jù)的時候是直接緩存64個字節(jié)，這樣可以利用存儲的局部性優(yōu)勢，但是也會有偽共享的問題，即如果緩存的數(shù)據(jù)不夠64個字節(jié)，兩個緩存數(shù)據(jù)同時存在一個緩存行中，一個數(shù)據(jù)更新后，整個緩存行失效。
還有一個問題就是當一個數(shù)據(jù)被多個cpu核心共享的時候，會有一致性問題。如果一個cpu修改了數(shù)據(jù)，需要同時讓其他cpu共享的同一份數(shù)據(jù)失效，這樣會造成cpu cache miss和一致性問題。
行業(yè)內(nèi)通過MESI協(xié)議來保證Cache的一致性。
2.2 內(nèi)存和緩存映射
我們知道程序在計算機中運行的時候，訪問的是虛擬地址，通過MMU將虛擬地址轉(zhuǎn)成實際內(nèi)存地址，如果
PTE（頁表項）不在高速緩存中，就同樣需要將頁表項調(diào)入到緩存中，這樣開銷就會有幾十到幾百個時鐘周期。如果PTE在L1緩存中，開銷就會下降到1-2個時鐘周期，所以現(xiàn)在MMU中都會包含一個小的PTE緩存叫TLB（后備緩沖器）。
CPU請求數(shù)據(jù)的時候是這樣的：
1） CPU產(chǎn)生一個虛擬地址。
2）MMU從TLB中取出PTE。
3）MMU通過PTE將虛擬地址轉(zhuǎn)成物理地址。
4）高速緩存或內(nèi)存將請求的數(shù)據(jù)返回給CPU。
如果TLB沒有命中，則需要從L1緩存中去取PTE，覆蓋TLB一個PTE。
三 利用高速緩存優(yōu)化程序性能
cpu訪問高速緩存比訪問內(nèi)存快的多，快100倍左右，所以代碼中要善于利用高速緩存提升程序的性能，如何利用那，就是盡量讓寫的程序滿足局部性原理，局部性原理包括兩個部分，第一個是時間的局部性即最近訪問的變量，在很多的時間內(nèi)會再次訪問；第二是空間局部性原理，即某個地址被程序訪問，它周邊的地址很可能會被再次訪問。
- 像我們經(jīng)常在循環(huán)中使用同一個局部變量，就滿足時間的局部性原理，這些變量常被寄存器保存。
- 我們循環(huán)遍歷數(shù)組的時候，滿足空間局部性原理。
一般來說，我們的循環(huán)代碼越小，循環(huán)步長越小，循環(huán)的次數(shù)越多，局部性就越好。
四 測試程序的緩存利用
以下面?zhèn)€小程序為例，看看滿足局部性原理和不滿足局部性原理的性能差異
#include <time.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#define SIZE 2048
long timediff(clock_t t1,clock_t t2)
{
// CLOCKS_PER_SEC 1秒鐘有多少個時鐘
return ( (double) t2 -t1)/CLOCKS_PER_SEC*1000;
}
int main(int argc,char ** argv)
{
//棧上分配，不能分配大了，會內(nèi)存錯誤的
char arrs[SIZE][SIZE];
// cpu時鐘作為計數(shù)單元更準確
clock_t start = clock();
for (int i = 0; i< SIZE; i++) {
for (int j = 0; j< SIZE;j++) {
// arrs[i][j] =0;
arrs[j][i] = 0;
}
}
clock_t end = clock();
//耗時多少ms
printf("\nCost time:%ld \n",timediff(start,end));
}
如果使用循環(huán)體內(nèi)注釋掉的代碼： arrs[i][j] =0; 耗時10ms；如果使用循環(huán)體內(nèi)沒有注釋掉的代碼: arrs[j][i] = 0;耗時50ms。
性能相差5倍，如何得知是利用緩存局部性原理得到的性能提升那，我們可以通過perf工具來查看下兩次執(zhí)行情況：
[root@localhost testcode]# perf stat -e cache-references,cache-misses,instructions,cycles,L1-dcache-load-misses,L1-dcache-loads ./a.out
Cost time:10
Performance counter stats for './a.out':
33,108 cache-references
10,248 cache-misses # 30.953 % of all cache refs
55,486,651 instructions # 1.46 insn per cycle
37,963,618 cycles
112,745 L1-dcache-load-misses # 0.62% of all L1-dcache hits
18,164,912 L1-dcache-loads
0.011468219 seconds time elapsed
0.010431000 seconds user
0.001043000 seconds sys
性能差的情況：
[root@localhost testcode]# perf stat -e cache-references,cache-misses,instructions,cycles,L1-dcache-load-misses,L1-dcache-loads ./a.out
Cost time:50
Performance counter stats for './a.out':
4,228,333 cache-references
31,962 cache-misses # 0.756 % of all cache refs
55,664,205 instructions # 0.31 insn per cycle
177,039,427 cycles
4,306,660 L1-dcache-load-misses # 23.64% of all L1-dcache hits
18,215,744 L1-dcache-loads
0.051881676 seconds time elapsed
0.050861000 seconds user
0.000997000 seconds sys
說明：
①cache-references 表示總的緩存讀取次數(shù)
②cache-misses 表示沒有命中緩存次數(shù)
②/ ① 即緩存的沒有命中率，
③ L1-dcache-load-misses： L1緩存沒有命中次數(shù)
④ L1-dcache-loads ： 總的L1緩存讀取次數(shù)
可以看出，第一執(zhí)行的總的緩存命中率比第二次總的緩存命中率要高的多，而且1個時鐘周期要執(zhí)行的指令條數(shù)也更多。
