[心得] Loop unrolling, Duff's device

[FRAXIS (喔喔)]

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


假設現在要做一個整數陣列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
→ MOONRAKER:不是在寫asm又不是在沒最佳化能力的compiler上實作的
→ MOONRAKER:前提下，何時需要這種手動最佳化？
→ tinlans:compiler 會自己做，還會幫你選該 unroll 或做 SWP。
→ FRAXIS:我只是在研究Duff's device的語法  沒有想那麼多..
→ MOONRAKER:那是叫logic，或flow，或pattern，不叫語法(syntax)
→ MOONRAKER:if後面要有小括號這種事情才叫語法
→ FRAXIS:其實我要表達的是 Duff's device使用到的語法
→ FRAXIS:用switch跳到迴圈內部  是否還有其他什麼用途？
推 Song6Lin:可以請問一下是什麼書嗎？
→ Song6Lin:我覺得duff's device的用法好神奇喔。
推 VictorTom:乍看之下是很有趣的用法, compiler的實作上或許也會用到
→ VictorTom:類似的概念, 但老實說小弟覺得這東西拿來研究或特定領域
→ VictorTom:與用途實作還行, 一般自己或工作上我一點都不想看到這種
→ VictorTom:寫法....Orz
→ VictorTom:考慮CPU/pipeline最佳化, 其實這種簡單迴圈判斷現在應該
→ VictorTom:predict都有不錯的效果; 最佳化應該考慮CPU與平台的特性
→ VictorTom:來作, 不一定換個方向用i>=0, 用--i取代i--等還比較易懂
→ VictorTom:也易除錯吧我想@_@"
→ VictorTom:看到加總另外說一下, 以前老師還說, 要安全的加總, 在已
→ VictorTom:知結果不會爆的情況, 可能也要先對資料排序好, 再抓頭抓
→ VictorTom:尾來加, 避免中間過程可能加爆; 比如特有錢人記收入支出
→ VictorTom:, 不過這已經無關效率最佳化就是了:)
推 ckclark:樓上說的加總例子可以舉一個會結果不同的嗎
※ 編輯: FRAXIS          來自: 140.119.162.51       (06/29 07:59)
推 VictorTom:忽然發現隨便想了幾個例子好像真的讓它爆了也沒差Orz
→ VictorTom:特地試了一下好像爆了也不會寫壞其他變數空間....
→ VictorTom:大概現在這東西比較不用care了吧....@_@"
→ FRAXIS:或許是浮點數相加？  按照某種順序加比較可以避免誤差？
推 VictorTom:Hmm~~浮點數處理難度又更大了說....Orz
→ FRAXIS:要不然就是有正負數..  讓正負相消避免溢位..
推 mabus:這個還蠻有趣的。