2

在对数字进行乘法或除法时,我进行了一些速度测试以找出最快的速度。我必须非常努力地打败优化器。我得到了荒谬的结果,例如在 2 微秒内运行的大规模循环,或者乘法与除法的速度相同(如果这是真的)。

在我最终努力工作以击败足够多的编译器优化,同时仍然让它优化速度之后,我得到了这些速度结果。他们可能对其他人感兴趣?

如果我的测试仍然存在缺陷,请告诉我,但请善待我,因为我只花了两个小时写这个废话:P

64 time: 3826718 us
32 time: 2476484 us
D(mul) time: 936524 us
D(div) time: 3614857 us
S time: 1506020 us

使用双精度“乘除”似乎是最快的除法方法,其次是整数除法。我没有测试划分的准确性。难道“适当的划分”更准确吗?我不想在这些速度测试结果之后找出答案,因为我只是在以 10 为基数的常量上使用整数除法并让我的编译器为我优化它;)(也不会破坏它的优化)。

这是我用来获取结果的代码:

#include <iostream>

int Run(int bla, int div, int add, int minus) {
    // these parameters are to force the compiler to not be able to optimise away the
    // multiplications and divides :)
    long LoopMax = 100000000;

    uint32_t Origbla32 = 1000000000;
    long i = 0;

    uint32_t bla32 = Origbla32;
    uint32_t div32 = div;
    clock_t Time32 = clock();
    for (i = 0; i < LoopMax; i++) {
        div32 += add;
        div32 -= minus;
        bla32 = bla32 / div32;
        bla32 += bla;
        bla32 = bla32 * div32;
    }
    Time32 = clock() - Time32;

    uint64_t bla64 = bla32;
    clock_t Time64 = clock();
    uint64_t div64 = div;
    for (long i = 0; i < LoopMax; i++) {
        div64 += add;
        div64 -= minus;
        bla64 = bla64 / div64;
        bla64 += bla;
        bla64 = bla64 * div64;
    }
    Time64 = clock() - Time64;

    double blaDMul = Origbla32;
    double multodiv = 1.0 / (double)div;
    double multomul = div;
    clock_t TimeDMul = clock();
    for (i = 0; i < LoopMax; i++) {
        multodiv += add;
        multomul -= minus;
        blaDMul = blaDMul * multodiv;
        blaDMul += bla;
        blaDMul = blaDMul * multomul;
    }
    TimeDMul = clock() - TimeDMul;

    double blaDDiv = Origbla32;
    clock_t TimeDDiv = clock();
    for (i = 0; i < LoopMax; i++) {
        multodiv += add;
        multomul -= minus;
        blaDDiv = blaDDiv / multomul;
        blaDDiv += bla;
        blaDDiv = blaDDiv / multodiv;
    }
    TimeDDiv = clock() - TimeDDiv;

    float blaS = Origbla32;
    float divS = div;
    clock_t TimeS = clock();
    for (i = 0; i < LoopMax; i++) {
        divS += add;
        divS -= minus;
        blaS = blaS / divS;
        blaS += bla;
        blaS = blaS * divS;
    }
    TimeS = clock() - TimeS;

    printf("64 time: %i us  (%i)\n", (int)Time64, (int)bla64);
    printf("32 time: %i us  (%i)\n", (int)Time32, bla32);

    printf("D(mul) time: %i us  (%f)\n", (int)TimeDMul, blaDMul);
    printf("D(div) time: %i us  (%f)\n", (int)TimeDDiv, blaDDiv);
    printf("S time: %i us  (%f)\n", (int)TimeS, blaS);

    return 0;
}

int main(int argc, char* const argv[]) {
    Run(0, 10, 0, 0); // adds and minuses 0 so it doesn't affect the math, only kills the opts
    return 0;
}
4

5 回答 5

11

有很多方法可以执行某些算术,因此可能没有单一的答案(移位、小数乘法、实际除法、通过对数单元的一些往返等;这些可能都有不同的相对成本,具体取决于操作数和资源分配)。

让编译器用它拥有的程序和数据流信息来做它的事情。

对于适用于 x86 上的汇编的一些数据,您可以查看:“AMD 和 Intel x86 处理器的指令延迟和吞吐量”

于 2009-11-17T22:02:10.243 回答
4

最快的将完全取决于目标架构。看起来您只对您碰巧所在的平台感兴趣,从您的执行时间猜测似乎是 64 位 x86,英特尔(Core2?)或 AMD。

也就是说,在许多平台上,浮点乘法将是最快的,但正如您推测的那样,通常不如浮点除法准确(两个舍入而不是一个 - 无论这对您的使用是否重要)是一个单独的问题)。一般来说,你最好重新安排你的算法以使用更少的除法,而不是跳过箍以使除法尽可能高效(最快的除法是你不做的那个),并确保在你之前进行基准测试完全花时间进行优化,因为划分瓶颈的算法很少而且相差甚远。

