[心得] Loop unrolling, Duff's device

看板C_and_CPP (C/C++)作者FRAXIS (喔喔)時間16年前 (2009/06/27 10:50)推噓6(6推 0噓 24→)

留言30則, 7人參與討論串1/2 (看更多)

這些技巧是在書上面看到的，跟大家分享。假設現在要做一個整數陣列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

06/27 10:54, , 1^F

06/27 10:54, 1^F

→

MOONRAKER

06/27 10:55, , 2^F

06/27 10:55, 2^F

→

tinlans

06/27 11:35, , 3^F

06/27 11:35, 3^F