（编辑：让我们将其命名为“测量如何出错的教训。”但我仍然没有弄清楚到底是什么导致了差异。）
我发现了一个非常快的整数平方根函数here http://www.azillionmonkeys.com/qed/sqroot.html作者：马克·克朗。至少在我的机器上使用 GCC，它显然是我测试过的最快的整数平方根函数（包括 Hacker's Delight 中的函数，这一页 http://web.archive.org/web/20101228021530/http://www.codecodex.com/wiki/Calculate_an_integer_square_root，以及来自标准库的 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);
}
