c++ - 如何向循環添加代碼使它的更快?

  显示原文与译文双语对照的内容

我有一個帶有內部循環的簡單函數- 它縮放輸入值,在查找表中查找輸出值,並將它複製到目標。 ( ftol_ambient是我從站點上複製的用於快速轉換到int的技巧) 。


for (i = 0; i <iCount; ++i)
{
 iScaled = ftol_ambient(*pSource * PRECISION3);
 if (iScaled <= 0)
 *pDestination = 0;
 else if (iScaled> = PRECISION3)
 *pDestination = 255;
 else
 {
 iSRGB = FloatToSRGBTable3[iScaled];
 *pDestination = iSRGB;
 }
 pSource++;
 pDestination++;
}

現在我的查找表是有限的,並且浮動是無限的,所以有可能出現off-by-one錯誤。 我用一些代碼創建了一個函數副本來處理這種情況。 注意,唯一的區別是添加了 2行代碼- 請忽略醜陋的指針轉換。


for (i = 0; i <iCount; ++i)
{
 iScaled = ftol_ambient(*pSource * PRECISION3);
 if (iScaled <= 0)
 *pDestination = 0;
 else if (iScaled> = PRECISION3)
 *pDestination = 255;
 else
 {
 iSRGB = FloatToSRGBTable3[iScaled];
 if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))
 ++iSRGB;
 *pDestination = (unsigned char) iSRGB;
 }
 pSource++;
 pDestination++;
}

下面是奇怪的部分。我測試兩個版本相同的100000個元素,重複 100次。 在我的速龍 64 1.8 GHz ( 32位模式) 上,第一個函數需要 0.231秒,第二個( 更長) 函數需要 0.185秒。 兩個函數都在同一個源文件中,因此不可能有不同的編譯器設置。 我多次運行了測試,顛倒了它們的運行順序,每次運行時間大致相同。

我知道現代處理器中有很多神秘的東西,但這怎麼可能?

這裡比較是來自微軟VC++6編譯器的相關彙編輸出。



; 173 : for (i = 0; i <iCount; ++i)

$L4455:

; 174 : {
; 175 : iScaled = ftol_ambient(*pSource * PRECISION3);

 fld DWORD PTR [esi]
 fmul DWORD PTR __real@4@400b8000000000000000
 fstp QWORD PTR $T5011[ebp]

; 170 : int i;
; 171 : int iScaled;
; 172 : unsigned int iSRGB;

 fld QWORD PTR $T5011[ebp]

; 173 : for (i = 0; i <iCount; ++i)

 fistp DWORD PTR _i$5009[ebp]

; 176 : if (iScaled <= 0)

 mov edx, DWORD PTR _i$5009[ebp]
 test edx, edx
 jg SHORT $L4458

; 177 : *pDestination = 0;

 mov BYTE PTR [ecx], 0

; 178 : else if (iScaled> = PRECISION3)

 jmp SHORT $L4461
$L4458:
 cmp edx, 4096 ; 00001000H
 jl SHORT $L4460

; 179 : *pDestination = 255;

 mov BYTE PTR [ecx], 255 ; 000000ffH

; 180 : else

 jmp SHORT $L4461
$L4460:

; 181 : {
; 182 : iSRGB = FloatToSRGBTable3[iScaled];
; 183 : *pDestination = (unsigned char) iSRGB;

 mov dl, BYTE PTR _FloatToSRGBTable3[edx]
 mov BYTE PTR [ecx], dl
$L4461:

; 184 : }
; 185 : pSource++;

 add esi, 4

; 186 : pDestination++;

 inc ecx
 dec edi
 jne SHORT $L4455



$L4472:

; 199 : {
; 200 : iScaled = ftol_ambient(*pSource * PRECISION3);

 fld DWORD PTR [esi]
 fmul DWORD PTR __real@4@400b8000000000000000
 fstp QWORD PTR $T4865[ebp]

; 195 : int i;
; 196 : int iScaled;
; 197 : unsigned int iSRGB;

 fld QWORD PTR $T4865[ebp]

; 198 : for (i = 0; i <iCount; ++i)

 fistp DWORD PTR _i$4863[ebp]

; 201 : if (iScaled <= 0)

 mov edx, DWORD PTR _i$4863[ebp]
 test edx, edx
 jg SHORT $L4475

; 202 : *pDestination = 0;

 mov BYTE PTR [edi], 0

; 203 : else if (iScaled> = PRECISION3)

 jmp SHORT $L4478
$L4475:
 cmp edx, 4096 ; 00001000H
 jl SHORT $L4477

; 204 : *pDestination = 255;

 mov BYTE PTR [edi], 255 ; 000000ffH

; 205 : else

 jmp SHORT $L4478
$L4477:

; 206 : {
; 207 : iSRGB = FloatToSRGBTable3[iScaled];

 xor ecx, ecx
 mov cl, BYTE PTR _FloatToSRGBTable3[edx]

; 208 : if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))

 mov edx, DWORD PTR _SRGBCeiling[ecx*4]
 cmp edx, DWORD PTR [esi]
 jg SHORT $L4481

; 209 : ++iSRGB;

 inc ecx
$L4481:

; 210 : *pDestination = (unsigned char) iSRGB;

 mov BYTE PTR [edi], cl
$L4478:

; 211 : }
; 212 : pSource++;

 add esi, 4

