1

タイトルは複雑に聞こえるかもしれませんが、数行のコードで非常に理解しやすくなります。

NULLまたは実際の構造体を指す可能性のあるポインタの配列があるとします。私たちのタスクは、すべてのポインターをNULLに設定することです(削除は関係ありません)。

次の方法で実行できます。

 // first way
 array[i] = NULL;

 // second way
 if (array[i] != NULL)
      array[i] = NULL;

2番目の方法で実行した場合、すでにNULLになっている値の速度をいくらか節約できるでしょうか。配列がすでに50%NULLであるとしましょう。私の大学の講師はかつて、「比較はそれほど費用がかからないが、価値の変化は費用がかかる」と述べました。それは本当ですか?2番目の方法で速度を上げた場合、速度にプラスの影響はありますか?または、追加の比較は時間を無駄にするだけですか?

4

4 に答える 4

5

最初の方法は常に高速です。ポインタを読み取ってnullであることを確認してから書き込む必要があります。これは、単に書き込むよりも時間がかかります。比較自体を行うのにそれほど時間はかからないかもしれませんが、条件付き分岐を取ることの結果は間違いなく良くありません。[わかりました。コンパイラはそれを削除できますが、保証はされません]。

しかし、いつものようにパフォーマンスでは、「インターネットで質問することは、測定に代わるものではありません!」。

于 2013-02-02T11:43:31.863 に答える
2

何かを行うことを常に保存できれば、コンパイラは多くの場合、この機械的な変換を行います。それについて聞いたことがない。

何かを節約できる可能性がある状況を少なくとも1つ考えることができます。ランダムな場所に割り当てる巨大な配列があり、値が同じであることが多い場合。その場合、CPUがキャッシュラインを汚して、それを書き戻すことを余儀なくされるのを防ぐために、おそらくブランチのサイクルを費やしたいと思うでしょう。

于 2013-02-02T11:43:30.893 に答える
1

答えはいつものように「状況次第」です。問題セットの大きさ、および特定のマシンの特性について。実際の経験的証拠のプロファイリングに勝るものはありません。

あなたは本質的にこれらの1つを他のものと交換しています:

  • 条件分岐のコスト。
  • メモリアクセスのコスト。

最初のソリューションでは、配列要素ごとに、メモリへの書き込みのみが必要です。2番目のソリューションでは、読み取り、比較、および条件付き書き込みが必要です。読み取りが書き込みよりも安価で、比較が比較的安価である場合、NULLエントリが多いと、より高速になる可能性があります。

私の頭の中での答えは、最初の方法は、memcpy分岐せず(高価です!)、ゴミ箱に捨てる必要がないため、特に非一時的な書き込みで最適化された場合、最近のプロセッサではおそらく高速です。要素を含むCPUキャッシュは1回だけ読み取ります。

于 2013-02-02T11:45:25.180 に答える
0

基本的な原則から始めましょう:あなたのインストラクターがあなたに言ったことはしばしば正確に逆です。通常、書き込みは読み取りよりも高速です。具体的には(少なくとも最新のCPUでは)書き込みとは、アドレスと値をキューに入れることを意味します。CPUの他の部分は、その値のメモリへの書き込みを処理できますが、実行ユニットはさらに多くの命令を実行できます。ただし、書き込みキューがすでにいっぱいになっているときに、さらにデータを書き込もうとすると、命令ストリームが停止する可能性があります。

対照的に、比較を行うには、データがまだキャッシュにない場合、アドレスをメモリに書き出してから、データがメモリから到着するまでストールして、適切な比較に使用できるようにする必要があります。

比較では、フラグレジスタも使用されます。フラグレジスタは、ほとんどの命令で変更されるため、「レジスタ圧力」が大きくなります。これにより、他の方法では利用できる命令レベルの並列性を防ぐことができます。

さて、他の目的ですぐに使用する予定がない限り、一般的に、問題のデータでキャッシュを汚染することは避けたいと思うのは事実です。一部のキャッシュは、書き込みにキャッシュスペースを割り当てないことで、これを完全に回避します。つまり、最近データを読み取って既にキャッシュにある場合を除いて、データに書き込んでもキャッシュに移動しません。データをメインメモリに直接書き込むだけです。

最近の多くの(ほとんど?)プロセッサは、キャッシュポリシーに関係なく、常にメモリに直接書き込む命令も備えています。Intelは(たとえば)これらの非一時的なストア(たとえば、MOVNTQおよびMOVNTPS)を呼び出します。ただし、これらを正しく使用するには少し注意が必要です。通常のメモリ書き込みとは異なり、デフォルトではキャッシュの一貫性は保証されません。他のプロセッサが書き込みの結果を確認できるように、書き込み後にSFENCE命令を実行する必要があります。

比較を行う価値があるもう1つの場合は、1回の比較で大量の書き込みを回避できる場合です。たとえば、配列が非常にまばらで、数百のエントリのうち約1つだけがnull以外であったと仮定します。このような場合、(一例として)ビットマップの1ビットがポインターがnullかどうかを示すビットマップを使用できます。このような場合、単一の64ビット比較により、(たとえば)それぞれ64ビットの64の異なるポインターへの書き込みを回避できます。

ただし、ポインタを個別に確認しても利点はありません。具体的には、比較を行う前に各ポインタをキャッシュにロードする必要があるため、キャッシュを汚染しないように1つずつ比較することをお勧めします。自滅的な提案。

于 2013-02-02T13:57:12.407 に答える