Gauche:Bignum演算
(2003/02/27 14:59:11 PST): メモ。SCM/JACALで扱うintegerの大きさのdistribution。 http://swissnet.ai.mit.edu/~jaffer/CNS/DIMPA
99.5%以上のintegerは63ビット以下に収まっていたとある。 やはり、少ないワード数での演算で最適化する戦略がよさげだ。
asm使用
Gaucheでは特にBignum演算の性能は重視していない。そっち方面では既に 良いライブラリがたくさんあるので、そういう応用が必要ならば拡張モジュールとして 組み込めば良いという方針である。GaucheのBignum演算に求めたのは、 システムスクリプトを書いていてたまにマシンワードを桁溢れした時に 遅くても正しい結果を返すこと、である。 但し浮動小数点入出力ルーチンでbignum演算が使われるので、 特に少ないワード数(2〜4ワード)での演算はある程度速度が欲しい。
で、Cで多倍長の演算を書いていると、キャリーフラグとか フルワード同士の乗算とか、プロセッサには備わっているのに Cから触れないものがあってなんかじれったい。 こいつをアセンブリで書いたらどうなるかというのに興味があった。
そこで、i386限定で基本部分だけインラインアセンブリにして 簡単なベンチマークを取ってみた。 比較対象は gauche/arith.hで定義されているマクロ部分だけをasmで書いたもの。 Gauche 0.6.2使用。
まずは、2〜4ワードのランダムなbignum 1000000個についてstring->numberと number->stringを適用してみる。 string->number内ではbignumの加算と乗算が、number->string内では bignum÷fixnumの演算が入る。数回やって平均を取る。
string->number number->string asm不使用 3.27s 8.26s asm使用 3.05s 8.22s
同じデータセットで、各数値について適当に加減乗算をしてみる。
asm不使用 3.35s asm使用 3.14s
今度はランダムな浮動小数点数について、おなじくstring->numberとnumber->stringを。
string->number number->string asm不使用 17.2s 159s asm使用 16.9s 139s
ということで、確かにasmを使ったほうが速くなるが、劇的という程でもない。 他のファクターが大きいのだろう。特に浮動小数点数のnumber->stringに関しては、 bignumのallocationを減らすほうがはるかに効くんではないかと踏んでいる。
(2002/09/09 00:26:39 PDT)
Tag: 数値