(编辑:让我们将其命名为“测量如何出错的教训。”但我仍然没有弄清楚究竟是什么导致了差异。)
我发现了一个非常快的整数平方根函数 here通过马克·克朗。至少在我的机器上使用 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++ 版本都要快(尽管测试存在可靠性问题)，但以下内容SSE 代码似乎对于标量 32 位整数 sqrt 可能会更快一点。它不能在不丢失精度的情况下推广到成熟的 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);
}
最佳答案
我用 gcc 4.5.3 试过你的代码。
我修改了你的第二个版本的代码以匹配第一个版本，
例如:
(1 << ((s) * 2 - 2)
对比
(1 << ((s << 1) - 1)
是的，s * 2 == s << 1，但是“-2”和“-1”？
我还修改了您的类型，用“unsigned long”替换了 uint32_t，因为在我的 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”来汇编，但我希望看到没有附加信息的汇编器。
你知道吗？
汇编程序完全一样，
在第一个和第二个版本中。
所以我认为你的时间测量是错误的。
关于c++ - 我可以将此宏更改为内联函数而不影响性能吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8221275/