（編集：これに「測定がうまくいかないことの教訓」というタイトルを付けましょう。ただし、何が不一致の原因であるかはまだ正確にはわかりません。）
ここで Mark Crowne による非常に高速な整数平方根関数を見つけました。少なくとも私のマシンの GCC では、これは明らかに私がテストした中で最速の整数平方根関数です (Hacker's Delight、このページ、および標準ライブラリの 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のnoobishnessのためにライブラリとしてコンパイルするのに問題があります. .)
要するに、これをインラインとして速度を落とさずに書く方法はありますか? (私はプロファイリングしていませんが、sqrt は、現在関心のあるプログラム以外の多くのプログラムで使用している可能性があるため、常に高速化する必要がある基本的な操作の 1 つです。さらに、私はただ興味があります.)
テンプレートを使用して定数値を「焼き込む」ことさえ試みましたが、他の2つのパラメーターがヒットを引き起こしている可能性が高いと感じています（ローカル変数を直接使用するため、マクロはそれを回避できます）。 .まあ、それかコンパイラが頑固にインライン化を拒否しています。
更新: 以下の user1034749 は、それらを別々のファイルに入れてコンパイルすると、両方の関数から同じアセンブリ出力を取得しています。彼の正確なコマンド ラインを試してみましたが、彼と同じ結果が得られました。すべての意図と目的のために、この質問は解決されています。
ただし、測定結果が異なる理由を知りたいです。明らかに、私の測定コードまたは元のビルド プロセスが原因で、状況が異なっていました。以下にコードを掲載します。どんな取引だったか知ってる人いますか？私のコンパイラは実際には私の main() 関数のループで mcrowne_isqrt() 関数全体をインライン化しているのかもしれませんが、他のバージョン全体をインライン化しているわけではありませんか?
更新 2 (コードをテストする前に圧縮): テストの順序を入れ替えてインライン バージョンを最初にすると、インライン バージョンはマクロ バージョンよりも同じ量だけ速くなることに注意してください。これはキャッシングの問題ですか、それともコンパイラが 1 つの呼び出しをインライン化していて、他の呼び出しをインライン化していないのでしょうか?
#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);
}