c - C の配列で Duff の Device を使用できますか?

Question

ここにループがあり、より高速に実行したいと考えています。大きな配列を渡しています。最近、Duff の Device を for ループに適用できると聞きました。何か案は？

for (i = 0; i < dim; i++) {
    for (j = 0; j < dim; j++) {
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
    }
}

score 19 · Accepted Answer

ダフのデバイスを使用しないでください。千人の保守プログラマーがあなたに感謝します。私はトレーニング会社で働いていました.Cプログラミングコースの最初の10ページでデバイスを紹介するのは面白いと誰かが思った. （コースのその部分を書いた人が明らかにしたように）あなたが「kewl」コーディングを信じていない限り、インストラクターとして対処することは不可能でした.

言うまでもなく、私はできるだけ早くコースから削除しました。

score 5 · Accepted Answer

なぜ高速化したいのですか？

実際のパフォーマンスの問題はありますか?

もしそうなら、プロファイリングを行って、これが十分な頻度で実行されていること、したがって最適化する価値があることを発見しましたか?

もしそうなら、あなたはそれを 2 つの方法で書きたくなるかもしれません。今の簡単な方法と Duff's Device を使った方法、またはその他の好きな方法です。

その時点で、パフォーマンスをテストします。あなたは驚くかもしれません。最新のオプティマイザーは非常に優れており、最新の CPU は非常に複雑であるため、ソースレベルの最適化はしばしば非生産的です。(私はかつて、非常に長い時間がかかるループでこれを実行しましたが、ループを強化すると、たとえ間接的なものを導入したとしても、パフォーマンスが向上することがわかりました。マイレージはほぼ確実に変化します。)

最後に、Duff's Device が実際に高速である場合、この単純で最適化可能なコードを使用して、次のコンパイラバージョンでパフォーマンスがまったく向上しない可能性があるメンテナンスの問題を置き換える価値があるかどうかを判断する必要があります。

score 3 · Accepted Answer

手でループを展開しないでください。もしあれば、非常にプラットフォーム固有の利点しか得られません. すべての優れたコンパイラはループをアンロールできますが、メインメモリから長いプログラムを読み取るためにより多くのメモリ帯域幅を消費するため、コードを高速化することさえ保証されていません。

ループを高速に実行したい場合は、RIDX が計算するものdstは何でも順次アクセスするようにして、キャッシュミスの数を最小限に抑える必要があります。それ以外に、ループを高速化する方法がわかりません。

score 2 · Accepted Answer

Duff's Device は、単純にループを展開するための手法です。そしてどんなループも展開できるので、ダフの仕掛けが使えます。

score 2 · Accepted Answer

ステートメントを実装するための命令サイクル数

dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];

ループのオーバーヘッドをはるかに上回るため、ループの展開は割合ベースではほとんど役に立ちません。

score 2 · Accepted Answer

これを理解して利益を得ることができたとしても、それはわずかなものであり、決して複雑さを正当化するものではありません.

エネルギーをレベルアップして、ソリューション全体を再考する方がよいでしょう。おそらく、値をコピーするのではなく、変換配列を作成し、必要に応じて間接的に回答を検索することにもう少し時間を費やすことができます (画像を作成するのにはあまり良い考えではありません-別の方法で表示しようとしているだけです)。

または、まったく異なるアプローチがあるかもしれません。問題全体を見て、現在のアプローチと概念を完全に捨てて、この実装に縛られすぎているために考慮していないものがあるかどうかを確認してください。

お使いのグラフィックスカードでこの作業を実行できますか?

高いレベルで問題を再考することは、あなたが思っているよりもはるかに頻繁に機能します。

編集:サンプルをさらに見ると、画像のブロックを取得して、ピクセルごとに別の画像にコピーしているように見えます。もしそうなら、マクロを取り除き、代わりにバイトごとにコピーする方法、またはブロック移動アセンブリ関数を使用して結果のエッジを調整して一致させる方法がほぼ確実にあります。

または、間違っていると推測したかもしれませんが、ピクセル単位よりも大きなスケールで見ることは、ループを展開するよりもはるかに役立つ可能性があります。

score 1 · Accepted Answer

RIDX() 関数の動作によっては、これが Duff's Device の候補になると思います。しかし、誰かがあなたのためにコードを書くことを期待しないでください... また、コードを適切にフォーマットして、実際に読みやすいようにすることもできます。

score 1 · Accepted Answer

おそらく、dim が 2 のべき乗であるか、ターゲットシステムに高速モジュラスがある限り。今日新しいことを学びました。私は独自に 5 年前にこのコンストラクトを発見し、memCopy() ルーチンに落とし込みました。誰かわかったね：）

