Gauche:Bignum演算

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: 数値


Last modified : 2008/12/21 21:17:18 UTC