編者按：C/C++代碼在編譯時(shí)，編譯器將源碼翻譯成CPU可識(shí)別的指令序列并生成可執(zhí)行代碼，而最終代碼的運(yùn)行效率取決于由編譯器生成的可執(zhí)行代碼。在大部分情況下，編寫源代碼時(shí)就已經(jīng)決定了程序可以在何種程度下被編譯器優(yōu)化。即使對(duì)源代碼做微小改動(dòng)也可能會(huì)對(duì)編譯器生成的代碼運(yùn)行效率產(chǎn)生重大影響。因此，源代碼的優(yōu)化可以在一定程度上幫助編譯器生成更高效的可執(zhí)行代碼。

本文將以Loop Interchange的場(chǎng)景為例，講述在編寫代碼時(shí)可以拿到更優(yōu)性能的書寫方式。

1. Loop Interchange 相關(guān)基本概念

1.1 訪問局部性

訪問局部性指的是在計(jì)算機(jī)科學(xué)領(lǐng)域中應(yīng)用程序在訪問內(nèi)存的時(shí)候，傾向于訪問內(nèi)存中較為靠近的值。這種局部性是出現(xiàn)在計(jì)算機(jī)系統(tǒng)中的一種可預(yù)測(cè)行為，我們可以利用系統(tǒng)的這種強(qiáng)訪問局部性來進(jìn)行性能優(yōu)化。訪問局部性分為三種基本形式，分別為時(shí)間局部性、空間局部性、循序局部性。

而本文主要講述的Loop Interchange主要是利用了空間局部性。空間局部性指的是，最近引用過的內(nèi)存位置以及其周邊的內(nèi)存位置容易再次被使用。比較常見于循環(huán)中，比如在一個(gè)數(shù)組中，如果第3個(gè)元素在上一個(gè)循環(huán)中被使用，那么本次循環(huán)中極有可能會(huì)使用第4個(gè)元素；如果本次循環(huán)確實(shí)使用第4個(gè)元素，就是命中上一次迭代所prefetch到的cache數(shù)據(jù)。

所以對(duì)于數(shù)組循環(huán)運(yùn)算，可以利用空間局部性這一特征，保證兩次相鄰循環(huán)中對(duì)數(shù)組元素的訪問在內(nèi)存上是更加靠近的，即循環(huán)訪問數(shù)組中的元素時(shí)stride越小，相應(yīng)的性能可能會(huì)有所優(yōu)化。

那么，數(shù)組在內(nèi)存上是如何存儲(chǔ)的呢？

1.2 Row-major 和 Column-major

Row-major 和 Column-major 是兩種將多維數(shù)組存儲(chǔ)在線性存儲(chǔ)中的方式。數(shù)組的元素在內(nèi)存中是連續(xù)的；Row-major ordering代表行的連續(xù)元素在內(nèi)存中彼此相鄰，而Column-major ordering則是代表列的連續(xù)元素彼此相鄰，如下圖所示。

雖然Row和Column的名稱看起來像是特指二維數(shù)組，但是Row-major和Column-major也可以推廣適用于任何維度的數(shù)組。

那么在C/C++中，數(shù)組是以以上哪種方式存儲(chǔ)的呢？

舉一個(gè)小例子，用cachegrind工具來展示C使用兩種不同的訪問形式的CPU的cache丟失率對(duì)比。

按行訪問：

?

#include?