; 213 : pDestination++;

 inc edi
 dec eax
 jne SHORT $L4472


編輯: 嘗試測試的pipenbrinck的假設,我在第一個函數的循環之前和內部添加了幾個行:

int one = 1;
int two = 2;

 if (one == two)
 ++iSRGB;

第一個函數的運行時間現在降到 0.152秒。 很有趣吧


編輯 2: 尼爾斯指出,比較優化版本的構建,它也確實如此。 彙編代碼中的變化非常微妙,我將把它發布到這裡看看它是否提供了線索。 現在我想知道它是否是代碼對齊?

; 175 : for (i = 0; i <iCount; ++i)

$L4457:

; 176 : {
; 177 : iScaled = ftol_ambient(*pSource * PRECISION3);

 fld DWORD PTR [edi]
 fmul DWORD PTR __real@4@400b8000000000000000
 fstp QWORD PTR $T5014[ebp]

; 170 : int i;
; 171 : int iScaled;
; 172 : int one = 1;

 fld QWORD PTR $T5014[ebp]

; 173 : int two = 2;

 fistp DWORD PTR _i$5012[ebp]

; 178 : if (iScaled <= 0)

 mov esi, DWORD PTR _i$5012[ebp]
 test esi, esi
 jg SHORT $L4460

; 179 : *pDestination = 0;

 mov BYTE PTR [edx], 0

; 180 : else if (iScaled> = PRECISION3)

 jmp SHORT $L4463
$L4460:
 cmp esi, 4096 ; 00001000H
 jl SHORT $L4462

; 181 : *pDestination = 255;

 mov BYTE PTR [edx], 255 ; 000000ffH

; 182 : else

 jmp SHORT $L4463
$L4462:

; 183 : {
; 184 : iSRGB = FloatToSRGBTable3[iScaled];

 xor ecx, ecx
 mov cl, BYTE PTR _FloatToSRGBTable3[esi]

; 185 : if (one == two)
; 186 : ++iSRGB;
; 187 : *pDestination = (unsigned char) iSRGB;

 mov BYTE PTR [edx], cl
$L4463:

; 188 : }
; 189 : pSource++;

 add edi, 4

; 190 : pDestination++;

 inc edx
 dec eax
 jne SHORT $L4457

时间: 原作者:

我的猜測是,在第一種情況下兩個不同的分支在同一個branch-predictioncpu插槽。 如果這兩個分支在代碼每次減慢時預測不同。

在第二個循環中,添加的代碼可能足以將分支移動到另一個分支預測槽。

確認你可以給英特爾VTune分析器或者 AMD CodeAnalyst工具一個嘗試。 這些工具將告訴你代碼中到底發生了什麼。

但是,記住,更多的可能是不值得進一步優化這裡代碼。 如果你優化你的代碼在你的cpu速度可能同時成為慢在一個不同的品牌。


編輯:

如果你想在branch-prediction上閱讀,請提供 Agner web-site的最佳效果: http://www.agner.org/optimize/

這裡pdf詳細解釋了branch-prediction插槽分配: http://www.agner.org/optimize/microarchitecture.pdf

原作者:

我的第一個猜測是分支在第二個案例中得到了更好的預測。 可能是因為嵌套給出了使用處理器的更多信息來猜測的演算法。 只是 curiousity,當你刪除行時會發生什麼

if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))

原作者:

你是如何定時計時的? 我想知道分頁或者緩存是否對時間產生了影響? 可能調用第一個程序載入到內存中,穿過一個頁面邊界或導致堆棧( 導致一個 page-in ) 進入一個無效的頁面,但只有第一個日常支付的價格。

你可能想要通過兩個函數運行曾經在調用之前,採取測量減少虛擬內存和緩存可能的影響。

原作者:

你是在測試內部循環,還是測試未公開的外部循環? 如果是的話,看看這三行:


if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource)) 
 ++iSRGB;
*pDestination = (unsigned char) iSRGB;

現在,看起來像*pDestination 是外部循環的計數器。 所以有時候做額外增加的iSRGB 值你可以跳過一些外層循環迭代,從而減少總量的代碼需要做的工作。

原作者:

我曾經有過類似的情況。 我從一個循環中提升了一些代碼,使它更快,但是它速度較慢。 令人迷惑。事實證明,循環的平均次數小於 1.

( 顯然你不需要)的教訓是,除非你的代碼實際運行得更快,否則改變不會使你的代碼更快。

...