22

我有一个带有内部循环的简单函数 - 它缩放输入值,在查找表中查找输出值,并将其复制到目的地。(ftol_ambient 是我从网上复制的一个技巧,用于将浮点数快速转换为整数)。

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++;
}

现在我的查找表是有限的,而浮点数是无限的,因此可能会出现错误。我用一些代码创建了一个函数的副本来处理这种情况。请注意,唯一的区别是添加了 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 次。在我的 Athlon 64 1.8 GHz(32 位模式)上,第一个函数需要 0.231 秒,第二个(更长的)函数需要 0.185 秒。这两个函数在同一个源文件中是相邻的,因此不可能有不同的编译器设置。我已经多次运行测试,颠倒它们运行的​​顺序,每次的时间都大致相同。

我知道现代处理器中有很多谜团,但这怎么可能呢?

这里比较的是来自 Microsoft 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


编辑:试图测试Nils Pipenbrinck 的假设,我在第一个函数的循环之前和内部添加了几行:

int one = 1;
int two = 2;

        if (one == two)
            ++iSRGB;

第一个函数的运行时间现在降至 0.152 秒。有趣的。


编辑 2: Nils 指出,比较将在发布版本中进行优化,确实如此。汇编代码的变化非常微妙,我将它贴在这里,看看它是否提供任何线索。在这一点上,我想知道它是否是代码对齐?

; 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
4

5 回答 5

11

我的猜测是,在第一种情况下,两个不同的分支最终位于 CPU 上的同一个分支预测槽中。如果这两个分支每次预测不同,代码就会变慢。

在第二个循环中,添加的代码可能足以将其中一个分支移动到不同的分支预测槽。

为了确保您可以尝试使用 Intel VTune 分析器或 AMD CodeAnalyst 工具。这些工具将向您展示代码中究竟发生了什么。

但是,请记住,进一步优化此代码很可能不值得。如果您将代码调整为在 CPU 上更快,它可能同时在不同品牌上变得更慢。


编辑:

如果您想阅读分支预测,请尝试 Agner Fog 的优秀网站:http ://www.agner.org/optimize/

这个pdf详细解释了分支预测槽分配:http ://www.agner.org/optimize/microarchitecture.pdf

于 2009-03-27T03:20:41.280 回答
4

我的第一个猜测是,在第二种情况下,分支预测得更好。可能是因为嵌套的 if 给出了处理器使用更多信息来猜测的任何算法。只是出于好奇,当你删除线会发生什么

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

?

于 2009-03-27T02:47:37.693 回答
1

你是如何安排这些例程的?我想知道分页或缓存是否对时间有影响?调用第一个例程可能会将两者都加载到内存中,越过页面边界或导致堆栈进入无效页面(导致页入),但只有第一个例程付出了代价。

您可能希望在进行测量之前运行这两个函数一次,以减少虚拟内存和缓存可能产生的影响。

于 2009-03-27T03:50:22.160 回答
0

你只是在测试这个内部循环,还是在测试你未公开的外部循环?如果是这样,请查看以下三行:

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

现在,它看起来像是*pDestination外循环的计数器。因此,有时通过额外增加iSRGB值,您可以跳过外部循环中的一些迭代,从而减少代码需要完成的工作总量。

于 2009-03-27T03:15:10.123 回答
0

我曾经有过类似的情况。我从循环中提取了一些代码以使其更快,但它变慢了。令人困惑。事实证明,循环的平均次数小于 1。

教训(显然,您不需要)是更改不会使您的代码更快,除非您测量它实际上运行得更快。

于 2009-10-29T05:05:02.853 回答