《深入理解計算機系統》（CSAPP）讀書筆記 —— 第五章 優化程式性能

寫程式最主要的目標就是使它在所有可能的情況下都正確作業，一個運行得很快但是給出錯誤結果的程式沒有任何用處，程式員必須寫出清晰簡潔的代碼，這樣做不僅是為了自己能夠看懂代碼，也是為了在檢査代碼和今后需要修改代碼時，其他人能夠讀懂和理解代碼，另一方面，在很多情況下，讓程式運行得快也是一個重要的考慮因素，本章主要介紹了回圈展開，減小程序呼叫，消除不必要的記憶體參考等優化代碼的方法，有助于我們寫出高效的代碼，提高代碼的性能，

• 優化編譯器的能力和局限性
  • GCC優化指令
  • 記憶體別名使用
• 表示程式性能
• 程式示例
• 消除回圈的低效率(Code Motion)
• 減少程序呼叫
• 消除不必要的記憶體參考
• 理解現代處理器
  • 整體操作
    • 基本概念
• 回圈展開
• 提高并行性
  • 多個累積變數
  • 重新結合變換
• 一些限制因素
  • 暫存器溢位
  • 分支預測何預測錯誤懲罰
• 理解記憶體性能
  • 加載的性能
• 性能提高技術
• 總結

??1.合適的演算法和資料結構

??2.撰寫出編譯器能夠有效優化以轉換成高效可執行代碼的源代碼（例如，在C語言中，指標運算和強制型別轉換使得編譯器很難對它進行優化），

??3.針對處理運算量特別大的計算，將一個任務分成多部分，即利用并行性，

優化編譯器的能力和局限性

GCC優化指令

??-Og:默認配置，不優化，

??-O1:編譯器試圖優化代碼大小和執行時間，它主要對代碼的分支，常量以及運算式等進行優化，但不執行任何會占用大量編譯時間的優化，

??-O2:GCC執行幾乎所有不包含時間和空間權衡的優化（比如，嘗試更多的暫存器級的優化以及指令級的優化），與-O相比，此選項增加了編譯時間，但提高了代碼的效率，

??-O3:比-O2更優化，對于-O3編譯選項，在-O2的基礎上，打開了更多的優化項（比如，使用偽暫存器網路，普通函式的行內，以及針對回圈的更多優化），不過可能導致編譯出來的二級制程式不能debug，

??-Os:主要是對代碼大小的優化，我們基本不用做更多的關心， 通常各種優化都會打亂程式的結構，讓除錯作業變得無從著手，并且會打亂執行順序，依賴記憶體操作順序的程式需要做相關處理才能確保程式的正確性，

記憶體別名使用

??兩個指標可能指向同一個記憶體位置的情況成為記憶體別名使用，

void twiddle1 (long *xp,long*yp)
{
	*xp+ = *yp;
	*xp+ = *yp;
}
void twiddle2(long *xp,long*yp)
{
	*xp+ = 2 * *yp;
}

twiddle1它們都是將存盤在由指標yp指示的位置處的值兩次加到指標xp指示的位置處的值，twiddle2需要3次記憶體參考（讀* xp，讀yp，寫* xp）， twiddle1需要6次（2次讀* xp，2次讀yp，2次寫* xp），一般，我們認為twiddle2要優于twiddle2，那么將twiddle1優化是不是就能產生類似twiddle2的代碼了？

答案顯然是不可以的，當 *xp == *yp 時，twiddle1執行后的結果是：xp的值增加4倍，而twiddle2的結果是xp的值增加3倍，因此，兩個程式是有本質差別的，

以上這個例子就介紹了記憶體別名使用，編譯器在優化時，并不知道*xp 和 *yp是否相等，只能假設他們不相等，即xp和yp指標不會指向同一位置，

表示程式性能

??程式性能度量標準：每元素的周期數（Cycles Per Element，CPE），