score 0 · Accepted Answer

ちなみに、いいえ。Duff's Deviceは、ハードウェアレジスタに書き込むためのものでした（したがって、コピーのターゲットは常に同じアドレスでした）。

このようなコピーには、Duff's Deviceのようなものを実装できますが、明確さとメンテナンスのコストがかかります。私はそれが問題であることを確認するために最初にプロファイルを作成します。また、インデックス作成を単純化できるかどうかも調べます。これにより、コンパイラーがループを展開するという汚い作業を実行できるようになる可能性があります。

score 0 · Accepted Answer

これを使用する場合は、パフォーマンス要件の観点から、改善が実際に、重要であり、必要であるかどうかを判断するために、必ず測定してください。そうなるとは思えません。

大きなループの場合、Duffのデバイスによって処理される残りの部分は操作のわずかな割合になります。残りの部分が重要な小さなループの場合、そのようなループが多数ある場合にのみメリットがあります（ループ内にあるため）。定義上、ループはそれほど長くはかかりません！それでも、コンパイラのオプティマイザは、コードを読み取れなくすることなく、同等またはそれ以上のパフォーマンスを発揮する可能性があります。また、Duffのデバイスを適用すると、オプティマイザーがより効果的な最適化を適用できなくなる可能性があります。そのため、Duffを使用する場合は、それを測定する必要があります。

あなたがこれを節約する可能性が高いときはいつも（もしあれば）、あなたはおそらくこの質問への回答を読むことに何度か無駄になっているでしょう。

score 0 · Accepted Answer

ダフのデバイスは、展開されたループでは最適化されたソリューションではない可能性があります。

ポートにビットを送信した後、別のポートにクロックパルスを送信する機能がありました。各ビットの機能は次のとおりです。

  if (bit == 1)
  {
     write to the set port.
  }
  else
  {
     write to the clear port.
  }
  write high clock bit.
  write low clock bit.

これは、ビットシフトとビットカウントのインクリメントと共に、Duff のデバイスループに入れられました。

ビットの代わりにニブル値 (ニブルは 4 ビット) を使用して、ループの効率を改善しました。switch ステートメントはニブル値に基づいていました。これにより、ステートメントなしで 4 ビットを処理できるようになりif、命令キャッシュ (パイプライン) を介したフローが改善されました。

ダフのデバイスが最適なソリューションではない場合があります。より効率的なソリューションの基盤となる可能性があります。

score 0 · Accepted Answer

最新のコンパイラは、最適化が有効になっている場合に既にループ展開を行っているため、Duff のデバイスは時代遅れになります。コンパイラは、コンパイルターゲットに最適なレベルのアンロールを行うよりもよく知っているため、それを行うために追加のコードを記述する必要はありません。当時は巧妙なハックでしたが、最近ではダフのデバイスは歴史的な好奇心に過ぎず、優れたプログラミング手法ではありません。

score 0 · Accepted Answer

最後に、最適化を行う人は誰でも、関係者全員が適切に文書化され、変数、関数などの意味のある正しい綴りの名前を使用して、可能な限り自己文書化されたスタイルで記述されていることを確認する必要があります。したがって、コメントとコードが同期しなくなります。

最適化の必要性は尽きることがありません。私は大学院生と話していましたが、malloc()/free() が壊れており、1 回のパスでこれまでに試みられた最大の遺伝子データファイルに取り組んでいました。しばらくすると、ヒープが断片化しすぎて、呼び出し元の関数に割り当てる連続した RAM のブロックを malloc で見つけることができなくなりました。彼は、malloc が 32k 境界でのみメモリのブロックを発行するライブラリに切り替える必要がありました。古いライブラリよりも 160% 多くのメモリを必要とし、実行速度はかなり遅くなりましたが、作業は完了しました。

ダフのデバイスやその他の多くの最適化を使用して、コンパイラが最適化を最適化して、あいまいな壊れたオブジェクトコードにならないように注意する必要があります。自動並列化ツールを使用する環境に入ると、これはさらに問題になります。

最適化のレベルが低いほど、将来の最適化でコードが壊れる可能性が高くなると思います。複数のプラットフォームで実行するように設計されたコードで改行を破棄し、各プラットフォームの印刷および書き込み関数に改行を戻すという私の習慣は、このスレッドで説明されているいくつかの事柄で問題に遭遇することがわかります。

-gcouger

c - C の配列で Duff の Device を使用できますか?

13 に答える 13

Related

Reference