10

（编辑：让我们把它命名为“测量如何出错的教训。”我仍然没有弄清楚究竟是什么导致了这种差异。）

我在这里找到了 Mark Crowne的一个非常快的整数平方根函数。至少在我的机器上使用 GCC，它显然是我测试过的最快的整数平方根函数（包括标准库中的 Hacker's Delight、this page和 floor(sqrt()) 中的函数）。

在稍微清理一下格式、重命名变量并使用固定宽度类型之后，它看起来像这样：

static uint32_t mcrowne_isqrt(uint32_t val)
{
    uint32_t temp, root = 0;

    if (val >= 0x40000000)
    {
        root = 0x8000;
        val -= 0x40000000;
    }

    #define INNER_ISQRT(s)                              \
    do                                                  \
    {                                                   \
        temp = (root << (s)) + (1 << ((s) * 2 - 2));    \
        if (val >= temp)                                \
        {                                               \
            root += 1 << ((s)-1);                       \
            val -= temp;                                \
        }                                               \
    } while(0)

    INNER_ISQRT(15);
    INNER_ISQRT(14);
    INNER_ISQRT(13);
    INNER_ISQRT(12);
    INNER_ISQRT(11);
    INNER_ISQRT(10);
    INNER_ISQRT( 9);
    INNER_ISQRT( 8);
    INNER_ISQRT( 7);
    INNER_ISQRT( 6);
    INNER_ISQRT( 5);
    INNER_ISQRT( 4);
    INNER_ISQRT( 3);
    INNER_ISQRT( 2);

    #undef INNER_ISQRT

    temp = root + root + 1;
    if (val >= temp)
        root++;
    return root;
}

INNER_ISQRT 宏并不太邪恶，因为它是本地的并且在不再需要后立即未定义。尽管如此，原则上我仍然想将其转换为内联函数。我已经在几个地方（包括 GCC 文档）阅读了有关内联函数与宏“一样快”的断言，但是在不影响速度的情况下转换它时遇到了麻烦。

我当前的迭代看起来像这样（注意 always_inline 属性，我把它放在了很好的衡量标准）：

static inline void inner_isqrt(const uint32_t s, uint32_t& val, uint32_t& root) __attribute__((always_inline));
static inline void inner_isqrt(const uint32_t s, uint32_t& val, uint32_t& root)
{
    const uint32_t temp = (root << s) + (1 << ((s << 1) - 2));
    if(val >= temp)
    {
        root += 1 << (s - 1);
        val -= temp;
    }
}

//  Note that I just now changed the name to mcrowne_inline_isqrt, so people can compile my full test.
static uint32_t mcrowne_inline_isqrt(uint32_t val)
{
    uint32_t root = 0;

    if(val >= 0x40000000)
    {
        root = 0x8000; 
        val -= 0x40000000;
    }

    inner_isqrt(15, val, root);
    inner_isqrt(14, val, root);
    inner_isqrt(13, val, root);
    inner_isqrt(12, val, root);
    inner_isqrt(11, val, root);
    inner_isqrt(10, val, root);
    inner_isqrt(9, val, root);
    inner_isqrt(8, val, root);
    inner_isqrt(7, val, root);
    inner_isqrt(6, val, root);
    inner_isqrt(5, val, root);
    inner_isqrt(4, val, root);
    inner_isqrt(3, val, root);
    inner_isqrt(2, val, root);

    const uint32_t temp = root + root + 1;
    if (val >= temp)
        root++;
    return root;
}

不管我做什么，内联函数总是比宏慢。使用 -O2 构建的 (2^28 - 1) 次迭代，宏版本的时间通常在 2.92 秒左右，而内联版本的时间通常在 3.25 秒左右。编辑：我之前说过 2^32 - 1 次迭代，但我忘记了我已经改变了它。他们需要更长的时间才能获得完整的色域。

编译器可能只是愚蠢并拒绝内联它（再次注意 always_inline 属性！），但如果是这样，那无论如何都会使宏版本通常更可取。（我尝试检查程序集以查看，但它作为程序的一部分太复杂了。当我尝试只编译函数时，优化器省略了所有内容，并且由于对 GCC 不熟悉，我在将其编译为库时遇到了问题.)

简而言之，有没有办法把它写成内联而不影响速度？（我没有分析过，但是 sqrt 是那些应该始终快速完成的基本操作之一，因为我可能在许多其他程序中使用它，而不仅仅是我目前感兴趣的程序。此外，我只是好奇.)

我什至尝试使用模板来“烘焙”常量值，但我觉得其他两个参数更有可能导致命中（宏可以避免这种情况，因为它直接使用局部变量）.. .好吧，无论是那个还是编译器都顽固地拒绝内联。

更新：下面的 user1034749 将这两个函数放在单独的文件中并编译它们时，从这两个函数中获得相同的程序集输出。我尝试了他的确切命令行，并且得到了与他相同的结果。出于所有意图和目的，这个问题得到了解决。