此外,如果您有整数源并需要整数结果,请确保在基准测试中包含整数和浮点之间的转换成本。

由于您对特定机器上的时序感兴趣,因此您应该知道英特尔现在在其优化参考手册 (pdf)中发布了此信息。具体来说,您将对附录 C 第 3.1 节“带有寄存器操作数的延迟和吞吐量”中的表格感兴趣。

请注意,整数除法时间很大程度上取决于所涉及的实际值。根据该指南中的信息,您的计时程序似乎仍然有相当多的开销,因为您测量的性能比与英特尔发布的信息不匹配。

于 2009-11-17T22:09:55.793 回答
2

正如斯蒂芬所提到的,使用优化手册——但你也应该考虑使用 SSE 指令。它们可以在一条指令中进行 4 或 8 次除法/乘法运算。

此外,一个除法需要一个时钟周期来处理是相当普遍的。结果可能在几个时钟周期内不可用(称为延迟),但是下一次除法可以在这段时间内开始(与第一次重叠),只要它不需要第一次的结果。这是由于 CPU 中的管道衬里,就像您可以在前一个负载仍在干燥时洗更多衣服一样。

乘除是一个常见的技巧,应该在除数不经常变化的地方使用。

您很有可能会花费时间和精力来加快数学运算,结果却发现内存访问的速度(当您导航输入并写入输出时)限制了您的最终实现。

于 2009-11-17T22:41:50.780 回答
0

我在 MSVC 2008 上写了一个有缺陷的测试来做到这一点

double i32Time  = GetTime();
{
    volatile __int32 i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 61;
        count++;
    }
}
i32Time = GetTime() - i32Time;

double i64Time  = GetTime();
{
    volatile __int64 i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 61;
        count++;
    }
}
i64Time = GetTime() - i64Time;


double fTime    = GetTime();
{
    volatile float i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 4.0f;
        count++;
    }
}
fTime   = GetTime() - fTime;

double fmTime   = GetTime();
{
    volatile float i = 4;
    const float div = 1.0f / 4.0f;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i *= div;
        count++;
    }
}
fmTime  = GetTime() - fmTime;

double dTime    = GetTime();
{
    volatile double i = 4;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i /= 4.0f;
        count++;
    }
}
dTime   = GetTime() - dTime;

double dmTime   = GetTime();
{
    volatile double i = 4;
    const double div = 1.0f / 4.0f;
    __int32 count   = 0;
    __int32 max     = 1000000;
    while( count < max )
    {
        i *= div;
        count++;
    }
}
dmTime  = GetTime() - dmTime;


DebugOutput( _T( "%f\n" ), i32Time );
DebugOutput( _T( "%f\n" ), i64Time );
DebugOutput( _T( "%f\n" ), fTime );
DebugOutput( _T( "%f\n" ), fmTime );
DebugOutput( _T( "%f\n" ), dTime );
DebugOutput( _T( "%f\n" ), dmTime );

DebugBreak();

然后我在 AMD64 Turion 64 上以 32 位模式运行它。我得到的结果如下:

0.006622
0.054654
0.006283
0.006353
0.006203
0.006161

测试存在缺陷的原因是 volatile 的使用,它强制编译器从内存中重新加载变量,以防万一它发生变化。所有这些都表明这台机器上的任何实现之间几乎没有什么区别(__int64 显然很慢)。

它还明确地表明 MSVC 编译器通过倒数优化执行乘法。我想 GCC 会做同样的事情,如果不是更好的话。如果我将浮点数和双除法检查更改为除以“i”,那么它会显着增加时间。虽然,虽然其中很多可能是从磁盘重新加载,但很明显编译器无法如此轻松地优化它。

要了解此类微优化,请尝试阅读此 pdf。

总而言之,我认为如果您担心这些事情,您显然没有分析您的代码。当问题真正成为问题时,分析并解决问题。

于 2009-11-17T23:02:17.473 回答
0

Agner Fog 自己做了一些非常详细的测量,可以在这里找到。如果你真的想优化东西,你也应该从他的软件优化资源中阅读其余的文档。

我要指出的是,即使您正在测量非矢量化浮点运算,编译器也有两个用于生成程序集的选项:它可以使用 FPU 指令 ( fadd, fmul) 或者它可以使用 SSE 指令同时仍然操纵一个浮点值每条指令 ( addss, mulss)。以我的经验,SSE 指令更快且不准确,但编译器不会将其设为默认值,因为它可能会破坏与依赖旧行为的代码的兼容性。-mfpmath=sse您可以使用标志在 gcc 中打开它。

于 2009-11-18T04:43:08.610 回答