int?main(){
????size_t?i,j;
????const?size_t?dim?=?1024?;
????int?matrix?[dim][dim];

????for?(i=0;i

	?

	

	按列訪問：

	?
#include?

int?main(){

????size_t?i,j;

????const?size_t?dim?=?1024?;

????int?matrix?[dim][dim];

????for?(i=0;i

	?

	

	根據(jù)上述C代碼中對(duì)相同數(shù)組的兩種不同訪問方式時(shí)cache丟失率的對(duì)比，可以說明在C/C++代碼中，數(shù)組是以Row-major形式儲(chǔ)存的。也就是說，如果前一步訪問了a[i][j]，那么對(duì)a[i][j+1]的訪問會(huì)命中cache。這樣就不會(huì)執(zhí)行對(duì)主存儲(chǔ)器的訪問，而cache比主內(nèi)存快，因此遵循相應(yīng)編程語言的儲(chǔ)存形式使其可以命中cache可能會(huì)帶來優(yōu)化。

	至于其他常用的編程語言，F(xiàn)ortran、MATLAB等則是默認(rèn)Column-major形式。

	1.3 Loop Interchange

	Loop Interchange利用系統(tǒng)傾向于訪問內(nèi)存中較為靠近的值的特征以及C/C++ Row-major的特點(diǎn)，通過改變循環(huán)嵌套中兩個(gè)循環(huán)之間的執(zhí)行順序，增加整體代碼空間局部性。此外，它還可以啟用其他重要的代碼轉(zhuǎn)換，例如，Loop Reordering就是Loop Interchange擴(kuò)展到兩個(gè)以上循環(huán)被重新排序時(shí)的優(yōu)化。在LLVM中，Loop Interchange需要通過使能-mllvm -enable-loopinterchange選項(xiàng)啟用。

	2. 優(yōu)化示例

	2.1 基礎(chǔ)場(chǎng)景

	簡單看下面一個(gè)矩陣運(yùn)算的示例：

	原始代碼：

	?
??for(int?i?=?0;?i?

	?

	試著把jk兩層循環(huán)進(jìn)行Loop Interchange之后的代碼：

	?
??for(int?i?=?0;?i?

	?

	可以發(fā)現(xiàn)，在原始代碼中，最內(nèi)層的k每次迭代，C要訪問的數(shù)據(jù)不變，A每次訪問的stride為1，大概率命中cache，但B由于每次訪問的stride為1024，幾乎每次都會(huì)cache miss。Loop Interchange之后，j位于最內(nèi)層循環(huán)，每次迭代時(shí)A每次要訪問的數(shù)據(jù)不變，C和B每次訪問的stride為1，都會(huì)有很大概率命中cache，cache命中率大大增加。

	那么cache命中率是否真的增加，以及兩者的性能又如何呢？

	原始代碼：

	?
$?time?-p?./a.out?


	?

	

	?
$?sudo?perf?stat?-r?3?-e?cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads?./a.out

	?

	

	Loop Interchange后的結(jié)果如下：

	?
$?time?-p?./a.out?


	?

	

	?
$?sudo?perf?stat?-r?3?-e?cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads?./a.out


	?

	

	兩者相比：

	L1-dcache-loads的數(shù)目差不多，因?yàn)橐L問的數(shù)據(jù)總量差不多；

	L1-dcache-load-misses所占L1-dcache-loads的比例在進(jìn)行Loop Interchange代碼修改后降低了將近10倍。

	同時(shí)，性能數(shù)據(jù)上也能帶來接近9.5%的性能提升。

	2.2 特殊場(chǎng)景

	當(dāng)然，在實(shí)際使用時(shí)，并不是所有的場(chǎng)景都是如2.1中所示的那種工整的可Loop Interchange場(chǎng)景。

	?
for?(?int?i?=?0;?i?

	?

	如上述場(chǎng)景，如果N是超大數(shù)組，那么Loop Interchange理論上可以帶來較大收益；但由于兩層循環(huán)中間增加一個(gè)分支判斷，導(dǎo)致原本可以Loop Interchange的場(chǎng)景無法實(shí)現(xiàn)。

	針對(duì)這種場(chǎng)景，可以考慮將中間的分支判斷邏輯剝離，可以先保證Loop Interchange使得數(shù)組res在連續(xù)內(nèi)存上進(jìn)行訪問；至于中間的判斷分支邏輯，可以在Loop Interchange兩層循環(huán)后再進(jìn)行回退。

	?
for?(?int?m?=?0;?m?

	?

	當(dāng)然，這樣的源碼修改也需要考慮cost是否值得，如果該if分支進(jìn)入頻率非常高，那么之后回退帶來的cost也會(huì)較大，可能就需要重新考慮Loop Interchange是否值得；反之，如果分支進(jìn)入頻率非常低，那么Loop Interchange的實(shí)現(xiàn)還是可以帶來可觀的收益的。

	3. 畢昇編譯器在LLVM社區(qū)的貢獻(xiàn)

	畢昇編譯器團(tuán)隊(duì)在LLVM社區(qū)中對(duì)Loop Interchange pass也做出了不小的貢獻(xiàn)。團(tuán)隊(duì)從legality、profitability等方面對(duì)Loop Interchange pass做了全方位的增強(qiáng)，同時(shí)也對(duì)該pass所支持的場(chǎng)景做了大量的擴(kuò)展。在Loop Interchange方面，近兩年來團(tuán)隊(duì)小伙伴為社區(qū)提供了二十余個(gè)主要的patch，包含Loop Interchange，以及相關(guān)的dependence analysis、loop cache analysis、delinearization等分析和優(yōu)化的增強(qiáng)。簡單舉幾個(gè)例子：

	D114916 [LoopInterchange] Enable loop interchange with multiple outer loop indvars (https://reviews.llvm.org/D114916)

	D114917 [LoopInterchange] Enable loop interchange with multiple inner loop indvars (https://reviews.llvm.org/D1149167)

	這兩個(gè)patch將Loop Interchange的應(yīng)用場(chǎng)景擴(kuò)展到內(nèi)層或者外層循環(huán)中包含不止一個(gè)induction variable的情況：

	?
for?(c?=?0,?e?=?1;?c?+?e?

	?

	D118073 [IVDescriptor] Get the exact FP instruction that does not allow reordering (https://reviews.llvm.org/D118073)

	D117450 [LoopInterchange] Support loop interchange with floating point reductions (https://reviews.llvm.org/D117450)

	這兩個(gè)patch將Loop Interchange的應(yīng)用場(chǎng)景擴(kuò)展到支持浮點(diǎn)類型的reduction計(jì)算的場(chǎng)景：

	?
double?matrix[dim][dim];
for?(j=0;j

	?

	D120386 [LoopInterchange] Try to achieve the most optimal access pattern after interchange (https://reviews.llvm.org/D120386)

	這個(gè)patch增強(qiáng)了Interchange的能力使編譯器能夠?qū)⒀h(huán)體permute成為全局最優(yōu)的循環(huán)順序：

	?
void?f(int?e[100][100][100],?int?f[100][100][100])?{
??for?(int?a?=?0;?a?

	?

	=>

	?
void?f(int?e[100][100][100],?int?f[100][100][100])?{
??for?(int?c?=?0;??c?

	?

	D124926 [LoopInterchange] New cost model for loop interchange (https://reviews.llvm.org/D124926)

	這個(gè)patch為loop interchange提供了一個(gè)全新的，功能更強(qiáng)的cost model，可以更準(zhǔn)確地對(duì)loop interchange的profitability做出判斷。

	結(jié)語

	如果想要盡可能的利用Loop Interchange優(yōu)化，那在書寫C/C++代碼時(shí)，請(qǐng)盡可能保證每個(gè)迭代之間對(duì)數(shù)組或數(shù)列的訪問stride越小越好；stride越接近1，空間局部性就越高，自然cache命中率也會(huì)更高，在性能數(shù)據(jù)上也可以拿到更理想的收益。另外，由于C/C++的存儲(chǔ)方式為Row-major ordering，所以在訪問多維數(shù)組時(shí)，請(qǐng)注意內(nèi)層循環(huán)要為Column才能拿到更小的stride。　　

	? ? ? 審核編輯：彭靜