20

US-en ロケール、ASCII、および非科学表記に最適化された IA32 での非常に高速な atof() 実装を探しています。Windows のマルチスレッド CRT は、isdigit() を呼び出すたびにロケールの変更をチェックするため、ここでは惨めに機能しません。私たちの現在のベストは、perl + tcl の atof 実装のベストから導き出されたもので、msvcrt.dll の atof を桁違いに上回っています。もっとうまくやりたいのですが、アイデアがありません。BCD 関連の x86 命令は有望に思えましたが、perl/tcl C コードを上回るパフォーマンスを得ることができませんでした。SO'ers はそこにある最高のものへのリンクを掘り下げることができますか? 非 x86 アセンブリ ベースのソリューションも歓迎します。

最初の回答に基づく説明:

このアプリケーションでは、最大 2 ulp の不正確さは問題ありません。
変換される数値はネットワークを介して小さなバッチで ASCII メッセージで到着し、アプリケーションはそれらを可能な限り低いレイテンシーで変換する必要があります。

4

6 に答える 6

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を計算すると、エラーが急速に蓄積されます。これにより、floatの代わりに整数を使用してほとんどの計算を実行することもできます。

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

于 2008-09-19T02:26:15.450 に答える
5

コーディングを終えたばかりのこの実装は、デスクトップに組み込まれている「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

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

数値解析ステート マシン図

于 2011-11-14T12:53:10.113 に答える
3

各状態が 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 回実行します。

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

于 2012-05-03T04:18:13.693 に答える
2

役に立ちそうなものを実装しました。atofと比較すると約5倍速く、一緒に使うと__forceinline約10倍速くなります。もう 1 つの優れた点は、crt の実装とまったく同じ演算を行うように仕立て上げられていることです。もちろん、いくつかの短所もあります。

  • 単精度浮動小数点のみをサポートし、
  • #INF などの特別な値はスキャンしません...
__forceinline bool float_scan(const wchar_t* wcs, float* val)
{
int hdr=0;
while (wcs[hdr]==L' ')
    hdr++;

int cur=hdr;

bool negative=false;
bool has_sign=false;

if (wcs[cur]==L'+' || wcs[cur]==L'-')
{
    if (wcs[cur]==L'-')
        negative=true;
    has_sign=true;
    cur++;
}
else
    has_sign=false;

int quot_digs=0;
int frac_digs=0;

bool full=false;

wchar_t period=0;
int binexp=0;
int decexp=0;
unsigned long value=0;

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
    if (!full)
    {
        if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
        {
            full=true;
            decexp++;
        }
        else
            value=value*10+wcs[cur]-L'0';
    }
    else
        decexp++;

    quot_digs++;
    cur++;
}

if (wcs[cur]==L'.' || wcs[cur]==L',')
{
    period=wcs[cur];
    cur++;

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (!full)
        {
            if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
                full=true;
            else
            {
                decexp--;
                value=value*10+wcs[cur]-L'0';
            }
        }

        frac_digs++;
        cur++;
    }
}

if (!quot_digs && !frac_digs)
    return false;

wchar_t exp_char=0;

int decexp2=0; // explicit exponent
bool exp_negative=false;
bool has_expsign=false;
int exp_digs=0;

// even if value is 0, we still need to eat exponent chars
if (wcs[cur]==L'e' || wcs[cur]==L'E')
{
    exp_char=wcs[cur];
    cur++;

    if (wcs[cur]==L'+' || wcs[cur]==L'-')
    {
        has_expsign=true;
        if (wcs[cur]=='-')
            exp_negative=true;
        cur++;
    }

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (decexp2>=0x19999999)
            return false;
        decexp2=10*decexp2+wcs[cur]-L'0';
        exp_digs++;
        cur++;
    }

    if (exp_negative)
        decexp-=decexp2;
    else
        decexp+=decexp2;
}

// end of wcs scan, cur contains value's tail

if (value)
{
    while (value<=0x19999999)
    {
        decexp--;
        value=value*10;
    }

    if (decexp)
    {
        // ensure 1bit space for mul by something lower than 2.0
        if (value&0x80000000)
        {
            value>>=1;
            binexp++;
        }

        if (decexp>308 || decexp<-307)
            return false;

        // convert exp from 10 to 2 (using FPU)
        int E;
        double v=pow(10.0,decexp);
        double m=frexp(v,&E);
        m=2.0*m;
        E--;
        value=(unsigned long)floor(value*m);

        binexp+=E;
    }

    binexp+=23; // rebase exponent to 23bits of mantisa


    // so the value is: +/- VALUE * pow(2,BINEXP);
    // (normalize manthisa to 24bits, update exponent)
    while (value&0xFE000000)
    {
        value>>=1;
        binexp++;
    }
    if (value&0x01000000)
    {
        if (value&1)
            value++;
        value>>=1;
        binexp++;
        if (value&0x01000000)
        {
            value>>=1;
            binexp++;
        }
    }

    while (!(value&0x00800000))
    {
        value<<=1;
        binexp--;
    }

    if (binexp<-127)
    {
        // underflow
        value=0;
        binexp=-127;
    }
    else
    if (binexp>128)
        return false;

    //exclude "implicit 1"
    value&=0x007FFFFF;

    // encode exponent
    unsigned long exponent=(binexp+127)<<23;
    value |= exponent;
}

// encode sign
unsigned long sign=negative<<31;
value |= sign;

if (val)
{
    *(unsigned long*)val=value;
}

return true;
}
于 2009-10-28T16:20:40.910 に答える
1

一部のデータ交換ファイルの解析中に Winforms アプリケーションの実行が非常に遅くなったことを覚えています。私たちは皆、それが db サーバーのスラッシングだと思っていましたが、賢明な上司は実際には、解析された文字列を小数！

最も簡単な方法は、文字列内の各桁 (文字) に対してループし、現在の合計を保持し、合計に 10 を掛けてから、次の桁の値を加算することです。文字列の最後に到達するか、ドットに遭遇するまで、これを続けます。ドットに遭遇した場合は、整数部分を小数部分から分離し、各桁を 10 で割る乗数を用意します。あなたが行くようにそれらを追加し続けます。

例: 123.456

現在の合計 = 0、1 を追加 (現在は 1) 現在の合計 = 1 * 10 = 10、2 を追加 (現在は 12) 現在の合計 = 12 * 10 = 120、3 を追加 (現在は 123) ドットに遭遇、準備小数部分の乗数 = 0.1、4 倍、0.4 を取得、現在の合計に追加、123.4 乗数 = 0.1 / 10 = 0.01、5 倍、0.05 を取得、現在の合計に追加、123.45 乗数 = 0.01 / 10 = 0.001、 6 を掛けて 0.006 を取得し、現在の合計に追加すると 123.456 になります

もちろん、数値の正確性と負の数値をテストすると、さらに複雑になります。しかし、入力が正しいと「想定」できれば、コードをより単純かつ高速にすることができます。

于 2008-09-19T02:06:52.640 に答える
0

GPUにこの作業をさせることを検討しましたか? 文字列を GPU メモリにロードしてすべて処理させることができれば、プロセッサよりもはるかに高速に実行される優れたアルゴリズムを見つけることができます。

または、FPGA で実行する - 任意のコプロセッサを作成するために使用できる FPGA PCI-E ボードがあります。DMA を使用して、変換する文字列の配列を含むメモリの部分に FPGA をポイントし、変換された値を残してそれらを通過させます。

クアッドコアプロセッサを見たことがありますか? これらのほとんどの場合の本当のボトルネックは、とにかくメモリアクセスです...

-アダム

于 2008-09-19T02:39:55.477 に答える