13

stdint.hヘッダーには、タイプに対応するためのint_fastest_tとがありません。整数型の幅が重要ではない場合、パフォーマンスへのペナルティを最小限に抑えて最大量のビットを処理できる整数型をどのように選択しますか？たとえば、単純なアプローチを使用してバッファ内の最初のセットビットを検索している場合、次のようなループが考えられます。uint_fastest_t{,u}int_fastX_t

// return the bit offset of the first 1 bit
size_t find_first_bit_set(void const *const buf)
{
    uint_fastest_t const *p = buf; // use the fastest type for comparison to zero
    for (; *p == 0; ++p); // inc p while no bits are set
    // return offset of first bit set
    return (p - buf) * sizeof(*p) * CHAR_BIT + ffsX(*p) - 1;
}

当然、を使用charすると、よりも多くの操作が発生しintます。ただし、32ビットシステムなどlong longで使用するオーバーヘッドよりもコストのかかる操作になる可能性があります。int

私の現在の仮定は主流のアーキテクチャであり、の使用がlong最も安全な方法です。32ビットシステムでは32ビット、64ビットシステムでは64ビットです。

4

9 に答える 9

11

int_fast8_t正しい実装では常に最速の整数型です。8ビットよりも小さい整数型は存在できません（CHAR_BIT>=8必須であるため）。また、int_fast8_tは少なくとも8ビットの最速の整数型であるため、最速の整数型である期間です。

于 2010-09-12T14:45:10.733 に答える
3

理論的にintは、最善の策です。CPUのネイティブレジスタサイズにマップする必要があるため、要求している意味で「最適」である必要があります。

ただし、一部のCPUではint-64またはint-128の方がint-32よりも高速であることに気付く場合があります。これらはレジスタサイズよりも大きいものの、ループの反復回数が減るため、ループの反復回数が減る可能性があるためです。ループのオーバーヘッドを最小限に抑えるか、DMAを利用してデータをより高速にロード/保存することにより、より効率的に処理します。

（たとえば、ARM-2プロセッサでは、1つの32ビットレジスタをロードするのに4メモリサイクルかかりましたが、2つを連続してロードするのに5サイクル、4つを連続してロードするのに7サイクルしかかかりませんでした。上記のルーチンは、次のように使用するように最適化されます。解放できるレジスターの数が多いため（通常は8〜10）、ループの反復ごとに複数のレジスターを使用することで、最大3〜4倍高速に実行できます）

確実にする唯一の方法は、いくつかのルーチンを作成し、それらを特定のターゲットマシンでプロファイリングして、どれが最高のパフォーマンスを生み出すかを見つけることです。

于 2010-09-12T08:27:49.303 に答える
3

質問が本当に理解できるかどうかはわかりませんが、なぜintを使用しないのですか？私の（間違った、つまりC ++の無料ドラフトコピー）標準から引用すると、「プレーンintは、実行環境のアーキテクチャによって提案される自然なサイズを持っています。」

ただし、特定の操作に最適な整数型が必要な場合は、操作によって異なると思います。大きなデータバッファの最初のビットを見つけようとしたり、整数のシーケンスで数値を見つけたり、それらを移動したりすると、最適なタイプが完全に異なる可能性があります。

編集：

価値があるものは何でも、私は小さなベンチマークを行いました。私の特定のシステム（Linuxを搭載したIntel i7 920、gcc -O3）では、この特定の例では、長いint（64ビット）がプレーンなint（32ビット）よりもかなり高速であることがわかりました。私は反対を推測したでしょう。

于 2010-09-12T08:25:49.900 に答える
2

最速の実装があることを確認したい場合は、推測するのではなく、実行する予定のシステムでそれぞれをベンチマークしてみませんか？

于 2010-09-12T08:03:36.847 に答える
1

size_tタイプ（符号なしタイプの場合）およびptrdiff_t（符号付きタイプの場合）は、通常、任意のプラットフォームで非常に効率的な整数型に対応すると思います。

しかし、作成されたアセンブラーを検査してベンチマークを実行することほど、それを証明することはできません。

ここと他の返信で、さまざまなコメントを含めて編集します。

size_tそしてptrdiff_t、C99で標準的であり、アーキテクチャに関連していると合理的に仮定できる唯一のtypedefです。

標準の整数型（、、、、、）には5つの異なるランクcharがあります。すべての力は、幅8、16、32、64、および近い将来128のタイプを持つようになります。その結果 、32ビットに固定されます。その定義はプラットフォームの効率とは何の関係もありませんが、その幅の要件によって制約されるだけです。shortintlonglong longint

于 2010-09-12T08:15:17.460 に答える
1

答えはintそれ自体です。少なくともC++では、標準の3.9.1/2は次のように述べています。

プレーンintは、実行環境のアーキテクチャによって提案される自然なサイズを持っています

標準文書はありませんが、Cについても同じことが言えると思います。

于 2010-09-12T08:26:34.880 に答える
0

gccでコンパイルしている場合は、最初のビットセットを見つけるために__builtin_ffs（）を使用することをお勧めします。

組み込み関数：int __builtin_ffs（unsigned int x）1に加えてxの最下位1ビットのインデックスを返すか、xがゼロの場合はゼロを返します。

これは、（多くの場合、単一の）ネイティブアセンブリ命令にコンパイルされます。

于 2010-09-12T20:18:22.557 に答える
0

質問が不完全なため、この質問に答えることはできません。例えとして、次の質問を考えてみましょう。

最速の車両は何ですか

ブガッティヴェイロン？確かに速いですが、ロンドンからニューヨークに行くには良くありません。

質問に欠けているのは、整数が使用されるコンテキストです。上記の元の例では、配列が大きくてスパースである場合、8、32、または64ビット値の間に大きな違いが見られるとは思えません。 CPU制限の前にメモリ帯域幅の制限に達している。

重要な点は、アーキテクチャはさまざまな整数型のサイズを定義しないということです。それを行うのはコンパイラ設計者です。設計者は、特定のアーキテクチャのタイプごとにさまざまなサイズの長所と短所を慎重に比較検討し、最も適切なものを選択します。

ほとんどの操作ではintが32ビットに使用されるので十分なので、64ビットシステムの32ビットintが選択されたと思います。メモリ帯域幅が制限要因であるため、メモリ使用量の節約がおそらく最も重要な要因でした。

于 2010-09-13T09:41:36.000 に答える
0

既存のすべての主流アーキテクチャlongでは、ループスループットに関して現在最速のタイプです。

于 2010-09-14T02:45:49.177 に答える