處理展開的循環餘數

我想問的貢獻上做手腳來處理展開的循環剩菜，有告誡說，循環是相當小的，1-3倍的展開因素，如：

EG。 B的給定的展開因素

int i = 0; 
for (; i < N-N%B; i += B) { 
    ... 
} 
// remainder 
for (; i < N; ++i) { 
    ... 
}

如果B 2，我可以做到以下幾點：

// remainder 
if (N%2) { 
    .... 
}

但是，什麼是處理B>2

2012-03-15 Anycorn

很難看到爲什麼需要一個技巧，你循環N/B次，其餘部分是N％B。你通常會把它留給代碼生成器，它已經知道如何展開循環。 – 2012-03-15 20:11:32

那麼總是有* [Duff's device]（http://en.wikipedia.org/wiki/Duff's_device）*，但是你的代碼沒有問題。 – 2012-03-15 20:57:30

在C或任何語言？在某些彙編語言中，預測的指令對此很有幫助。 – harold 2012-03-15 22:40:18

你if (N%2)可以很容易地擴展到一個好辦法任何展開因子：

for (; i < N-B+1; i += B) { 
    x1; x2; ... xB; 
} 
if (i < N) { 
    x1; 
if (i < N-1) { 
    x2; 
    ... 
if (i < N-B+2) { 
    xB; 
}}}

對於較小的展開因子，這可能是比第二回路或達夫的設備更有效率。

該版本看起來更好。 GCC 4.6編譯幾乎相同的代碼出來的：

if (i++ < N) { 
    x1; 
if (i++ < N) { 
    x2; 
    ... 
if (i++ < N) { 
    xB; 
}}}

而且這個版本可能是更理想的，如果B是二的冪。至少gcc爲它編譯更好的代碼。如果N是一個常數，它絕對是最好的。但是，如果既不N是一個常數，也不B是二的冪，利用這種方法不是那麼明顯，因爲效率較低剩餘計算的（這意味着通常是幾個指令，包括乘法）：

if (N%B > B-2) { 
    x1; 
if (N%B > B-3) { 
    x2; 
    ... 
if (N%B > 0) { 
    xB; 
}}}

2012-03-16 12:49:27

回答