template library を作る - 固定小数点数

since: 2002-08-27 update: 2002-08-29 count: 21166

コード - gamenum.h

使い方 - gamenumTest.cc

説明

浮動小数の演算はどうも遅くてかなわん、 と昔の人は int の使ってない上の方のビットを 使うこと考えました… はい、説明めんどいんで、知らない人は adasさんのC言語実験室 を "8/6" とかで検索すれば、 整数化小数という項目に書いてありますので、 そちらを参考にして下さい。

さて、この固定小数点数ですが、 確かに早くてメモリの節約にもなるんですが、 これ、凄くめんどくさいです。 printfデバッグの際なんかにも いちいちshiftしにゃならんですし、 shift数を覚えてなきゃですし、 煩雑この上ないのです。

で、そういうものってのは非常に典型的なカプセル化の対象なので、 そういうクラス GameNum を作りました。

やっとコンパイルタイムメタプログラミングの出番です。

GameNum 仕様

テンプレート引数で、小数点以下の表現に用いるbit数 shifts_ と、 値を保存する整数型 Int_ (デフォルトでint、これは long int なんかを使いたい場合に指定する) を指定します。

メモリ使用量は Int_ と等しい。

double に対して行いうる演算を大抵行える。

演算速度は、同じシフト数のGameNum同士の演算では、 Int_ と、完全に同じ速度で動作(して欲しい)。

異なるシフト数同士の演算では、シフト一回分遅くなる。 (実行時 if でビットの違いを判定してはいけない)

GameNum と double の演算は全て、非常に遅い。

GameNum の使い方

typedef GameNum<8> Num;

的なことは最初にしておきましょう。 やっぱ double の方がいいやと思った時の変更も楽ですし。 shift数を変えたい時にも有効です。

まあ、後は double みたいに使って下さい。 gamenumTest.cc を見ればおおよそのことがわかるはずなので、 まあ、適当な説明。

GameNum 実際の速度

gamenumTest.cc を -O オプションを付けて gcc-2.96 でコンパイルしたところ、

double: value 2.95834e+06 sec 0.51
float: value 2.92842e+06 sec 1.57
int: value 2955585 sec 0.38
GameNum - GameNum: value 2955585 sec 0.38
GameNum - GameNum_another: value 2956171 sec 0.38
GameNum - double: value 2955585 sec 6.34
GameNum_longlong - GameNum_longlong: value 2958338 sec 0.4

とのことでした。 このパフォーマンステストでは加算を膨大な数行っています。

同じ計算を、上から double のみで、float のみで、 自前で int をシフトして、GameNumを精度8ビットで、 GameNumを異なる精度で、GameNumとdoubleで、 GameNumのテンプレート第二引数に long long を指定して、 それぞれ行ったものです。

1行目と4行目のvalueが似たような数値であることから、 まあ、一定の精度を持っていることがわかります。

また、同時に3行目と4行目のsecが同じであることから、 関数のインライン展開によって、 自前でシフトした時と同じ速度を保っていることがわかります。

五行目は異なる精度でも、適切な計算を行うことを示しています。

六行目はdoubleとの演算は非常に遅いことを示します。

完璧に要求仕様を満たしているように見えます。 が、実は多少インチキがあって、 一番良さげな結果の出るコンパイルオプションを紹介しました。 コンパイルオプションを -O2 にすると、

double: value -3.34014e+06 sec 0.5
float: value -3.34014e+06 sec 0.51
int: value -3339375 sec 0.29
GameNum - GameNum: value -3339375 sec 0.45
GameNum - GameNum_another: value -3337266 sec 0.38
GameNum - double: value -3339375 sec 6.25
GameNum_longlong - GameNum_longlong: value -3340134 sec 0.68

となって、何故か遅くなってしまいました。 -O3も似たようなものです。

だらだら紹介しといてこんなことを言うのも何ですが、 正直なところ、この程度の差なら double で十分やんけ、と思います。

実装

最初に出てくる public 以降は全然難しくないです。 単なるオペレータやらコンストラクタの定義なので。 よって省略。

最初の private 部分が結構難しいと思います。 この部分は GameNum<8> と GameNum<6> で 演算する時に、右辺値の値を2ビット左シフトする、 という決定をコンパイルタイムに下すためのものです。

これを決定するには、左辺値と右辺値のシフト数が、 等しければシフト無し、左辺が大きければ右辺を左シフト、 右辺が大きければ右辺を右シフトすれば良いはずです。

この条件分岐を実現するために、 ConvertHelper_ というヘルパクラスを作ってみました。 この宣言は以下のようなものです。

template <bool equal_, bool leftLarge_,
          int leftShifts_, int rightShifts_>
struct ConvertHelper_;

これのテンプレート特別バージョンを定義することによって、 コンパイルタイムに条件分岐を行うことになります。 この場合、 (equal_, leftLarge_) = (true, false), (false, true), (false, false) の三パターンの特別バージョンを定義します。

template <int leftShifts_, int rightShifts_>
struct ConvertHelper_<true, false, leftShifts_, rightShifts_> {
    static Int_ run(Int_ v) {
        return v;
    }
};
template <int leftShifts_, int rightShifts_>
struct ConvertHelper_<false, true, leftShifts_, rightShifts_> {
    static Int_ run(Int_ v) {
        return v << leftShifts_ - rightShifts_;
    }
};  
template <int leftShifts_, int rightShifts_>
struct ConvertHelper_<false, false, leftShifts_, rightShifts_> {
    static Int_ run(Int_ v) {
        return v >> rightShifts_ - leftShifts_;
    }
};  

(true, true) の場合は、論理的に起こり得ませんが、 ConvertHelper_ は最初の段階で、 汎用的な形は宣言だけで、定義を行っていないので、 仮に (true, true) が入ってきても、 これはコンパイルエラーになります。

これを MPL を使って書き直したバージョンも、 boost user - MPL で公開しとります。 gamenum-boost.h

TODO

double 使うと遅すぎ。


home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h