深入理解計算機系統(二十三):優化程序性能
4 人贊了文章
目錄
1、編寫高效程序的切入點
2、編譯器的優化能力和局限性
3、程序的性能表示
4、提高程序的性能方法
與機器無關
與機器相關
你能獲得的對程序最大的加速比就是當你第一次讓它工作起來的時候。
在講解如何優化程序性能之前,我們首先要明確寫程序最主要的目標就是使它在所有可能的情況下都能正常工作,一個運行的很快的程序但是卻是錯誤的結果是沒有任何用處的,所以我們在進行程序性能優化之前,首先要保證程序能正常運行,且結果是我們需要的。
而且在很多情況下,讓程序跑的更快是我們必須要解決的問題。比如一個程序要實時處理視頻幀或者網路包,那麼一個運行的很慢的程序就不能解決此問題。再比如一個計算任務計算量非常大,需要數日或者數周,如果我們哪怕只是讓它運行的快20%也會產生重大影響。
正文:
1、編寫高效程序的切入點
①、選擇一組合適的演算法和數據結構。
②、編寫出編譯器能夠有效優化以轉換成高效可執行的源代碼。
③、多線程並行處理運算。
對於第一點,程序=數據結構+演算法,選擇合適的數據結構和演算法無疑對於提高程序的運行效率有很大的影響。第二點對於編程者則需要理解編譯器的優化能力以及局限性,編寫程序看上去只是一點小小的改動,可能都會引起編譯器優化方式很大的變化;第三點技術主要這對運算量特別大的運算,我們將一個大的任務分成多個小任務,這些任務又可以在多核和多處理器的某種組合上並行的計算,這裡我們也需要知道,即使是利用並行性,每個並行的線程都要以最高性能的方式執行。
2、編譯器的優化能力和局限性
正確性,正確性,正確性!!!這個要著重提醒,所以編譯器必須很小心的對程序使用安全的優化。限制編譯器只進行安全的優化,會消除一些造成錯誤的運行結果,但是這也意味著程序員必須花費更大的力氣寫出程序使編譯器能夠將之轉換為有效機器代碼。
對於下面兩個程序:
void add1(int *xp,int *yp){ *xp += *yp; *xp += *yp; }
和
void add2(int *xp,int *yp){ *xp += 2* *yp;}
對上上面兩個函數add1和add2,它們都是將存儲在由指針 yp 指示的位置處的值兩次加到指針 xp 指示的位置處的值。但是明顯add2的執行效率要高,它只要求 3 次存儲器的引用(讀*xp,讀*yp,寫*xp),而add1需要 6 次存儲器引用(2次讀*xp,2次讀*yp,2次寫*xp)。
下面有評論指出乘法指令要比加法指令慢很多,這裡的add1是兩次加法指令,而add2是一次乘法指令,按道理來講是add1要比add2快,但我這裡為什麼說add2要快呢?我們可以看一下彙編級別的代碼:
我們通過執行 gcc -O0 -S add1.c 優化級別為0,生成彙編代碼:
同理通過執行 gcc -O0 -S add2.c 優化級別為0,生成彙編代碼:
很明顯,add2的乘法指令被轉換成一次加法指令了,雖然乘法指令確實比加法指令慢。但是要注意這裡是乘以2,如果倍數大於2,那就不一定了。
因此,如果編譯器要優化add1,我們可以認為add2是其優化後的代碼。但實際上真的是這樣嗎?如果 xp 等於 yp,那麼變成如下:
void add1(int *xp,int *xp){ *xp += *xp; *xp += *xp; }
和
void add2(int *xp,int *xp){ *xp += 2* *xp;}
我們可以看到,這個時候對於 add1,xp的值會增加 4 倍,但是 add2 當中,xp 的值只增加 3 倍。由於編譯器不知道參數 xp 和 yp 是否相等,它必須假定他們有可能相等,所以不會產生 add2 作為 add1 的優化版本。
在各種編譯器中,我們前面說過的 gcc 編譯器,可以通過加參數O0 -->> O1 -->> O2 -->> O3,分別是從沒有優化到優化級別最高。但是基本上編譯器都不會對程序進行各種激進的優化,所以程序員必須以一種簡化編譯器生成高效代碼的任務來編寫程序。如何編寫,請接著往下面看。
3、程序的性能表示
處理器活動的順序是由時鐘控制的,時鐘提供了某個頻率的規律信號,通常用千兆赫茲(GHz),即十億周期每秒來表示。例如,當表明一個系統有「4GHz」處理器,這表示處理器時鐘運行頻率為 4*109 千兆赫茲。每個時鐘周期的時間是時鐘頻率的倒數。通常用納秒(nanosecond,1 納秒等於10-9秒),或者皮秒(picosecond,1 皮秒等於10-12秒)來表示,一個 4GHz 的十周周期為0.25納秒,或者說250皮秒。從程序員的角度來看,用時鐘周期來表示度量標準要比用納秒或者皮秒來表示有用的多。
用時鐘周期來表示,度量值表示的是執行了多少條指令,而不是時鐘運行的有多快。
4、提高程序的性能方法
這本書的作者講解如何優化程序性能主要從兩個方面入手,第一個是與機器無關,第二個是與機器相關。
與機器無關:
①、消除循環的低效率:將每次循環中執行多次但計算結果不改變的部分提出循環,這樣只需計算一次,而不用循環一次,計算一次。以此提高演算法效率。
②、減少過程調用:也就是減少函數方法的調用,因為函數方法的調用會帶來相當大的開銷。但是這樣也會帶來一個缺點,就是破壞程序的模塊化,所以我們需要權衡利弊。
③、消除不必要的存儲器引用:在循環中不停地對指針所指向的變數賦值的時候,我們可以用一個中間變數代替指針,以增加速度。
④、選擇合適的演算法和數據結構:為遇到的問題選擇合適的演算法和數據結構,避免使用產生糟糕性能的演算法或編碼技術。
與機器相關:
①、理解現代處理器
在代碼級上,看上去似乎是一次執行條指令,每條指令都從寄存器或存儲器中取值,執行一個操作後,並把結果存到一個寄存器或存儲器位置。但是實際上,在處理器中是同時對多條指令求值,稱為指令級並行。現代微處理器了不起的成就就是它們採用複雜而奇異的微處理結構,多條指令可以並行執行,同時又呈現出一種簡單的順序執行指令的表象。
當一系列操作必須按照嚴格的順序執行時,就會遇到延遲界限,因為在下一條指令開始之前,這條指令必須結束。當代碼中的數據相關限制令處理器利用指令級並行的能力時,延遲界限能夠限定程序性能。吞吐量界限刻畫了處理器功能單元的原始計算能力。這個界限是程序性能的終極限制。
下圖是一個現代微處理器的簡化示意圖:
指令控制單元(Instruction Control Unit,ICU)從指令高速緩存(instruction cache)中讀取指令,併產生一系列基本操作。指令高速緩存是一個特殊的高速緩存存儲器,它存儲最近訪問的指令。通常ICU會在當前正在執行的指令很早之前取指,這樣它才有足夠的時間對指令解碼,並把操作發給執行單元 EU(Execution Unit ,EU),然後由EU完成ICU產生的基本操作。
②、提高並行性
循環分割,利用功能單元的流水線化的能力提高代碼性能。對於一個可結合和可交換的合併操作來說,比如說整數加法和乘法,我們可以通過將一組合併操作分割成兩個或更多的部分,通過在最後合併結果來提高性能。
推薦閱讀:
※把文本格式的HEX文件轉換為二進位文件
※Python中用Decorator來簡化元編程的教程
※編程,在這一刻溫暖人心!!!
※簡單易用的樹莓派平板 帶你快速入門計算機編程