第5章?優(yōu)化程序性能 關(guān)鍵詞：程序優(yōu)化，循環(huán)開銷，并行性，投機(jī)執(zhí)行，Amdahl定律 編寫高效程序需要兩類活動(dòng)：第一，我們必須選擇一組最好的算法和數(shù)據(jù)結(jié)構(gòu)；第二，我們必須編寫出編譯器能夠有效優(yōu)化以轉(zhuǎn)換成高校可執(zhí)行代碼的源程序。 研究匯編代碼是理解編譯器以及產(chǎn)生的代碼會(huì)如何運(yùn)行的最有效的手段之一。 5.1優(yōu)化編譯器的能力和局限性 對許多程序都很有用的度量標(biāo)準(zhǔn)是每元素的周期數(shù)（cycle per element，CPE）。這種度量標(biāo)準(zhǔn)幫助我們在更詳細(xì)的級(jí)別上理解迭代程序的循環(huán)性能。 1 降低過程調(diào)用開銷 消除循環(huán)的低效率。移動(dòng)代碼優(yōu)化，這類優(yōu)化包括識(shí)別出要執(zhí)行多次（例如，在循環(huán)里）但是計(jì)算結(jié)果不會(huì)改變的計(jì)算，因而我們可以將計(jì)算移動(dòng)到代碼前面的、不會(huì)被多次求值的部分。 減少過程調(diào)用。過程調(diào)用會(huì)帶來相當(dāng)大的開銷，而且妨礙大多數(shù)形式的程序優(yōu)化。因此減少過程調(diào)用，可以優(yōu)化程序代碼。對于性能至關(guān)重要的程序來說，為了速度，經(jīng)常必須要損害一些模塊性和抽象性。如果以后要修改代碼，添加一些對所采用的變換進(jìn)行文檔的記錄是很明智的。 消除不必要的存儲(chǔ)器引用。換句話說，就是減少程序讀入和寫入的次數(shù)，數(shù)據(jù)量少的時(shí)候可能用處不明顯，但是一旦數(shù)據(jù)量變大，少讀取一次就會(huì)使得程序性能大大優(yōu)化。 2 針對目標(biāo)處理器進(jìn)行的程序優(yōu)化 P6微體系結(jié)構(gòu)，在工業(yè)上稱為超標(biāo)量（superscalar），意思是它可以在每個(gè)時(shí)鐘周期執(zhí)行多個(gè)操作，而且是亂序的（out-of-order），意思就是指令執(zhí)行的順序不一定要與它們在匯編程序中的順序一致。整個(gè)設(shè)計(jì)有兩個(gè)主要部分：ICU（instruction control unit，指令控制單元）和EU（execution unit，執(zhí)行單元）。前者負(fù)責(zé)從存儲(chǔ)器中讀取指令序列，并根據(jù)指令序列生成一組針對程序數(shù)據(jù)的基本操作；而后者執(zhí)行這些操作。 功能單元的性能。每個(gè)操作數(shù)都是由兩個(gè)周期計(jì)數(shù)值來刻畫的：一個(gè)是執(zhí)行時(shí)間（latency），它指明功能單元完成操作所需要的總周期數(shù)；另一個(gè)是發(fā)射時(shí)間（issue time），它指明連續(xù)的、獨(dú)立操作數(shù)之間的周期數(shù)。 通常處理器性能是受三類約束閑置的。第一，程序中的數(shù)據(jù)相關(guān)性迫使一些操作延遲直到它們的操作數(shù)被計(jì)算出來。因?yàn)楣δ軉卧幸粋€(gè)或多個(gè)周期的執(zhí)行時(shí)間，這就設(shè)置了一個(gè)給定的操作序列執(zhí)行周期數(shù)的下界。第二，資源約束限制了在任意給定時(shí)刻能夠執(zhí)行多少個(gè)操作。最后，轉(zhuǎn)移預(yù)測邏輯的成功約束了處理器能夠在指令流中超前工作以保持執(zhí)行單元繁忙的程度。每次發(fā)生預(yù)測錯(cuò)誤時(shí)，處理器從正確位置重新開始都會(huì)引起很大的延遲。 5.2 降低循環(huán)開銷 我們可以在每次迭代中執(zhí)行更多的數(shù)據(jù)操作來減小循環(huán)開銷的影響，使用的是稱為循環(huán)展開（loop unrolling）技術(shù)。其思想是在一次迭代中對多個(gè)數(shù)組元素進(jìn)行訪問和合并操作。這樣使得到的程序需要更少的迭代，從而降低循環(huán)的開銷。 循環(huán)展開的兩個(gè)缺點(diǎn)：第一，使用循環(huán)展開時(shí)，我們引入了一種新的開銷——當(dāng)向量長度不能被展開整除時(shí)，需要完成所有剩下的元素（如for循環(huán)，原本循環(huán)變量為i+1,現(xiàn)在為i+3）。第二，就是它增加了生成的目標(biāo)代碼的數(shù)量。 將數(shù)組代買轉(zhuǎn)換到指針代碼，可以優(yōu)化程序性能，但是這是以程序的可讀性為代價(jià)的。通常數(shù)組代碼更可取一些。編譯器中，他們對數(shù)組代碼應(yīng)用非常高級(jí)的優(yōu)化，而對指針代碼只應(yīng)用最小限度的優(yōu)化。 5.3 提高并行性 處理器的幾個(gè)功能單元是流水線化的，這意味著它們可以在前一個(gè)操作完成之前開始一個(gè)新的操作。我們的代碼不能利用這種能力，即使使用循環(huán)展開也不能，這是因?yàn)槲覀儗⒗鄯e值放在一個(gè)單獨(dú)的變量中。直到前面的計(jì)算完成之前，我們都不能計(jì)算x的新值。因此，處理器會(huì)暫停（stall），等待開始新的操作，直到當(dāng)前操作完成。 1 循環(huán)分割（loop splitting） 對于一個(gè)可結(jié)合和可交換的合并操作來說，比如說整數(shù)加法或乘法，我們可以通過將一組合并操作分割成兩個(gè)或更多的部分，并在最后合并結(jié)果來提高性能（但是，循環(huán)分割后的寄存器存放如果發(fā)生溢出，則會(huì)出現(xiàn)性能急劇下降，如2所示）。 2 寄存器溢出（register spilling） 循環(huán)并行性的好處是受描述計(jì)算的匯編代碼的能力閑置的。特別地，IA32指令集中有很少量的寄存器來存放累積的值。如果我們有并行度p超過了可用的寄存器數(shù)量，編譯器會(huì)訴諸于溢出，將某些臨時(shí)值存放到棧中。一旦出現(xiàn)這種情況，性能會(huì)急劇下降。 對于整數(shù)數(shù)據(jù)類型的情況，總共只有八個(gè)整數(shù)寄存器可用。其中有兩個(gè)（%ebp和%esp）指向棧中的區(qū)域。 5.4 綜合：優(yōu)化合并代碼的效果小結(jié) 1 浮點(diǎn)性能異常：可能是提前溢出報(bào)錯(cuò)，從而降低了運(yùn)行時(shí)間。 2 變換平臺(tái)。 3 轉(zhuǎn)移預(yù)測和預(yù)測錯(cuò)誤懲罰。 正如我們前面提到過的，現(xiàn)代處理器在執(zhí)行當(dāng)前指令之前能工作的得很好，從存儲(chǔ)器讀取新指令，并譯碼指令，已確定在什么操作數(shù)上執(zhí)行什么操作。只要指令遵循的是一種簡單的順序，那么這種指令流水線化（instruction pipelining）就能很好地工作。不過，當(dāng)遇到轉(zhuǎn)移的時(shí)候，處理器必須猜測轉(zhuǎn)移該往哪個(gè)方向走。對于條件跳轉(zhuǎn)的情況，這意味著要預(yù)測是否會(huì)選擇轉(zhuǎn)移。對于間接跳轉(zhuǎn)（就像我們在代碼中看到的，跳轉(zhuǎn)到由一個(gè)跳轉(zhuǎn)條目指定的地址）或過程返回這樣的指令，這意味著預(yù)測目標(biāo)地址。 在一個(gè)說投機(jī)執(zhí)行（speculative execution）的處理器中，處理器會(huì)開始執(zhí)行預(yù)測的轉(zhuǎn)移目標(biāo)處的指令。它這樣做的方式是，避免修改任何實(shí)際的寄存器或存儲(chǔ)器位置，直到確定了實(shí)際的結(jié)果。如果預(yù)測是正確的，處理器就簡單地“提交”投機(jī)執(zhí)行的指令的結(jié)果，把他們存儲(chǔ)到寄存器或存儲(chǔ)器中。如果預(yù)測是錯(cuò)誤的，處理器必須丟掉所有投機(jī)執(zhí)行的結(jié)果，在正確的位置，重新開始取指令的過程。這樣做會(huì)引起很大的轉(zhuǎn)移處罰（branch penalty），因?yàn)樵诋a(chǎn)生有用的結(jié)果之前，必須重新填充指令流水線。 直到最近，支持投機(jī)執(zhí)行所需的技術(shù)都被認(rèn)為是開銷太大，對除了最高級(jí)的超級(jí)計(jì)算機(jī)以外的所有機(jī)器來說都是異乎尋常的。不過大約從1998年開始，集成電路技術(shù)使得可以在一塊芯片上放置如此之多的電路，以至于有些電路可以專門用來支持轉(zhuǎn)移預(yù)測和投機(jī)執(zhí)行。到目前，臺(tái)式機(jī)或服務(wù)器中幾乎每個(gè)處理器都支持投機(jī)執(zhí)行。 不幸的是，C程序員對改進(jìn)一個(gè)程序的轉(zhuǎn)移性能是無能為力的，除了意識(shí)到數(shù)據(jù)相關(guān)的轉(zhuǎn)一會(huì)引起性能上更高的花費(fèi)。除此之外，程序員對編譯器產(chǎn)生的詳細(xì)的轉(zhuǎn)移結(jié)構(gòu)幾乎沒有什么控制，很難使轉(zhuǎn)移更容易預(yù)測一些。最終，我們必須依靠兩種因素的結(jié)合，一是編譯器生成好的代碼，盡量減少條件轉(zhuǎn)移的使用；另一個(gè)是處理器有效地顓臾預(yù)測，降低轉(zhuǎn)移預(yù)測錯(cuò)誤的數(shù)量。 5.5 現(xiàn)實(shí)生活：性能提高技術(shù) 優(yōu)化程序的基本策略： 1 高級(jí)設(shè)計(jì)。為手邊的問題選擇適當(dāng)?shù)乃惴ê蛿?shù)據(jù)結(jié)構(gòu)。要特別警覺，避免使用漸進(jìn)地產(chǎn)生遭高性能的算法或編碼技術(shù)。 2 基本編碼原則。避免限制優(yōu)化的因素，這樣編譯器就能產(chǎn)生高效的代碼。 （1）消除連續(xù)的函數(shù)調(diào)用。在可能時(shí)，將計(jì)算移到循環(huán)外。考慮有選擇的妥協(xié)程序的模塊性以獲得更大的效率。 （2）消除不必要的存儲(chǔ)器引用。引入臨時(shí)變量來保存中間結(jié)果。只有在最后的值計(jì)算出來時(shí)，才將結(jié)果存放到數(shù)組或全局變量中。 3 低級(jí)優(yōu)化 （1）嘗試各種與數(shù)組代碼相關(guān)的指針形式。 （2）通過展開循環(huán)降低循環(huán)開銷。 （3）通過諸如迭代分割之類的技術(shù)，找到使用流水線化的功能單元的方法。 要給讀者的忠告是，要小心避免花費(fèi)精力在令人誤解的結(jié)果上。一項(xiàng)有用的技術(shù)是，在優(yōu)化代碼時(shí)使用檢查代碼（checking code）來測試代碼的每個(gè)版本，以確保在這一過程中沒有引入錯(cuò)誤。檢查代碼將一系列測試應(yīng)用到程序上，確保它得到期望的結(jié)果。當(dāng)引入新的變量，改變循環(huán)邊界，以及使代碼整體更復(fù)雜時(shí)，很容易出錯(cuò)。此外，注意到性能上任何不同尋常的或出乎意料的變化是很重要的。 5.6 確認(rèn)和消除性能瓶頸 代碼剖析程序（code profiles），這是在程序執(zhí)行時(shí)手機(jī)性能數(shù)據(jù)的分析工具。 系統(tǒng)優(yōu)化的通用原則，成為Amdahl定律（Amdahl's law）。 程序剖析包括運(yùn)行程序的這樣一個(gè)版本，其中插入了工具代碼，以確定程序的各個(gè)部分需要多少時(shí)間。確認(rèn)出程序中我們需要集中注意力優(yōu)化的部分是很有用的。剖析的一個(gè)有力之處在于可以一邊在現(xiàn)實(shí)的基準(zhǔn)數(shù)據(jù)（benchmark data）上運(yùn)行的程序，一邊進(jìn)行剖析。 Amdahl定律，其主要思想是當(dāng)我們加快系統(tǒng)一個(gè)部分的速度時(shí)，對系統(tǒng)整體性能的影響依賴于這個(gè)部分有多重要和速度提高了多少。考慮一個(gè)系統(tǒng)，在其中執(zhí)行某個(gè)應(yīng)用程序所用的時(shí)間T1，假設(shè)系統(tǒng)的某個(gè)部分需要這個(gè)時(shí)間的百分比為a，而我們將它的性能提高了k倍，也就是這個(gè)部分原來需要時(shí)間aT1，而現(xiàn)在需要時(shí)間（aT1/k），因此整個(gè)執(zhí)行時(shí)間位T2： T2=（1-a）T1+（aT1）/k。 據(jù)此，我們可以計(jì)算加速S=T2/T1為 S=1/((1-a)+a/k)。 Amdahl定律提供了對通過只改進(jìn)系統(tǒng)的一部分所獲得性能收益的一個(gè)簡單但是很有力的看法。收益既依賴于我們對這個(gè)部分的提高程度，也依賴于這個(gè)部分原來在整個(gè)時(shí)間中所占的比例。 參考文獻(xiàn) 布賴恩特, O'Hallaron D, et al. 深入理解計(jì)算機(jī)系統(tǒng)[M]. 中國電力出版社, 2004.