這代碼居然有差別？CPU友好的代碼該這樣寫
本文用實際用例闡述了用心組織的代碼也能讓性能提升百倍，我們不應該停留在CRUD的漩渦中。下面來看看這個神奇的現象。
一、震驚，這代碼居然有差別！
CPU友好的代碼與我們平時的那些CRUD操作可能沒啥關系。但是用心組織的代碼其實也能讓性能提升百倍。我們不應該停留在CRUD的漩渦中。今天我給大家?guī)硪粋€很神奇的現象，文章不長，原理通用，還請大家耐心看完！
我們可以先看下面的矩陣計算。
大家也可以自己思考一下，如果是你來實現一個矩陣的乘法，你會怎么來做。
下圖是我給出的A、B、C 三個解題的思路。大家覺得在Jvm里面，下面的代碼性能會有區(qū)別么？如果有的話，哪一個會快一點？如果沒有的話，又為什么？
這里停頓兩秒。
/...1
/...2
現在是公布答案的時間，下圖是benchmark運行的結果（具體的運行代碼和結果查看文末的附件），是否和你想的一樣呢。
x軸是計算數組的大小。y軸是所消耗的時間。
最上兩條線是 B 代碼塊兒的結果，中間是 A 代碼塊兒的結果，最下面是 C 代碼塊兒的結果。
從運行時間角度看結果是：TC?< TA?< TB。從性能角度看結果是：PC?> PA?> PB。
大家猜對結果了么？是不是很你想的一樣呢？
如果不是的話，那就慢慢往下面看吧。
二、為什么會有性能差別？
要想知道這個問題的答案，我們需要知道兩個知識點，缺一不可。
首先，我們需要知道Java二維數組的存儲結構是什么樣子的。
其次，我們需要知道CPU在計算的時候它L1、L2、L3的緩存機制。
2.1 知識點
2.1.1 知識點一 -- Java二維數組的存儲結構
下圖便是Java二維數組的一個存儲方式示意圖，意思是 int[][] array_A = new int[4][3]。
在一個數組里面存的都是“指針”，指向真實存放數據的地址塊。
每一行的數據是連續(xù)的地址，但是行與行之間的地址就不一定連續(xù)了。這一點很重要，后面會用到。
2.1.2 知識點二 -- CPU的緩存機制
CPU架構是會演進的，高低端的參數也不一定相同。但我們畢竟不是CPU的制造者，不必每一個CPU都去細扣，我們只需要理解他的原理，在適當的時候做一些抽象方便理解就可以了。
下圖是我當前Mac的CPU參數，大家需要注意2個東西，L2緩存、L3緩存。這2個參數就是影響我們今天討論的性能的主要因素。
下面是各個緩存的CPU的訪問時間：
L1 、L2、L3、主存 的大小是逐漸增大，速度是逐漸減小的。
下面是現代CPU的一個架構示意圖：
其中：Regs，是寄存器。
d-cache，是數據緩存。
i-cache，是指令緩存。
本次我們并不討論這個緩存快的影響。
L1、L2、L3和主存的緩存的內容，可以參考下圖：
圖片來自：https://www.deskdecode.com/what-is-cpu-central-processing-unit-and-how-its-work/
CPU的緩存里面還有很多的細節(jié)，我就先忽略了，知道上面的信息就已經足夠我們理解今天的問題了。
2.2 性能損失的原因 -- 緩存命中率
有了上面的各級別的緩存參考之后，我們可以想象一下，如果把上面的圖像換成是我們的二維數組呢。是不是就是下面這樣（可能沒有那么嚴謹，但是不妨礙我們理解）。
在RAM（主存）的數據是這樣的：
L3緩存就是這樣的（紅色框選中部分）：
L2緩存就是這樣的（紅色框選中部分）：
有了這個這些層級的緩存之后，CPU在計算的時候就可以不用來回的到速度極慢的RAM（主存）中去找數組的數據了。
2.2.1 友好的遍歷方式
假設上面的數據的變量名稱是A，成員使用 a 來表述。
我們取數據按照?從左到右，再從上到下?的順序來進行遍歷。
對于L2緩存來說，
第一次獲取數據 a11（“1”）的時候其實是沒有數據的，所以會耗時去把 a11，a12，a13（“1，2，3”）都取回來緩存起來。
當第二次取 a12、a13的時候候就直接從L2緩存取了。這樣 cache 命中率就是?66.7%.
對于L3的情況類似。
這樣的遍歷方式對于CPU來說是一個很友好且高效的。
?C代碼塊 就是這種橫向優(yōu)先的訪問方式。
?A代碼塊 里面對 arrays_A 的方式是橫向優(yōu)先遍歷的，但是在處理 arrays_B 的時候就是縱向遍歷的（也就是下面即將提到的方式）。
?B代碼塊 所有的訪問都是縱向的（不友好的遍歷方式）。因為發(fā)揮不出CPU緩存的效果，所以性能最差。
2.2.2 不友好的遍歷方式
從上到下，再從左到右。
為啥這是一個不好的遍歷方式呢？
這個得結合上一節(jié)Java的二維數組的存儲結構一起看。再來回顧一下：
從上面的存儲的結構圖來看，其實 a11，a12，a13?與 a21，a22，a23?行與行之間并不是連續(xù)的。所以對于L1、L2、L3緩存來說很有可能是不能一起被緩存的（這里用了可能，具體得看L1、L2、L3的容量和數組的大小）。雖然是可能，但是通常都不會一起出現。
有了這個知識之后，我們再來看，先從上到下，再從左到右的順序的緩存命中率。
第一次，獲取 a11，但是緩存里面沒有，找到 a11?之后就把 a11，a12，a13?緩存下來了。
第二次，獲取 a21，但是緩存里面沒有，找到 a21?之后就把 a21，a22，a23??緩存下來了，假設有CPU有兩行的緩存空間。
第三次，獲取 a31，但是緩存里面沒有，找到 a31?之后把 a31，a32，a33??緩存下來，并且把 a11，a12，a13??替換掉（緩存的空間有限，雖然具體的替換策略有很多種，并且還和數據本身的Hash有關系，這里就假設把第一次的結果覆蓋了）。
后面的邏輯重復之前的步驟。最后得到的緩存命中率就是?0%?。
結合文章開頭的緩存速率表格，我們就不難發(fā)現，如果我們每次都不命中緩存的話，那么延遲帶來的耗時將會相差一個數量級。
三、總結
再來回顧一下我們之前的問題。
C代碼塊 是橫向優(yōu)先的訪問方式。?
A代碼塊 里面對 arrays_A 的方式是橫向順序訪問的，但是在處理 arrays_B 的時候就是縱向遍歷的。?
B代碼塊 所有的訪問都是縱向的（不友好的遍歷方式）。因為發(fā)揮不出CPU緩存的效果，所以性能最差。
Java的二維數組在內存里面是行連續(xù)的，但是行與行之間不一定連續(xù)。CPU在緩存大小有限的情況下，不可能把所有的數據都緩存下來。再加上每一層級訪問速度的硬件限制，就導致了上面的性能結果。
相信大家也和我一樣，知道原理之后，也不是那么迷惑了。
在實際的業(yè)務環(huán)境中，我們不一定能遇到這種純計算的場景。但是我們還是應該盡量順序訪問數據，不管是什么樣的數據。投其所好，方能夠優(yōu)化代碼性能。
其次，我們在訪問數據的時候，還是需要了解各種語言背后實際的存儲結構和CPU的緩存原理，本次是講述的是Java，但是這個思想其他語言其實也是受用的。
四、附件
4.1 運行的環(huán)境
系統(tǒng)參數：JMH version: 1.36
VM version: JDK 11.0.13, Java HotSpot(TM) 64-Bit Server VM, 11.0.13+10-LTS-370
4.2 整個benchmark的java代碼
ArrayTestBenchmark
4.3 多次運行benchmark的結果
引用：
《深入理解計算機操作系統(tǒng)》
《深入理解Java虛擬機》