??處理器活動的順序是由時鐘控制的，時鐘提供了某個頻率的規律信號，通常用千兆赫茲（GHz），即十億周期每秒來表示，例如，當表明一個系統有“4GHz”處理器，這表示處理器時鐘運行頻率為每秒\(4 \times {10^9}\)個周期，每個時鐘周期的時間是時鐘頻率的倒數，通常是以納秒（ nanosecond，1納秒等于\({10^{ - 8}}\)秒）或皮秒（ picosecond，1皮秒等于\({10^{ - 12}}\)秒）為單位的，例如，一個4GHz的時鐘其周期為0.25納秒，或者250皮秒，從程式員的角度來看，用時鐘周期來表示度量標準要比用納秒或皮秒來表示有幫助得多，用時鐘周期來表示，度量值表示的是執行了多少條指令，而不是時鐘運行得有多快，

程式示例

消除回圈的低效率(Code Motion)

??舉個例子如下所示：

void lower1(char *s)
{
  size_t i;
  for (i = 0; i < strlen(s); i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
      s[i] -= ('A' - 'a');
}

??程式看起來沒什么問題，一個很平常的大小寫轉換的代碼，但是為什么隨著字串輸入長度的變長，代碼的執行時間會呈指數式增長呢？我們把程式轉換成GOTO形式看下，

void lower1(char *s)
{
   size_t i = 0;
   if (i >= strlen(s))
     goto done;
 loop:
   if (s[i] >= 'A' && s[i] <= 'Z')
       s[i] -= ('A' - 'a');
   i++;
   if (i < strlen(s))
     goto loop;
 done:
}

??我們可以看到，在C語言中呼叫strlen一次，這個函式實際上會執行兩次，還有一個重要的原因是：字串的長度并不會隨著回圈的進行而改變，因此，我們可以把strlen放在回圈外，避免每次都呼叫strlen進行計算，

因為C語言中的字串是以null結尾的字符序列，strlen必須一步一步地檢查這個序列，直到遇到null字符，對于一個長度為n的字串，strlen所用的時間與n成正比，因為對lower1的n次迭代的每一次都會呼叫strlen，所以lower1的整體運行時間是字串長度的二次項，正比于\({n^2}\)，

??優化后的代碼如下所示：

void lower2(char *s)
{
  size_t i;
  size_t len = strlen(s);           /*放在函式體外*/
  for (i = 0; i < len; i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
      s[i] -= ('A' - 'a');
}

??二者的執行效率比較如下所示：

??這種優化是常見的一類優化的方法，稱為代碼移動（Code motion），這類優化包括識別要執行多次（例如在回圈里）但是計算結果不會改變的計算，因而可以將計算移動到代碼前面不會被多次求值的部分，

減少程序呼叫

/* Move call to vec_length out of loop */
void combine2 (vec_ptr v, data_t *dest)
{
	long i;
	long length vec_length(v);
	*dest = IDENT;
	for (i=0;i< length;i++)
	{
		data_t val;
		get_vec_element(v,i,&val);
		*dest = *dest OP val;
	}
}

??從combine2的代碼中我們可以看出，每次回圈迭代都會呼叫get_vec_element來獲取下一個向量元素，對每個向量參考，這個函式要把向量索引i與回圈邊界做比較，很明顯會造成低效率，在處理任意的陣列訪問時，邊界檢查可能是個很有用的特性，但是對 combine2代碼的簡單分析表明所有的參考都是合法的，

data_t *get_vec_start(vec_ptr v)
{
	return v-data;
}
/* Move call to vec_length out of loop */
void combine3 (vec_ptr v, data_t *dest)
{
	long i;
	long length vec_length(v);
    data_t *data = https://www.cnblogs.com/dongxb/p/get_vec_start(v);
	*dest = IDENT;
	for (i=0;i< length;i++)
	{
		*dest = *dest OP data[i];
	}
}

??作為替代，假設為我們的抽象資料型別增加一個函式get_vec_start，這個函式回傳陣列的起始地址，然后就能寫出此combine3所示的程序，其內回圈里沒有函式呼叫，它沒有用函式呼叫來獲取每個向量元素，而是直接訪問陣列，

??事實上，經過這一步后，并沒有使得性能有較大提升，后面會詳細講到，這只是我們優化路上的一步，

消除不必要的記憶體參考

#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax 
.L17:
vmovsd (%rbx),%xmm()           # Read product from dest 
vmulsd (%rdx),%xmm0,%xmm0      # Multiply product by data[i]
vmovsd %xmm, (%rbx）           # Store product at dest
addq $8,%rdx                   # Increment data+i
cmp %rax,%rdx                  # Compare to data+length 
jne .L17

??在這段回圈代碼中，我們看到，指標dest的地址存放在暫存器%rbx中，它還改變了代碼，將第i個資料元素的指標保存在暫存器%rdx中，注釋中顯示為data+i，每次迭代，這個指標都加8，回圈終止操作通過比較這個指標與保存在暫存器各ax中的數值來判斷，我們可以看到每次迭代時，累積變數的數值都要從記憶體讀出再寫入到記憶體，這樣的讀寫很浪費，因為每次迭代開始時從dest讀出的值就是上次迭代最后寫入的值，

??我們能夠消除這種不必要的記憶體讀寫， combine4所示的方式如下，引入一個臨時變數acc，它在回圈中用來累積計算出來的值，只有在回圈完成之后結果才存放在dest中，正如下面的匯編代碼所示，編譯器現在可以用暫存器%xmm0來保存累積值，

#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax 
.L25:
vmulsd (%rdx),%xmm0,%xmm0      # Multiply product by data[i]
addq $8,%rdx                   # Increment data+i
cmp %rax,%rdx                  # Compare to data+length 
jne .L25

void combine4 (vec_ptr v, data_t *dest)
{
	long i;
	long length vec_length(v);
    data_t *data = https://www.cnblogs.com/dongxb/p/get_vec_start(v);
	*data acc = IDENT;
	for (i=0;i< length;i++)
	{
		acc = acc OP data[i];
	}
	*dest = acc;
}

??把結果累積在臨時變數中，將累積值存放在區域變數acc（累積器（ accumulator）的簡寫）中，消除了每次回圈迭代中從記憶體中讀出并將更新值寫回的需要，

??程式性能如下（以int整數為例），單位為CPE，

理解現代處理器

整體操作

基本概念

??超標量（superscalar）：在每個時鐘周期執行多個操作

??亂序（out-of-order）：指令執行的順序不一定要與它們在機器級程式中的順序一致

??如上圖所示，為一個亂序處理器的框圖，整個設計有兩個主要部分：指令控制單元（ Instruction Control Unit,ICU）和執行單元（ Execution Unit,EU），前者負責從記憶體中讀出指令序列，并根據這些指令序列生成一組針對程式資料的基本操作；而后者執行這些操作，

??指令高速快取（Instruction cache）：一個特殊的高速存盤器，它包含最近訪問的指令，

??分支預測（branch prediction）：處理器會猜測是否會選擇分支，同時還預測分支的目標地址，使用投機執行（ speculative execution）的技術，處理器會開始取出位于它預測的分支，會跳到的地方的指令，并對指令譯碼，甚至在它確定分支預測是否正確之前就開始執行這些操作，如果過后確定分支預測錯誤，會將狀態重新設定到分支點的狀態，并開始取出和執行另一個方向上的指令，標記為取指控制的塊包括分支預測，以完成確定取哪些指令的任務，

??指令譯碼邏輯：一條指令會被譯碼成多個操作，例如，addq %rax,8(%rdx)，，這條指令會被譯碼成為三個操作：一個操作從記憶體中加載一個值到處理器中，一個操作將加載進來的值加上暫存器%rax中的值,而一個操作將結果存回到記憶體，

??讀寫記憶體是由加載和存盤單元實作的，加載單元處理從記憶體讀資料到處理器的操作，這個單元有一個加法器來完成地址計算，類似，存盤單元處理從處理器寫資料到記憶體的操作，它也有一個加法器來完成地址計算，如圖中所示，加載和存盤單元通過資料高速快取（ data cache）來訪問記憶體，資料高速快取是一個高速存盤器，存放著最近訪問的資料值，

??退役單元（ retirement unit）:記錄正在進行的處理，并確保它遵守機器級程式的順序語意，退役單元控制這些暫存器的更新，指令譯碼時，關于指令的資訊被放置在一個先進先出的佇列中，這個資訊會一直保持在佇列中，直到發生以下兩個結果中的一個，首先，一旦一條指令的操作完成了，而且所有引起這條指令的分支點也都被確認為預測正確，那么這條指令就可以退役（ retired）了，所有對程式暫存器的更新都可以被實際執行了，另一方面，如果引起該指令的某個分支點預測錯誤，這條指令會被清空（ flushed），丟棄所有計算出來的結果，通過這種方法，預測錯誤就不會改變程式的狀態了，(任何對程式暫存器的更新都只會在指令退役時才會發生)

??暫存器重命名（ register renaming）：當一條更新暫存器r的指令譯碼時，產生標記t，得到一個指向該操作結果的唯一的識別符號，條目（r,t）被加入到一張表中，該表維護著每個程式暫存器r與會更新該暫存器的操作的標記t之間的關聯，當隨后以暫存器r作為運算元的指令譯碼時，發送到執行單元的操作會包含t作為運算元源的值，當某個執行單元完成第一個操作時，會生成一個結果（v,t），指明標記為t的操作產生值v，所有等待t作為源的操作都能使用v作為源值，這就是一種形式的資料轉發，通過這種機制，值可以從一個操作直接轉發到另一個操作，而不是寫到暫存器檔案再讀出來，使得第二個操作能夠在第一個操作完成后盡快開始，重命名表只包含關于有未進行寫操作的暫存器條目，當一條被譯碼的指令需要暫存器r，而又沒有標記與這個暫存器相關聯，那么可以直接從暫存器檔案中獲取這個運算元，有了暫存器重命名，即使只有在處理器確定了分支結果之后才能更新暫存器，也可以預測著執行操作的整個序列，

??延遲（ latency）：它表示完成運算所需要的總時間，

??發射時間（ Issue time）：它表示兩個連續的同型別的運算之間需要的最小時鐘周期數，(發射時間為1：完全流水線化)

浮點數加法器流水線化分為三個階段：一個階段處理指數值，一個階段將小數相加，而另一個階段對結果進行舍入，

??容量（ capacity）：它表示能夠執行該運算的功能單元的數量，

??延遲界限：完成合并運算的函式所需要的最小CPE值，

??最大吞吐量：發射時間的倒數，給出了CPE的最小界限，

回圈展開

??回圈展開是一種程式變換，通過增加每次迭代計算的元素的數量，減少回圈的迭代次數，回圈展開能夠從兩個方面改行程式的性能，首先，它減少了不直接有助于程式結果的操作的數量，例如回圈索引計算和條件分支，第二，它提供了一些方法，可以進一步變化代碼，減少整個計算中關鍵路徑上的運算元量，

/*2 * 1 loop unrolling*/
/*使用2×1回圈展開，這種變換能減小回圈開銷的影響*/
void combine5(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length-1;
    data_t *data = https://www.cnblogs.com/dongxb/p/get_vec_start(v);
    data_t acc = IDENT;
    
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		acc = (acc OP data[i]) OP data[i+1];
    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
		acc = acc OP data[i];
    }
    *dest = acc;
}

??上述代碼是使用的”2 * 1回圈展開“的版本，第一個回圈每次處理陣列的兩個元素，也就是每次迭代，回圈索引i加2，在一次迭代中，對陣列元素i和i+1使用合并運算，（注意訪問不要越界，正確設定limit，n個元素，一般設定界限n-1），

??\(K \times 1\)回圈展開次數和性能提升并不是正比關系，一般來講，最多回圈展開一次后，性能提升就不會很大了（主要原因是關鍵路徑中n個mul操作，迭代次數減半，但是每次迭代中還是有兩個順序的乘法操作，具體參考P367），

提高并行性

多個累積變數

??\({P_n}\)表示\({a_0},{a_1} \cdots {a_n}\) 乘積：${P_n} = \sum\limits_{i = 0}^{n - 1} {{a_i}} \(，假設n為偶數，我們還可以把它寫成\){P_n} = P{E_n} \times P{O_n}\(,這里\)P{E_n}\(是索引為偶數的元素的乘積，而\)P{O_n}$是索引值為奇數的元素的乘積，

??代碼如下：

/*2 * 2 loop unrolling*/
/*運用2×2回圈展開，通過維護多個累積變數，這種方法利用了多個功能單元以及它們的流水線能力*/
void combine6(vec_ptr v, data_t *dest)
{
	long i;
    long length = vec_length(v);
    long limit = length-1;
    data_t *data = https://www.cnblogs.com/dongxb/p/get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;
    
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		acc0 = acc0 OP data[i];
		acc1 = acc1 OP data[i+1];
    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
        acc0 = acc0 OP data[i];
    }
    *dest = acc0 OP acc1;
}

??上述代碼用了兩次回圈展開，以使每次迭代合并更多的元素，也使用了兩路并行，將索引值為偶數的元素累積在變數acc0中，而索引值為奇數的元素累積在變數acc1中，因此，我們將其稱為”2×2回圈展開”，同前面一樣，我們還包括了第二個回圈，對于向量長度不為2的倍數時，這個回圈要累積所有剩下的陣列元素，然后，我們對acc0和acc1應用合并運算，計算最終的結果，

??事實上，combine6比combine5性能提升近2倍左右，

重新結合變換

/*2 * 1a loop unrolling*/
/*運用2×1a回圈展開，重新結合合并操作，這種方法增加了可以并行執行的運算元量*/
void combine7(vec_ptr v, data_t *dest)
{
	long i;
    long length = vec_length(v);
    long limit = length-1;
    data_t *data = https://www.cnblogs.com/dongxb/p/get_vec_start(v);
    data_t acc = IDENT;
    
    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i+=2) {
		acc = acc OP (data[i] OP data[i+1]);
    }
    /* Finish any remaining elements */
    for (; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

??我們可以看到關鍵路徑上只有n/2個操作，每次迭代內的第一個乘法都不需要等待前一次迭代的累積值就可以執行，因此，最小可能的CPE減少了2倍，這種改進方式幾乎達到了吞吐量的極限，

??在執行重新結合變換時，我們又一次改變向量元素合并的順序，對于整數加法和乘法，這些運算是可結合的，這表示這種重新變換順序對結果沒有影響，對于浮點數情況，必須再次評估這種重新結合是否有可能嚴重影響結果，我們會說對大多數應用來說，這種差別不重要，

??總的來說，重新結合變換能夠減少計算中關鍵路徑上操作的數量，通過更好地利用功能單元的流水線能力得到更好的性能，大多數編譯器不會嘗試對浮點運算做重新結合，因為這些運算不保證是可結合的，當前的GCC版本會對整數運算執行重新結合，但不是總有好的效果，通常，我們發現回圈展開和并行地累積在多個值中，是提高程式性能的更可靠的方法，

Intel在199年引入了SSE指令，SSE是“ Streaming SIMD Extensions（流SIMD擴展）”的縮寫，而SIMD（讀作“ sim-dee”）是“ Single-In-Struction, Multiple-Data（單指令多資料）”的縮寫，SSE功能歷經幾代，最新的版本為高級向量擴展（ advanced vector extension）或AVX，SIMD執行模型是用單條指令對整個向量資料進行操作，這些向量保存在一組特殊的向量暫存器（ vector register）中，名字為號%ymm0~%ymm15，目前的AVX向量暫存器長為32位元組，因此每一個都可以存放8個32位數或4個64位數，這些資料既可以是整數也可以是浮點數，AVX指令可以對這些暫存器執行向量操作，比如并行執行8組數值或4組數值的加法或乘法，例如，如果YMM暫存器%ymm0包含8個單精度浮點數，用\({a_0},{a_1} \cdots {a_n}\)表示，而%rcx包含8個單精度浮點數的記憶體地址，用\({b_0},{b_1} \cdots {b_n}\)表示，那么指令vmulps （%rcx）， %ymm0, %ymm1會從記憶體中讀出8個值，并行地執行8個乘法，計算\({a_i} \leftarrow {a_i}{b_i},0 \le i \le 7\)，并將得到的8個乘積保存到向量暫存器%ymm1，我們看到，一條指令能夠產生對多個資料值的計算，因此稱為“SIMD”，（使用SIMD指令重寫代碼可以使程式性能獲得上百倍提升）

一些限制因素

暫存器溢位

??我們可以看到對這種回圈展開程度的增加沒有改善CPE，有些甚至還變差了，現代x86-64處理器有16個暫存器，并可以使用16個YMM暫存器來保存浮點數，一旦回圈變數的數量超過了可用暫存器的數量，程式就必須在堆疊上分配一些變數，
例如，下面的代碼片段展示了在10×10回圈展開的內回圈中，累積變數acc0是如何更新的：

# Updating of accumulator acco in 10 x 10 unrolling 
vmulsd (%rdx),%xmm,%xmm0       #acc0 *=data[i]

??我們看到該累積變數被保存在暫存器%xmm0中，因此程式可以簡單地從記憶體中讀取data[i],并與這個暫存器相乘，

??與之相比，20×20回圈展開的相應部分非常不同：

# Updating of accumulator acco in 20 x 20 unrolling 
vmovsd 40(%rsp),%xmm0
vmulsd (%rdx),%xmm0,%xmm0
vmovsd %xmmO,40(%rsp)

??累積變數保存為堆疊上的一個區域變數，其位置距離堆疊指標偏移量為40，程式必須從記憶體中讀取兩個數值：累積變數的值和data[i]的值，將兩者相乘后，將結果保存回記憶體，

??一旦編譯器必須要訴諸暫存器溢位，那么維護多個累積變數的優勢就很可能消失，幸運的是，x86-64有足夠多的暫存器，大多數回圈在出現暫存器溢位之前就將達到吞吐量限制，

分支預測何預測錯誤懲罰

??現代處理器的作業遠遠超前于當前正在執行的指令，

1.不要過分關心可預測的分支

??我們已經看到錯誤的分支預測的影響可能非常大，但是這并不意味著所有的程式分支都會級訓程式的執行，實際上，現代處理器中的分支預測邏輯非常善于辨別不同的分支指令的有規律的模式和長期的趨勢，例如，在合并函式中結束回圈的分支通常會被預測為選擇分支，因此只在最后一次會導致預測錯誤處罰，

2.書寫適合用條件傳送實作的代碼

??程式中的許多測驗是完全不可預測的，依賴于資料的任意特性，例如一個數是負數還是正數，對于這些測驗，分支預測邏輯會處理得很糟糕，對于本質上無法預測的情況，如果編譯器能夠產生使用條件資料傳送而不是使用條件控制轉移的代碼，可以極大地提高程式的性能，

??我們發現GCC能夠為以一種更“功能性的”風格書寫的代碼產生條件傳送，在這種風格的代碼中，我們用條件操作來計算值，然后用這些值來更新程式狀態，這種風格對立于一種更“命令式的”風格，這種風格中，我們用條件陳述句來有選擇地更新程式狀態，

void minmax1(long a[],long b[],long n){
	long i;
	for(i = 0;i,n;i++){
	if(a[i]>b[i]){
		long t = a[i];
		a[i] = b[i];
		b[i] = t;
	}
}
}

??在隨機資料上測驗這個函式，得到的CPE大約為13.50，而對于可預測的資料，CPE為2.5其預測錯誤懲罰約為20個周期，

??用功能式的風格實作這個函式是計算每個位置i的最大值和最小值，然后將這些值分別賦給a[i]和b[i]，

void minmax2(long a[],long b[],long n){
	long i;
	for(i = 0;i,n;i++){
	long min = a[i] < b[i] ? a[i]:b[i];
	long max = a[i] < b[i] ? b[i]:a[i];
	a[i] = min;
	b[i] = max;
	
}
}

??對于這個函式的測驗表明，無論資料是任意的，還是可預測的，CPE都大約為4.0，

理解記憶體性能

加載的性能

??現代處理器有專門的功能單元來執行加載和存盤操作，這些單元有內部的緩沖區來保存未完成的記憶體操作請求集合，一個包含加載操作的程式的性能既依賴于流水線的能力，也依賴于加載單元的延遲，

??要確定一臺機器上加載操作的延遲，我們可以建立由一系列加載操作組成的一個計算，一條加載操作的結果決定下一條操作的地址，舉例如下：

typedef struct ELE{
 struct ELE *next;
 long data;
}list_ele, *list_ptr;
long list_len(list_ptr ls){
	long len = 0;
	while (ls){
	len++;
	ls = ls->next; 
	}
	return len;
} 

.L3:                       #loop
addq $1,%rax               #Increment len
moveq (%rdi),%rdi          #ls = ls->next
tesatq %rdi,%rdi           #Test ls
jne .L3                    # if nonnull,goto loop

??第3行上的movq指令是這個回圈中關鍵的瓶頸，后面暫存器%rdi的每個值都依賴于加載操作的結果，而加載操作又以%rdi中的值作為它的地址，因此，直到前一次迭代的加載操作完成，下一次迭代的加載操作才能開始，這個函式的CPE等于4.00，是由加載操作的延遲決定的，

性能提高技術

??雖然只考慮了有限的一組應用程式，但是我們能得出關于如何撰寫高效代碼的很重要的經驗教訓，總結如下：

(1)高級設計

??為遇到的問題選擇適當的演算法和資料結構，要特別警覺，避免使用那些會漸進地產生糟糕性能的演算法或編碼技術，

(2)基本編碼原則

??避免限制優化的因素，這樣編譯器就能產生高效的代碼，

??消除連續的函式呼叫，在可能時，將計算移到回圈外，考慮有選擇地妥協程式的模塊性以獲得更大的效率，

??消除不必要的記憶體參考，引入臨時變數來保存中間結果，只有在最后的值計算出來時，才將結果存放到陣列或全域變數中，

(3)低級優化

??結構化代碼以利用硬體功能，

??展開回圈，降低開銷，并且使得進一步的優化成為可能，

??通過使用例如多個累積變數和重新結合等技術，找到方法提高指令級并行，

??用功能性的風格重寫條件操作，使得編譯采用條件資料傳送，

(4)使用性能分析工具

??當處理大型程式時，將注意力集中在最耗時的部分變得很重要，代碼剖析程式和相關的工具能幫助我們系統地評價和改行程式性能，我們描述了 GPROF，一個標準的Unix剖析工具，還有更加復雜完善的剖析程式可用，例如 Intel的VTUNE程式開發系統，還有 Linux系統基本上都有的 VALGRIND，這些工具可以在程序級分解執行時間，估計程式每個基本塊（ basic block）的性能，（基本塊是內部沒有控制轉移的指令序列，因此基本塊總是整個被執行的，)

??最后要給讀者一個忠告，要警惕，在為了提高效率重寫程式時避免引入錯誤，在引人新變數、改變回圈邊界和使得代碼整體上更復雜時，很容易犯錯誤，一項有用的技術是在優化函式時，用檢查代碼來測驗函式的每個版本，以確保在這個程序沒有引入錯誤，檢查代碼對函式的新版本實施一系列的測驗，確保它們產生與原來一樣的結果，對于高度優化的代碼，這組測驗情況必須變得更加廣泛，因為要考慮的情況也更多，例如，使用回圈展開的檢査代碼需要測驗許多不同的回圈界限，保證它能夠處理最終單步迭代所需要的所有不同的可能的數字，

總結

??本章中詳細介紹了提高程式性能的一些通用方法和工具，在日常撰寫代碼的程序中，應時刻注意代碼的風格，養成良好的習慣，當處理大型程式時或者不知道優化程式的那個部分時，我們可以借助GPROF，VTUNE，VALGRIND等工具來進一步剖析程式，分析每個函式的性能，找到限制程式性能的因素，逐一解決，

有任何問題，均可通過公告中的二維碼聯系我

標籤：嵌入式

上一篇：windows10在安裝ubuntu圖形界面時出現compiz(core)-Fatal:Couldn't open display

下一篇：《深入理解計算機系統》（CSAPP）實驗四 —— Attack Lab