计算平方根有多慢(多少个周期)？

Question

计算平方根有多慢(多少个周期)？这出现在一个分子动力学课程中,效率很重要,采取不必要的平方根对算法的运行时间有显着影响.

Answer 1

来自Agner Fog的指令表:

在Core2 65nm上,FSQRT需要9到69 cc(具有几乎相等的倒数吞吐量),具体取决于值和精度位.为了比较,FDIV需要9到38 cc(几乎相等的倒数吞吐量),FMUL需要5(recipthroughput = 2)而FADD需要3(recipthroughput = 1).SSE性能大致相等,但看起来更快,因为它不能做80位数学运算.SSE具有超快速近似倒数和近似倒数sqrt.

在Core2 45nm上,除法和平方根得到了更快; FSQRT需要6到20毫升,FDIV需要6到21毫升,FADD和FMUL没有变化.SSE的表现再次大致相同.

您可以从他的网站获取包含此信息的文档.

Answer 2

平方根比添加使用慢约4倍-O2,或不使用约13倍-O2.在网上的其他地方,我发现50-100个周期的估计值可能是正确的,但它不是一个非常有用的相对成本度量,因此我将下面的代码汇总在一起进行相对测量.如果您发现测试代码有任何问题,请告诉我.

下面的代码在Windows 7操作系统下的Intel Core i3上运行,并在DevC++(使用GCC)中编译.你的旅费可能会改变.

#include <cstdlib>
#include <iostream>
#include <cmath>

/*
Output using -O2:

1 billion square roots running time: 14738ms

1 billion additions running time   : 3719ms

Press any key to continue . . .

Output without -O2:

10 million square roots running time: 870ms

10 million additions running time   : 66ms

Press any key to continue . . .

Results:

Square root is about 4 times slower than addition using -O2,
            or about 13 times slower without using -O2
*/

int main(int argc, char *argv[]) {

    const int cycles = 100000;
    const int subcycles = 10000;

    double squares[cycles];

    for ( int i = 0; i < cycles; ++i ) {
        squares[i] = rand();
    }

    std::clock_t start = std::clock();

    for ( int i = 0; i < cycles; ++i ) {
        for ( int j = 0; j < subcycles; ++j ) {
            squares[i] = sqrt(squares[i]);
        }
    }

    double time_ms = ( ( std::clock() - start ) / (double) CLOCKS_PER_SEC ) * 1000;

    std::cout << "1 billion square roots running time: " << time_ms << "ms" << std::endl;

    start = std::clock();

    for ( int i = 0; i < cycles; ++i ) {
        for ( int j = 0; j < subcycles; ++j ) {
            squares[i] = squares[i] + squares[i];
        }
    }

    time_ms = ( ( std::clock() - start ) / (double) CLOCKS_PER_SEC ) * 1000;

    std::cout << "1 billion additions running time   : " << time_ms << "ms" << std::endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

Answer 3

平方根需要几个周期,但如果它不在缓存中,则访问内存需要几个数量级.因此,试图通过从存储器中取出预先计算的结果来避免计算实际上可能对性能有害.

很难在摘要中说明你是否会获益,所以如果你想确切地知道,请尝试并对这两种方法进行基准测试.

以下是关于MSVC编译器开发人员Eric Brummer的精彩演讲:http://channel9.msdn.com/Events/Build/2013/4-329