bignumの使用のオーバーヘッド

Question

数字が関係する場合、デフォルトのデータ型として自分の言語でbignumを使用するかどうかについて、この問題に遭遇しました。私はこれを自分で評価し、利便性と快適さの対パフォーマンスの質問に減らしました。その質問に対する答えは、最適化されていないプログラムでのパフォーマンスヒットの大きさによって異なります。

fixnumまたは整数で十分な場所でbignumを使用するオーバーヘッドはどのくらい小さいですか？最高の実装でどれくらい小さいことができますか？どのような実装が最小のオーバーヘッドに到達し、どのような追加のトレードオフがもたらされますか？

bignumの言語をデフォルトに設定すると、全体的な言語パフォーマンスの結果にどのようなヒットが期待できますか？

Answer 1

正直に言うと、最良の答えは「試してみてください」です。

明らかに、bignumsは通常単一のCPUレジスタに収まるネイティブ型ほど効率的ではありませんが、すべてのアプリケーションは異なります-整数演算の全負荷を行わない場合、オーバーヘッドは無視できます。

Answer 2

おそらく、Lispがどのようにそれを行うかを見ることができます。ほとんどの場合、正確に 正しいことを行い、必要に応じて暗黙的に型を変換します。 fixnum（「通常の」整数）、bignum、比率（2つの整数のセットとして表される適切な分数の削減）、およびfloat（異なるサイズ）があります。浮動小数点数にのみ精度エラーがあり、伝染性があります。つまり、計算に浮動小数点数が含まれると、結果も浮動小数点数になります。 ＆quot; Practical Common Lisp＆quot;この振る舞いの良い説明があります。

Answer 3

考えてみてください...パフォーマンスに大きな影響はないと思います。

bignumは元々、非常に大きなベース、たとえば65536以上のベースを持ちます。これは通常、従来のfixnumと整数の最大値です。

bignumの基数をどれだけ大きく設定するかはわかりませんが、fixnumや整数の代わりに使用するときに十分に大きく設定すると、最初のbignum-digitを超えることはありませんしたがって、操作は通常のfixnums / intとほぼ同じになります。

これにより、最初のbignum-digitを超えることのないbignumの最適化の機会が開きます。bignum-digitを超高速の1-bignum-digit操作に置き換えることができます。

そして、2番目のbignum-digitが必要になったらn桁のアルゴリズムに切り替えます。

これは、ビットフラグとすべての算術演算の検証操作で実装できます。大まかに言って、データブロックの最上位ビットが0に設定されている場合、最上位ビットを使用してbignumを表すことができます。通常のfixnum / intsであるかのように処理しますが、1に設定されている場合、ブロックをbignum構造として解析し、そこからbignumアルゴリズムを使用します。

これは、パフォーマンスヒットの最初の可能なソースであると思う単純なループイテレータ変数からのパフォーマンスヒットを回避する必要があります。

それは私の大まかな考えですが、あなたは私よりもよく知っている必要があるので提案です：-）

p.s。申し訳ありませんが、bignum-digitとbignum-baseの技術用語が何であるかを忘れました

Answer 4

あなたの削減は正しいですが、選択はあなたの言語のパフォーマンス特性に依存します。それはおそらくわからない！

言語を実装したら、パフォーマンスの違いを測定し、おそらくプログラマにデフォルトを選択するためのディレクティブを提供できます

Answer 5

結果は言語ごと、言語リビジョンごと、cpuごと、およびそれぞれ異なるため、独自のベンチマークを作成するまで、実際のパフォーマンスヒットを知ることはできません。 32ビット整数が16ビット整数の2倍のメモリを使用するという明らかな事実を除いて、これを測定する言語に依存しない方法はありません。

Answer 6

  

fixnumまたは整数で十分な場所でbignumを使用するオーバーヘッドはどのくらい小さいですか？小さく見せても最高の実装が可能か？

悪いニュースは、可能な限り最高のソフトウェア実装であっても、BigNumは組み込みの演算よりも桁違いに遅くなることです（つまり、ファクター10からファクター1000までのすべて）。

正確な数字はありませんが、そのような状況では正確な数字があまり役立つとは思いません。大きな数字が必要な場合は、それらを使用してください。そうでない場合は、しないでください。あなたの言語がデフォルトでそれらを使用している場合（どの言語が使用しますか？一部の動的言語は使用します＆＃8230;）、別の言語に切り替えることの不利な点がパフォーマンスの向上によって補われるかどうかを考えます（めったにないはずです）。

（大まかに翻訳できますが、大きな違いがありますが、それは重要ではありません。 （それが重要な場合のみ）別の言語を使用してください。言語は明らかにタスクに適していない。）

Answer 7

ドメイン固有である場合を除き、それだけの価値があるとはまったく思いません。

最初に頭に浮かぶのは、すべてのプログラム全体の小さなループです。小さなイテレータ変数はすべてビッグナムになりますか？怖い！

しかし、もしあなたの言語がかなり機能的であれば...多分そうではありません。