世界最速の atof 実装はどこにありますか?

精度要件は何ですか?本当に「正しい」必要がある場合 (常に指定された 10 進数に最も近い浮動小数点値を取得する)、標準ライブラリのバージョンを打ち負かすのはおそらく難しいでしょう (すでに行ったロケールサポートの削除を除いて)。これには、任意精度の演算が必要です。 1 つまたは 2 つの ulp のエラー (およびサブノーマルの場合はそれ以上) を許容する場合は、cruzer によって提案された種類のアプローチが機能し、より高速になる可能性がありますが、0.5ulp 未満の出力は確実に生成されません。整数部分と小数部分を別々に計算し、最後に分数を計算すると、精度が向上します (たとえば、12345.6789 の場合、6*.1 + 7*.01 + 8 ではなく、12345 + 6789 / 10000.0 として計算します)。 *.001 + 9*0.0001) 0.1 は無理数の 2 進分数であり、0.1^n を計算すると誤差が急速に蓄積されるためです。これにより、浮動小数点の代わりに整数を使用してほとんどの計算を行うこともできます。

(IIRC) 286 以降、BCD 命令はハードウェアに実装されておらず、現在は単純にマイクロコード化されています。特に高性能である可能性は低いです。


コーディングを終えたばかりのこの実装は、デスクトップに組み込まれている「atof」の 2 倍の速さで実行されます。 1024*1024*39 の数値入力を 2 秒で変換しますが、私のシステムの標準的な gnu 'atof' では 4 秒かかります。 (セットアップ時間とメモリ取得などすべてを含みます)。

更新: 申し訳ありませんが、2 倍の速さの請求を取り消さなければなりません。変換するものがすでに文字列になっている場合は高速ですが、ハードコードされた文字列リテラルを渡す場合は atof とほぼ同じです。ただし、ここでは省略します。おそらく、ragel ファイルとステート マシンを微調整することで、特定の目的のためにより高速なコードを生成できる可能性があります。

https://github.com/matiu2/yajp

興味深いファイルは次のとおりです:

https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp

https://github.com/matiu2/yajp/blob/master/number.hpp

また、変換を行うステート マシンにも興味があるかもしれません:


各状態が N 番目の入力桁または指数桁を処理する状態マシンに相当するものを (手動で) 構築したいようです。このステート マシンは、ツリーのような形になります (ループはありません!)。目標は、可能な限り整数演算を行い、(明らかに) 状態の状態変数 (「先頭のマイナス」、「位置 3 の小数点」) を暗黙的に記憶し、そのような値の割り当て、保存、および後でフェッチ/テストを回避することです。 .入力文字のみに単純な古い「if」ステートメントを使用してステートマシンを実装します(したがって、ツリーはネストされたifのセットになります)。バッファ文字へのインライン アクセス。 getchar への関数呼び出しは必要ありません

先行ゼロは単純に非表示にすることができます。とてつもなく長い先頭のゼロ シーケンスを処理するには、ここでループが必要になる場合があります。最初のゼロ以外の数字は、アキュムレータをゼロにしたり、10 を掛けたりすることなく収集できます。最初の 4 ~ 9 桁のゼロ以外の数字 (16 ビットまたは 32 ビットの整数の場合) は、定数値 10 による整数乗算で収集できます (ほとんどのコンパイラでは、数回のシフトと加算に変換されます)。 [上に:ゼロ以外の数字が見つかるまでゼロの数字は何の作業も必要とせず、N 個の連続するゼロに対して 10^N を乗算する必要があります。これらすべてをステートマシンに配線できます]。最初の 4 ~ 9 に続く数字は、マシンのワード サイズに応じて 32 ビットまたは 64 ビットの乗算を使用して収集できます。精度は気にしないので、32 ビットまたは 64 ビットの値を収集した後は、単純に数字を無視できます。アプリケーションがこれらの数値で実際に行うことに基づいて、ゼロ以外の数字の固定数がある場合、実際に停止できると思います。数字列に小数点があると、ステート マシン ツリーに分岐が発生します。そのブランチはポイントの暗黙的な位置を知っているため、後で適切に 10 のべき乗でスケーリングする方法を知っています。このコードのサイズが気に入らない場合は、努力すれば、いくつかのステート マシンのサブツリーを組み合わせることができるかもしれません。

[上に:整数部分と小数部分を別々の (小さい) 整数として保持します。これには、整数部分と小数部分を結合するために最後に追加の浮動小数点演算が必要になりますが、おそらく価値はありません].

[上から:数字ペアの 2 文字を 16 ビット値に収集し、16 ビット値を検索します。これにより、メモリ アクセスと引き換えにレジスタでの乗算が回避されます。おそらく、最新のマシンではうまくいきません].

「E」に遭遇すると、上記のように指数を整数として収集します。事前計算された乗数のテーブルで正確に事前計算された/スケーリングされた 10 の累乗を検索し ("-" 符号が指数に存在する場合は逆数)、収集された仮数を乗算します。 (浮動小数点除算は絶対に行わないでください)。各指数収集ルーチンはツリーの異なるブランチ (リーフ) にあるため、10 の累乗のインデックスをオフセットすることによって、見かけ上または実際の小数点の位置を調整する必要があります。

[おまけ:ptr++ のコストを回避できます 数値の文字がバッファーに線形に格納され、バッファーの境界を越えていないことがわかっている場合。ツリー ブランチに沿った k 番目の状態では、k 番目の文字に *(start+k) としてアクセスできます。 .優れたコンパイラは通常、アドレッシング モードでインデックス付きオフセットの "...+k" を隠すことができます。]

正しく実行すると、このスキームは、ゼロ以外の桁ごとに約 1 つの安価な乗加算、仮数の浮動小数点への 1 つのキャスト、指数と小数点の位置によって結果をスケーリングするための 1 つの浮動小数点乗算を実行します。

上記は実装していません。ループ付きのバージョンを実装しましたが、かなり高速です。