這些技巧是在書上面看到的，跟大家分享。


假設現在要做一個整數陣列a的加總，如果已知陣列長度為100的話，

最簡單的寫法是。

for ( i = 0; i < 100; ++i )
sum += a[ i ];

但是這樣會做100次的 i < 100 的判斷，增加branch降低效率，所

以loop unrolling的技巧就是在迴圈內部多做幾次，減少判斷的次

數。

for ( i = 0; i < 100; i += 5 ) {
sum += a[ i ];
sum += a[ i + 1 ];
sum += a[ i + 2 ];
sum += a[ i + 3 ];
sum += a[ i + 4 ];
}

（當然可以乾脆展開100次，所有的判斷都省了，但是這樣做會加大
程式碼的長度，對效率也會有影響，而且完全沒彈性）

這是在已知長度是100的情況下才能做的，因為我們知道100是5的倍

數，但是如果情況變成要對任意的陣列長度n都可以適用，就得寫成。

for ( i = 0; i < n % 5; ++i ) // 先把n % 5的餘數做完
sum += a[ i ];
for ( ; i < n; i += 5 ) { // 剩下的迴圈數一定是5的倍數了
sum += a[ i ];
sum += a[ i + 1 ];
sum += a[ i + 2 ];
sum += a[ i + 3 ];
sum += a[ i + 4 ];
}

不過Duff's device的技巧就是可以把這兩個迴圈融合在一起。

i = 0;
switch ( n % 5 ) {
case 0: do {sum += a[ i++ ];
case 4: sum += a[ i++ ];
case 3: sum += a[ i++ ];
case 2: sum += a[ i++ ];
case 1: sum += a[ i++ ];
} while ((n -= 5) > 0);
}

這邊是用switch-case跳到do-while的迴圈之中。


回到一開始的loop unrolling的版本

for ( i = 0; i < 100; i += 5 ) {
sum += a[ i ];
sum += a[ i + 1 ];
sum += a[ i + 2 ];
sum += a[ i + 3 ];
sum += a[ i + 4 ];
}

其實這程式等價於

for ( i = 0; i < 100;) {
sum += a[ i++ ];
sum += a[ i++ ];
sum += a[ i++ ];
sum += a[ i++ ];
sum += a[ i++ ];
}

但是這樣做會讓造成前後兩個指令之間在i上的相依性，沒辦法完全

利用到CPU的pipeline。用前者會稍微比較好，不過實際上sum也是

造成相依性的來源，所以可以改寫成

for ( i = 0; i < 100; i += 5 ) {
sum1 += a[ i ];
sum2 += a[ i + 1 ];
sum1 += a[ i + 2 ];
sum2 += a[ i + 3 ];
sum1 += a[ i + 4 ];
}
sum = sum1 + sum2;

這技巧也能和Duff's device同時使用，只是有沒有辦法增加效率就

要試試看才知道。


上面這些程式碼都只是示意，迴圈要展開幾次，要用多少個變數來

加總才能達成最高效率，與硬體實作部份有很大的關係，只能慢慢

的作測試。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51
※ 編輯: FRAXIS 來自: 140.119.162.51 (06/29 07:59)