向量化
下面這段代碼可以如何優(yōu)化？
void foo(byte[] dst, byte[] src) {
for (int i = 0; i < dst.length - 4; i += 4) {
dst[i] = src[i];
dst[i+1] = src[i+1];
dst[i+2] = src[i+2];
dst[i+3] = src[i+3];
}
... // post-loop
}
- X86_64 平臺不支持內(nèi)存間的直接移動，上面代碼中的dst[i] = src[i]通常會被編譯為兩條內(nèi)存訪問指令
- 第一條指令把src[i]的值讀取至寄存器中
- 第二條指令則把寄存器中的值寫入至dst[i]中
- 上述代碼一個循環(huán)迭代將會執(zhí)行四條內(nèi)存讀取指令，以及四條內(nèi)存寫入指令
- 數(shù)組元素在內(nèi)存中是連續(xù)的，當從src[i]的內(nèi)存地址處讀取 32 位的內(nèi)容時，我們將一并讀取src[i]至src[i+3]的值
- 當向dst[i]的內(nèi)存地址處寫入 32 位的內(nèi)容時，我們將一并寫入dst[i]至dst[i+3]的值
- 通過綜合這兩個批量操作，我們可以使用一條內(nèi)存讀取指令以及一條內(nèi)存寫入指令，完成上面代碼中循環(huán)體內(nèi)的全部工作
//優(yōu)化后代碼：x[i:i+3]指代x[i]至x[i+3]合并后的值
void foo(byte[] dst, byte[] src) {
for (int i = 0; i < dst.length - 4; i += 4) {
dst[i:i+3] = src[i:i+3];
}
... // post-loop
}
SIMD 指令
- 在前面的示例中，我們使用的是 byte 數(shù)組，四個數(shù)組元素并起來也才 4 個字節(jié)
- 如果換成 int 數(shù)組，或者 long 數(shù)組，那么四個數(shù)組元素并起來將會是 16 字節(jié)或 32 字節(jié)
- X86_64 體系架構(gòu)上通用寄存器的大小為 64 位（即 8 個字節(jié)），無法暫存這些超長的數(shù)據(jù)
- 編譯器需借助長度足夠的 XMM 寄存器，來完成 int 數(shù)組與 long 數(shù)組的向量化讀取和寫入操作
- XMM寄存器：
- 由 SSE（Streaming SIMD Extensions）指令集所引入的
- 一開始僅為 128 位。自從 X86 平臺上的 CPU 開始支持 AVX（Advanced Vector Extensions）指令集后（2011 年），XMM 寄存器便升級為 256 位，并更名為 YMM 寄存器
- 原本使用 XMM 寄存器的指令，現(xiàn)將使用 YMM 寄存器的低 128 位
- 單指令流多數(shù)據(jù)流（Single Instruction Multiple Data，SIMD），即通過單條指令操控多組數(shù)據(jù)的計算操作。這些指令我們稱之為 SIMD 指令
-
SIMD 指令將 XMM 寄存器（或 YMM 寄存器、ZMM 寄存器）中的值看成多個整數(shù)或者浮點數(shù)組成的向量，并且批量進行計算
XMM寄存器示意圖 - 128 位 XMM 寄存器里的值可以看成 16 個 byte 值組成的向量，或者 8 個 short 值組成的向量，4 個 int 值組成的向量，兩個 long 值組成的向量
- SIMD 指令PADDB、PADDW、PADDD以及PADDQ，將分別實現(xiàn) byte 值、short 值、int 值或者 long 值的向量加法
- 看如下方法：
void foo(int[] a, int[] b, int[] c) {
for (int i = 0; i < c.length; i++) {
c[i] = a[i] + b[i];
}
}
優(yōu)化后示意圖
- 原本需要c.length次加法操作的代碼，現(xiàn)在最少只需要c.length/4次(理論上)向量加法即可完成。因此，SIMD 指令也被看成 CPU 指令級別的并行
使用 SIMD 指令的 HotSpot Intrinsic
- SIMD 指令雖然非常高效，但是使用起來卻很麻煩
- 主要是因為不同的 CPU 所支持的 SIMD 指令可能不同
- 越新的 SIMD 指令，它所支持的寄存器長度越大，功能也越強
- 為了能夠盡量利用新的 SIMD 指令，我們需要提前知道程序會被運行在支持哪些指令集的 CPU 上，并在編譯過程中選擇所支持的 SIMD 指令中最新的那些
- 我們可以在編譯結(jié)果中納入同一段代碼的不同版本，每個版本使用不同的 SIMD 指令。在運行過程中，程序?qū)⒏鶕?jù) CPU 所支持的指令集，來選擇執(zhí)行哪一個版本
- Java 字節(jié)碼的平臺無關(guān)性，Java 程序無法像 C++ 程序那樣，直接使用由 Intel 提供的，將被替換為具體 SIMD 指令的 intrinsic 方法
- 替代方案是 Java 層面的 intrinsic 方法，這些 intrinsic 方法的語義要比單個 SIMD 指令復雜得多
- 在運行過程中，HotSpot 虛擬機將根據(jù)當前體系架構(gòu)來決定是否將對該 intrinsic 方法的調(diào)用替換為另一高效的實現(xiàn)。如果不，則使用原本的 Java 實現(xiàn)
自動向量化
- 即時編譯器的自動向量化將針對能夠展開的計數(shù)循環(huán)，進行向量化優(yōu)化
- 自動向量化的條件
- 循環(huán)變量的增量應為 1，即能夠遍歷整個數(shù)組
- 循環(huán)變量不能為 long 類型，否則 C2 無法將循環(huán)識別為計數(shù)循環(huán)
- 循環(huán)迭代之間最好不要有數(shù)據(jù)依賴，例如出現(xiàn)類似于a[i] = a[i-1]的語句。當循環(huán)展開之后，循環(huán)體內(nèi)存在數(shù)據(jù)依賴，那么 C2 無法進行自動向量化
- 循環(huán)體內(nèi)不要有分支跳轉(zhuǎn)
- 不要手工進行循環(huán)展開。如果 C2 無法自動展開，那么它也將無法進行自動向量化
