利用CPU緩存實現高性能程序
我們選購電腦時，CPU處理器的配置會有緩存大小，它是CPU性能的重要指標。
為什么呢?因為CPU計算速度與訪問主存速度非常不匹配!
先來看計算速度。單顆CPU計算速度目前在2GHz-4GHz之間，以2.5GHz計即每秒鐘計算25億次，每個時鐘周期耗時1/2.5GHz==0.4納秒。當前所有的計算機都遵循馮諾依曼結構，所以執行任何指令(例如加法操作)的流程必然遵循下圖：
所以，做一次加法的指令是由多個時鐘周期組成的(如取指令和數字、放入寄存器、執行ALU、將結果寫回主存)，做ALU執行指令僅需要1個時鐘周期，而取指令或者取數據、回寫結果數據就需要與主存打交道了。CPU訪問內存(主存)的速度非常慢，訪問一次常常需要上百納秒以上，這與計算指令有千倍的差距!怎樣解決訪問主存慢導致的CPU計算能力的浪費呢?加入CPU緩存!
CPU上增加緩存后，由于CPU緩存離CPU核心更近，所以訪問速度比主存快得多!如果我們訪問內存時，先把數據讀取到CPU緩存再計算，而下次讀取到該數據時直接使用緩存(若未被淘汰掉)，這在時間和空間上都會降低CPU計算能力的浪費!在時間上，有些數據訪問頻率高(熱點)，多次訪問之間都未被淘汰出緩存;在空間上，緩存可以同時加載相鄰的數據、代碼，這樣函數、循環的執行都在使用緩存中的數據。
CPU緩存是分為多級的，原因是熱點數據太大了!最快的緩存一定離CPU核心最近，因為體積小所以容量也最小，不能滿足以MB計算的熱點數據。最終發展出了三級緩存，分別稱為L1、L2、L3級緩存。這三級緩存的訪問速度各不相同，但都遠大于訪問主存的速度(訪問時間更小)，如下圖所示：
可見，L1和L2的緩存訪問速度非常快，只有不到3ns，L3稍慢一些，但都遠小于訪問主存的速度。當然，CPU緩存的大小也遠小于主存的大小，如本文最開始的那張圖，現在的CPU緩存往往只有幾十MB。如果大家點擊具體的CPU細看緩存，可以看到intel只標明了smart cache，如下圖所示(intel e5-2620 v4)：
這個smart cache其實就是L3緩存，現在的CPU都是多核心的，而smart cache就是智能的被多CPU核心共用的意思。那么L1、L2緩存大小為什么不標出來呢?其實沒有必要，因為通常L1就是32KB，而L2是256KB，在linux上我們可以直接看到：
這里，index0和index1分別代表L1緩存中的指令緩存和數據緩存，index2是L2緩存，index3就是L3緩存。也可能一個緩存由多個CPU共享，仍然以E5-2620 v4這個8核16線程的CPU為例：
筆者的服務器有兩顆e5，所以表現為32顆邏輯CPU。由于intel的超線程技術，所以兩顆邏輯CPU對應一顆物理CPU。簡單插一下何謂超線程技術：由于訪問主存的速度太慢，所以intel想了一個主意，就是當CPU在等待從主存中調入數據或者指令時，同時做另一個任務，這樣一顆CPU就表現為兩顆邏輯CPU，如下圖所示：
從shared_cpu_list可見，20MB的L3緩存被16顆邏輯CPU(8顆物理CPU)共享，而L2和L1都是由一顆物理CPU獨占的。
CPU緩存與主存交換數據每次大小是固定的，我們稱其為cpu cache line，在64位系統下通常是64字節，在linux下可以這么獲取該值：
在C語言程序里，可以通過sysconf (_SC_LEVEL1_DCACHE_LINESIZE)獲取，例如在nginx 1.13.8版本后是這么獲取的：
為什么需要cpu cache line這個數值呢?因為它對提高性能是有用的!比如nginx中存儲http header的hash表。假設我們的cache size是64字節，而一個hash bucket是48字節。假如某一個bucket的起始地址是1F7D030，那么它占用的內存就從1F7D030到1F7D05F，而cache size的特性導致只會從64的整數倍地址訪問，于是需要訪問兩次：1F7D000和1F7D040。而如果我們能使得hash bucket大小是cache size的整數倍，那么就不會出現訪問一個hash bucket需要兩次操作主存的情況。比如，若原本bucket size是32，則設為64;原本為96，則設為128，即向上對齊。nginx有一個向上對齊函數就是做這個事的：
上面這個ngx_align算法來源于一個數學特性：對于正整數2^n(n>1)來說，存在這樣的特性，如果整數X是2^n的整數倍，則X的二進制形式的低n位為0， 如果X不是2^n的整數倍，則X與(~(2^n-1))進行與運算可以得到一個與X相近的是2^n整數倍的正整數。對于上對齊，則需要先加上2^n-1，再進行上述運算。
事實上，如果hash bucket沒有對齊cache line，那么出現訪問一個bucket要調用兩次載入主存數據的操作可能性非常大!比如上面的例子中hash bucket size是48，即使***個bucket沒有跨cache line，第2個bucket一定會跨從而導致兩次主存訪問!
當CPU獲取數據時，cpu緩存由于已經存有數據，那么核心可以直接使用緩存，不用再去訪問內存了，這一過程我們稱為cache hit***!反之，稱為cache miss。可見，如果我們的程序在循環或者熱點代碼中，能夠控制數據規模，使之長期落在CPU緩存中，那么性能就可以提升!怎么判斷CPU緩存***率現在是多少呢?在linux下可以通過perf命令輕松實現(centos下通過yum install perf安裝)，如下所示：
當然，perf支持很多事件，包括進程上下文切換等，上面的cache-references,cache-misses兩個事件分別代表緩存***和未***。perf支持的事件很多，如下表所示：
使用perf來定位程序性能的瓶頸是個有效的辦法!
