コンパイラ: MinGW/GCCの
問題: GPL/LGPL コードは許可されていません (GMP やその他の bignum ライブラリは、既にクラスを実装しているため、この問題には過剰です)。
私は独自の128 ビットの固定サイズの大きな整数クラス (ゲーム エンジンでの使用を意図していますが、あらゆる使用ケースに一般化される可能性があります) を作成しましたが、現在の乗算および除算演算のパフォーマンスは非常にひどいものであることがわかりました (はい、私はそれらの時間を測定しました。以下を参照してください) 、低レベルの数値処理を行うアルゴリズムを改善 (または変更) したいと考えています。
乗算演算子と除算演算子に関して言えば、クラスの他のほぼすべての演算子と比較して、耐えられないほど遅いです。
これらは、自分のコンピューターと比較したおおよその測定値です。
Raw times as defined by QueryPerformanceFrequency:
1/60sec 31080833u
Addition: ~8u
Subtraction: ~8u
Multiplication: ~546u
Division: ~4760u (with maximum bit count)
ご覧のとおり、掛け算だけを行うのは、足し算や引き算よりも何倍も遅くなります。除算は、乗算よりも約 10 倍遅くなります。
フレームごとに非常に大量の計算が行われる可能性があるため (内積、さまざまな衝突検出方法など)、これら 2 つの演算子の速度を改善したいと考えています。
構造 (メソッドは省略) は次のようになります。
class uint128_t
{
public:
unsigned long int dw3, dw2, dw1, dw0;
//...
}
乗算は現在、典型的なlong-multiplicationメソッドを使用して (出力をキャッチできるようにアセンブリでEDX) 実行されますが、範囲外になる単語は無視されます (つまり、mull16 と比較して 10 のみを実行しています)。
除算はシフト減算アルゴリズムを使用します (速度はオペランドのビット数に依存します)。ただし、アセンブリでは行われません。集めるのが少し難しすぎることがわかり、コンパイラーに最適化させることにしました。
カラツバ乗算、高基数除算、ニュートンラプソン除算などのアルゴリズムを説明するページを数日間 Google で調べましたが、数学記号は頭の中に少しありすぎます。これらの高度な方法を使用してコードを高速化したいのですが、最初に「ギリシャ語」をわかりやすいものに翻訳する必要があります。
私の努力を「時期尚早の最適化」と見なす可能性のある人のために。非常に基本的な数学演算自体が遅くなるため、このコードがボトルネックになると考えています。高レベルのコードでは、このようなタイプの最適化は無視できますが、このコードは十分に呼び出されたり使用されたりします。
乗算と除算を改善するために使用するアルゴリズムについての提案 (可能であれば) と、提案されたアルゴリズムがどのように機能するかについての基本的な (できれば理解しやすい) 説明をいただければ幸いです。
編集：乗算の改善
コードを operator*= にインライン化することで乗算演算を改善することができ、可能な限り高速に見えます。
Updated raw times:
1/60sec 31080833u
Addition: ~8u
Subtraction: ~8u
Multiplication: ~100u (lowest ~86u, highest around ~256u)
Division: ~4760u (with maximum bit count)
調べる必要のある最低限のコードを次に示します (私のタイプ名は実際には異なることに注意してください。これは簡単にするために編集されています)。
//File: "int128_t.h"
class int128_t
{
uint32_t dw3, dw2, dw1, dw0;
// Various constrctors, operators, etc...
int128_t& operator*=(const int128_t& rhs) __attribute__((always_inline))
{
int128_t Urhs(rhs);
uint32_t lhs_xor_mask = (int32_t(dw3) >> 31);
uint32_t rhs_xor_mask = (int32_t(Urhs.dw3) >> 31);
uint32_t result_xor_mask = (lhs_xor_mask ^ rhs_xor_mask);
dw0 ^= lhs_xor_mask;
dw1 ^= lhs_xor_mask;
dw2 ^= lhs_xor_mask;
dw3 ^= lhs_xor_mask;
Urhs.dw0 ^= rhs_xor_mask;
Urhs.dw1 ^= rhs_xor_mask;
Urhs.dw2 ^= rhs_xor_mask;
Urhs.dw3 ^= rhs_xor_mask;
*this += (lhs_xor_mask & 1);
Urhs += (rhs_xor_mask & 1);
struct mul128_t
{
int128_t dqw1, dqw0;
mul128_t(const int128_t& dqw1, const int128_t& dqw0): dqw1(dqw1), dqw0(dqw0){}
};
mul128_t data(Urhs,*this);
asm volatile(
"push %%ebp \n\
movl %%eax, %%ebp \n\
movl $0x00, %%ebx \n\
movl $0x00, %%ecx \n\
movl $0x00, %%esi \n\
movl $0x00, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%ebx \n\
adcl %%edx, %%ecx \n\
adcl $0x00, %%esi \n\
adcl $0x00, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%ecx \n\
adcl %%edx, %%esi \n\
adcl $0x00, %%edi \n\
movl 20(%%ebp), %%eax #Calc: (dw2*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 16(%%ebp), %%eax #Calc: (dw3*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%ecx \n\
adcl %%edx, %%esi \n\
adcl $0x00, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 20(%%ebp), %%eax #Calc: (dw2*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw2) \n\
mull 4(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw2) \n\
mull 4(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw3) \n\
mull (%%ebp) \n\
addl %%eax, %%edi \n\
pop %%ebp \n"
:"=b"(this->dw0),"=c"(this->dw1),"=S"(this->dw2),"=D"(this->dw3)
:"a"(&data):"%ebp");
dw0 ^= result_xor_mask;
dw1 ^= result_xor_mask;
dw2 ^= result_xor_mask;
dw3 ^= result_xor_mask;
return (*this += (result_xor_mask & 1));
}
};
除算に関しては、実質的な利点を確認するには数学的アルゴリズムを変更する必要があるため、コードを調べることはあまり意味がありません。実行可能な唯一の選択肢は高基数除算のようですが、それがどのように機能するかについてはまだ (私の頭の中で) 解決していません。