但是，我仍然想知道为什么我的测量结果会有所不同。显然，我的测量代码或原始构建过程导致情况有所不同。我将在下面发布代码。有谁知道这笔交易是什么？也许我的编译器实际上在我的 main() 函数的循环中内联了整个 mcrowne_isqrt() 函数，但它没有内联整个其他版本？

更新 2（在测试代码之前压缩）：请注意，如果我交换测试的顺序并使内联版本排在第一位，则内联版本的输出速度比宏版本快相同的数量。这是一个缓存问题，还是编译器内联一个调用而不是另一个，或者什么？

#include <iostream>
#include <time.h>      //  Linux high-resolution timer
#include <stdint.h>

/*  Functions go here */

timespec timespecdiff(const timespec& start, const timespec& end)
{
    timespec elapsed;
    timespec endmod = end;
    if(endmod.tv_nsec < start.tv_nsec)
    {
        endmod.tv_sec -= 1;
        endmod.tv_nsec += 1000000000;
    }

    elapsed.tv_sec = endmod.tv_sec - start.tv_sec;
    elapsed.tv_nsec = endmod.tv_nsec - start.tv_nsec;
    return elapsed;
}


int main()
{
    uint64_t inputlimit = 4294967295;
    //  Test a wide range of values
    uint64_t widestep = 16;

    timespec start, end;

    //  Time macro version:
    uint32_t sum = 0;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
    for(uint64_t num = (widestep - 1); num <= inputlimit; num += widestep)
    {
        sum += mcrowne_isqrt(uint32_t(num));
    }
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
    timespec markcrowntime = timespecdiff(start, end);
    std::cout << "Done timing Mark Crowne's sqrt variant.  Sum of results = " << sum << " (to avoid over-optimization)." << std::endl;


    //  Time inline version:
    sum = 0;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
    for(uint64_t num = (widestep - 1); num <= inputlimit; num += widestep)
    {
        sum += mcrowne_inline_isqrt(uint32_t(num));
    }
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
    timespec markcrowninlinetime = timespecdiff(start, end);
    std::cout << "Done timing Mark Crowne's inline sqrt variant.  Sum of results = " << sum << " (to avoid over-optimization)." << std::endl;

    //  Results:
    std::cout << "Mark Crowne sqrt variant time:\t" << markcrowntime.tv_sec << "s, " << markcrowntime.tv_nsec << "ns" << std::endl;
    std::cout << "Mark Crowne inline sqrt variant time:\t" << markcrowninlinetime.tv_sec << "s, " << markcrowninlinetime.tv_nsec << "ns" << std::endl;
    std::cout << std::endl;
}

更新3：我仍然不知道如何可靠地比较不同功能的时间，而不需要根据测试的顺序来确定时间。我将不胜感激任何提示！

但是，如果其他阅读本文的人对快速 sqrt 实现感兴趣，我应该提一下：Mark Crowne 的代码测试速度比我尝试过的任何其他纯 C/C++ 版本都快（尽管测试存在可靠性问题），但以下对于标量 32 位整数 sqrt，SSE 代码似乎可能会更快一些。它不能被推广到成熟的 64 位无符号整数输入而不损失精度（并且第一个有符号转换也必须由处理值 >= 2^63 的固有负载替换）：

uint32_t sse_sqrt(uint64_t num)
{
    //  Uses 64-bit input, because SSE conversion functions treat all
    //  integers as signed (so conversion from a 32-bit value >= 2^31
    //  will be interpreted as negative).  As it stands, this function
    //  will similarly fail for values >= 2^63.
    //  It can also probably be made faster, since it generates a strange/
    //  useless movsd %xmm0,%xmm0 instruction before the sqrtsd.  It clears
    //  xmm0 first too with xorpd (seems unnecessary, but I could be wrong).
    __m128d result;
    __m128d num_as_sse_double = _mm_cvtsi64_sd(result, num);
    result = _mm_sqrt_sd(num_as_sse_double, num_as_sse_double);
    return _mm_cvttsd_si32(result);
}
4

1 回答 1

7

我用 gcc 4.5.3 试过你的代码。我修改了您的第二个版本的代码以匹配第一个版本，例如：

(1 << ((s) * 2 - 2)

对比

(1 << ((s << 1) - 1)

是的，s * 2 == s << 1，但是“-2”和“-1”？

我还修改了您的类型，将 uint32_t 替换为“unsigned long”，因为在我的 64 位机器上，“long”不是 32 位数字。

然后我运行：

g++ -ggdb -O2 -march=native -c -pipe inline.cpp
g++ -ggdb -O2 -march=native -c -pipe macros.cpp
objdump -d inline.o > inline.s
objdump -d macros.o > macros.s

我可以使用“-S”而不是“-c”来汇编程序，但我希望看到没有附加信息的汇编程序。

你知道吗？
在第一个版本和第二个版本中，汇编程序完全一样。所以我认为你的时间测量是错误的。

于 2011-11-22T05:29:36.790 回答