-
循環展開
鎖定
循環展開，英文中稱（Loop unwinding或loop unrolling），是一種犧牲程序的尺寸來加快程序的執行速度的優化方法。可以由程序員完成，也可由編譯器自動優化完成。
- 中文名
- 循環展開
- 外文名
- loop unrolling
- 定 義
- 是一種犧牲程序的尺寸
- 優 點
- 展開循環的好處
- 缺 點
- 展開過度或展開非常大的循環時
循環展開定義
循環展開優缺點
展開循環的好處
由於展開能夠消除分支以及一些管理歸納變量的代碼，因此可以攤銷一些分支開銷。
展開可以積極調度（或管道化）循環以掩蓋一些延遲。如果有足夠的空閒寄存器使變量保持活動狀態，因為通過展開相關性鏈展露了關鍵路徑，這將非常有用。
如果迭代次數是可預測的，並且循環中沒有條件分支，則英特爾(R) 奔騰(R) 4 處理器可以正確預測迭代次數為 16 次或更少的內部循環的退出分支。因此，如果循環體不是太大，並且已知可探測的迭代次數，則可以展開內部循環，直到它們的迭代次數達到最大值 16。對於奔騰 III 或奔騰 II 處理器，請不要展開迭代次數大於 4 的循環。
展開循環的可能開銷
通常增加程序代碼大小可能是不合需要的，特別是對於嵌入式應用程序。 也可能導致指令緩存未命中增加，這可能會對性能產生負面影響。
除非優化編譯器透明地執行，否則代碼可能會變得不那麼可讀。
如果循環體中的代碼涉及函數調用，則可能無法將展開與內聯組合，因為代碼大小的增加可能過多。 因此，可以在兩個優化之間進行權衡。
除了非常小而簡單的代碼之外，包含分支的展開循環甚至比遞歸更慢。
循環展開靜態循環展開
手動（或靜態）循環展開涉及程序員分析循環並將迭代解釋為一系列指令，這將減少循環開銷。 這與由編譯器完成的動態展開形成對比。
C中的簡單手動示例
計算機程序中的過程是從集合中刪除100個項目。 這通常是通過調用函數delete（item_number）的for循環來完成的。 如果要優化程序的這一部分，並且與delete（x）循環相比，循環的開銷需要大量資源，則可以使用展開來加速它。
正常循環
int x;
for (x = 0; x < 100; x++)
{
delete(x);
}
循環展開後
int x;
for (x = 0; x < 100; x += 5 )
{
delete(x);
delete(x + 1);
delete(x + 2);
delete(x + 3);
delete(x + 4);
}
這種修改的結果，新程序只需要進行20次迭代，而不是100次。之後，只需要採用20%的跳轉和條件分支，並且在多次迭代中表示可能顯着減少。循環管理開銷。為了產生最佳效益，不應在需要指針運算的展開代碼中指定變量。這通常需要“基礎加偏移”尋址，而不是索引引用。
另一方面，這個手動循環展開將源代碼大小從3行擴展到7，必須生成，檢查和調試，並且編譯器可能必須分配更多寄存器來在擴展循環迭代中存儲變量。此外，必須仔細選擇循環控制變量和展開的循環結構內的操作數，以便結果確實與原始代碼中的相同（假設這是對已經工作的代碼的後續優化）。例如，考慮迭代計數不能被5整除的含義。如果測試條件是變量，則所需的手動修正也會變得更復雜。另見Duff的設備。
循環展開動態展開
由於循環展開的好處經常取決於數組的大小 - 這通常在運行時才知道 - JIT編譯器（例如）可以確定是否調用“標準”循環序列或者生成（相對較短） ）每個元素的單個指令序列。這種靈活性是即時技術與循環展開環境中的靜態或手動優化相比的優勢之一。在這種情況下，它通常具有相對較小的n值，其中節省仍然有用 - 需要非常小的（如果有的話）整體增加程序大小（可能僅包括一次，作為標準庫的一部分）。
彙編語言程序員（包括優化編譯器編寫器）也能夠從動態循環展開技術中受益，使用類似於用於高效分支表的方法。這裏的優勢是最大的，其中特定數組中任何引用字段的最大偏移量小於可在機器指令中指定的最大偏移量（如果超出則將由彙編程序標記）。
下面的示例演示了用C編寫的簡單程序的動態循環展開。與上面的彙編程序示例不同，在此示例中，編譯器仍然生成指針/索引算法，因為變量（i）仍用於尋址數組元素。 只有在替換語句中使用絕對索引時，才能進行完全優化。
#include <stdio.h>
/* The number of entries processed per loop iteration. */
/* Note that this number is a 'constant constant' reflecting the code below. */
#define BUNCHSIZE (8)
int main(void)
{
int i = 0; /* counter */
int entries = 50; /* total number to process */
int repeat; /* number of while repetitions*/
int left = 0; /* remainder (process later) */
/* If the number of elements is not be divisible by BLOCKSIZE, */
/* get repeat times required to do most processing in the while loop */
repeat = (entries / BUNCHSIZE); /* number of times to repeat */
left = (entries % BUNCHSIZE); /* calculate remainder */
/* Unroll the loop in 'bunches' of 8 */
while (repeat--)
{
printf("process(%d)\n", i );
printf("process(%d)\n", i + 1);
printf("process(%d)\n", i + 2);
printf("process(%d)\n", i + 3);
printf("process(%d)\n", i + 4);
printf("process(%d)\n", i + 5);
printf("process(%d)\n", i + 6);
printf("process(%d)\n", i + 7);
/* update the index by amount processed in one go */
i += BUNCHSIZE;
}
/* Use a switch statement to process remaining by jumping to the case label */
/* at the label that will then drop through to complete the set */
switch (left)
{
case 7 : printf("process(%d)\n", i + 6); /* process and rely on drop
through */
case 6 : printf("process(%d)\n", i + 5);
case 5 : printf("process(%d)\n", i + 4);
case 4 : printf("process(%d)\n", i + 3);
case 3 : printf("process(%d)\n", i + 2);
case 2 : printf("process(%d)\n", i + 1); /* two left */
case 1 : printf("process(%d)\n", i); /* just one left to process */
case 0 : ; /* none left */
}
}
