c++ - 一般的な C++ 最適化手法のリスト

Question

一般的な C++ 最適化プラクティスの優れたリストを入手できますか?

最適化とは、コンパイラの設定を変更するのではなく、プログラムをより高速に実行できるようにソースコードを変更する必要があるということです。

score 24 · Accepted Answer

他の人が言ったことを繰り返します。パフォーマンスの向上という点では、より優れたアルゴリズムが勝つでしょう。

とは言っても、私は画像処理の仕事をしていますが、問題領域として粘着性が高くなる可能性があります。たとえば、何年も前に、次のようなコードの塊がありました。

void FlipBuffer(unsigned char *start, unsigned char *end)
{
    unsigned char temp;

    while (start <= end) {
        temp = _bitRev[*start];
        *start++ = _bitRev[*end];
        *end-- = temp;
    }
 }

これは、1 ビットのフレームバッファを 180 度回転させます。_bitRev は、反転されたビットの 256 バイトのテーブルです。このコードは、あなたが得ることができるほどタイトです。これは 8MHz 68K レーザープリンターコントローラーで実行され、法定サイズの紙に約 2.5 秒かかりました。詳細を省くために、顧客は 2.5 秒に耐えられませんでした。解決策は、これと同じアルゴリズムでした。違いはそれでした

私は 128K のテーブルを使用し、バイトではなくワードで操作しました (ワードでは 68K の方がはるかに快適です)。
ダフのデバイスを使用して、短いブランチに収まる限りループを展開しました
空白の単語をスキップする最適化を入れました
最後に、アセンブリで書き直して、sobgtr 命令 (1 を減算して大きい方に分岐) を利用し、適切な場所に「自由な」ポストインクリメントとプリデクリメントを配置しました。

つまり 5 倍: アルゴリズムの変更はありません。

要点は、問題のドメインとボトルネックの意味も理解する必要があるということです。画像処理では、アルゴリズムは依然として王様ですが、ループが余分な作業を行っている場合、その作業を数百万倍すると、それが代償になります。

score 17 · Accepted Answer

より良いプログラムを書くための 2 つの方法:

言語を最大限に活用する

Steve McConnell によるコードの完成
効果的な C++
優れた C++

アプリケーションのプロファイリング

コードのどの領域にどのくらいの時間がかかっているかを特定する
より良いデータ構造/アルゴリズムを使用して物事を高速化できるかどうかを確認してください

実行できる言語固有の最適化はあまりありません - 言語構造の使用に制限されています (#1 から学びます)。主な利点は、上記の 2 から得られます。

score 12 · Accepted Answer

いくつかのことを忘れないでください：
-「効率が小さいことを忘れる必要があります。たとえば、97％の確率で、時期尚早の最適化がすべての悪の根源です。」（c）Donald Knuth-
コードよりもアルゴリズムを最適化すれば、より多くを得ることができます。-プロファイラーまたは他の特別なツールによって検出される既存の
コードの遅い部分のみを最適化します。

score 9 · Accepted Answer

Agner Fogは、C++構造に関するいくつかのコンパイラの出力を分析する素晴らしい仕事をしました。彼の作品はここにあります：http ：//www.agner.org/optimize/ 。

インテルは、優れたドキュメントも提供しています。「インテル®64およびIA-32アーキテクチャー最適化リファレンス・マニュアル」は、http：//www.intel.com/products/processor/manuals/index.htmにあります。主にIA-32アーキテクチャを対象としていますが、ほとんどのプラットフォームに適用できる一般的なアドバイスが含まれています。明らかに、それとAgnerFogのガイドは少し交差しています。

他の回答で述べたように、マイクロ最適化は明らかに、プロファイリングとアルゴリズムの選択の後、プログラムを高速化するために実行したい最後のステップです。

score 5 · Accepted Answer

5

あなたはこれに興味があるかもしれません：C++Wikibookの最適化

于 2010-10-13T22:28:01.540 に答える

score 4 · Accepted Answer

思いついたサイトはありませんが、Sutter の著書「Exceptional C++」は C/C++ 開発に最適です。すべての C++ プログラマーがこの本を読むことを強くお勧めします。この本は、最適化だけでなく、言語の賢明な使用法についての優れた洞察を提供し、真に優れたプログラミングができるようにするためです。

score 2 · Accepted Answer

最適化の知恵を含むサイト/ソースを求めました。

いくつかの良いものが提案されました。

パフォーマンスの問題を特定する唯一の方法ではないにしても、プロファイリングが最善の方法であるとほぼ全員が言うだろうと付け加えておきます。

この民間の知恵がどこから来たのか、どのように正当化されたのかはわかりませんが、もっと良い方法があります.

追加した：

「間違ったアルゴリズム」がパフォーマンスを低下させる可能性があるのは事実ですが、それが唯一の方法ではないことは確かです。

私は多くのパフォーマンスチューニングを行っています。大規模なソフトウェアでは、通常、データ構造が多すぎて抽象化のレイヤーが多すぎると、パフォーマンスが低下します。

抽象オブジェクトへの無害なワンライナーメソッド呼び出しのように見えるものは、その呼び出しが何を犠牲にするかを忘れさせてくれます。この傾向を抽象化のいくつかのレイヤーに掛け合わせると、たとえば、インデックス付きの単純な配列で十分 (そして保守性も劣らず) であるにもかかわらず、イテレータやコレクションクラスなどの割り当てと収集にすべての時間を費やしていることがわかります。 "。

それが「常識」の問題です。多くの場合、それは知恵とは正反対です。

score 2 · Accepted Answer

コンパイラが異なれば最適化も異なるため、ほとんどの手法はコンパイラ固有のものです。

コンパイラに依存しない最適化のヒントが必要な場合は、次の 2 つを参考にしてください。

やらないでください。
(専門家のみ!): まだやらないでください。

(マイケル・A・ジャクソンに謝罪)

score 1 · Accepted Answer

ほとんどの最適化は言語に依存しません。コードを理解し、実行しているハードウェアを理解すると、ほとんどの低レベルの最適化を実行できます。

問題のドメインと適切なアルゴリズムを理解すると、高レベルの最適化を行うことができます。

私が考えることができる唯一のC++固有の最適化アドバイスは、「コードの意味を理解する」ことです。C ++が一時的なものをいつコピーするかを理解し、どのコンストラクタとデストラクタがいつ呼び出されるかを理解します。

また、関数ポインターよりもファンクターを優先します。前者はコンパイラーによってインライン化できるためです。一般に、実行時ではなくコンパイル時に可能な限り移動します。テンプレートを使用して、手間のかかる作業を行います。

そしてもちろん、1）最適化が必要であり、2）最適化が必要なものをプロファイリングして見つけ出すまで、最適化を試みないでください。

編集：インライン化されているファンクターと関数ポインターについて尋ねられたコメント。説明は次のとおりです。

関数は通常、個別にコンパイルされます。では、コンパイラーは、関数ポインターFPを引数として取る関数Fについて何を知っていますか？何もありません。Fがどこから呼び出されているかを調べる必要があります。おそらくそこで、FPがどの関数を指しているかについて明確な手がかりを見つけることができます。ここから呼び出されたときに、FPが常に関数Gを指すと判断できる場合は、はい、この特定の呼び出しサイトに対して、Gが内部にインライン化されたFのインライン化バージョンを作成できます。ただし、Fは他の場所からも呼び出され、別の関数ポインターが渡される可能性があるため、Fをインライン化せずにGを単純にインライン化することはできません。それでも、インライン化できるものを決定するには、コストのかかるグローバルな最適化が必要です。

代わりに、次のようなファンクターを渡すと想像してください。

struct Ftor {
  void operator()() { ... }
};

したがって、関数Fは次のようになります。

void F(const FTor& ft) {
  ...
  ft();
  ...
}

これで、コンパイラはどの関数が呼び出されるかを正確に認識します。関数の2行目はFtor :: operator（）を呼び出します。そのため、通話を簡単にインライン化できます。

もちろん、実際には、通常はテンプレート化するので、関数は任意のファンクタータイプで呼び出すことができます。

template <typename F>
void F(const F& ft) {
  ...
  ft();
  ...
}

score 1 · Accepted Answer

コードのプロファイルを作成して、実際に最も時間がかかっているものを見つけます
正しいアルゴリズムを使用していることを確認してください
多数の処理を行う場合は、キャッシュに慣れて、データのチャンクに対して可能な限りすべてを一度に実行して、キャッシュに何度もロードする必要がないようにしてください。

score 1 · Accepted Answer

多くの人が言っていることとは反対に、実行できる言語固有の最適化はたくさんあります。これは Wikibooks の優れたリソースです。コードを設計し、プロファイル、プロファイル、プロファイルを設計するときは、このことを念頭に置いてください。

score 1 · Accepted Answer

テンプレートメタプログラミングを使用すると、動的ポリモーフィズムからコンパイル時のポリモーフィズムに移行し、その過程で非常に最適なコードを生成できます。Alexandrescu のModern C++ Designは、TMP について詳しく説明している優れた本です。すべてのページが最適化に関係しているわけではありませんが、プログラムの設計において頻繁に考慮されます。

score 1 · Accepted Answer

申し訳ありませんが、参考文献はありませんが、山に追加する別の逸話があります。

Microsoft の CString オブジェクトをキーとして使用して生成していたかなり大きな std::map がありました。パフォーマンスは受け入れられませんでした。すべての文字列の長さが同じだったので、CString のインターフェイスをエミュレートするために、昔ながらの固定サイズの文字配列のクラスラッパーを作成しました。残念ながら、正確なスピードアップを思い出せませんが、それは顕著であり、結果として得られたパフォーマンスは十分以上でした。

依存するライブラリ構造について少し知る必要がある場合があります。

score 0 · Accepted Answer

取得できる最善の最適化は、設計を再検討し、パフォーマンスに関連するアプリケーションのパーツ/アルゴリズムをプロファイリングした後です。これは通常、言語固有ではありません。

つまり、（アイデアとして）わずかに優れたアルゴリズム（またはコレクション/コンテナークラス）を選択することでパフォーマンスが30％向上する場合、C ++関連のリファクタリングから期待できる向上は最大で2％になります。設計の改善により、30％を超えるものが得られる可能性があります。

具体的なアプリケーションがある場合、最善の戦略は、アプリケーションを測定してプロファイルすることです。プロファイリングは通常、どの部分がパフォーマンスに関連しているかを最も即座に把握します。

score 0 · Accepted Answer

最適化のためのいくつかのキャッチオールパスを次に示します。

最適化の問題には1 つの方法はありません...それらは常にハードウェア/ソフトウェア/システムの考慮事項に合わせて手動で調整されます。

最適なアルゴリズムがあると仮定します。

「アセンブリ出力の表示」および「最高の最適化」でコンパイルします
アセンブリ出力を見てください
コンパイラの最適化や不適切なキャッシングを台無しにする非効率性を特定する
スニペットを再コーディングする
それでも問題が解決しない場合は、2 に戻ります。
終わり

ここに見られる例: C で値を交換する最速の方法は何ですか?

一般的なヒント:

http://www.ceet.niu.edu/faculty/kuo/exp/exp6/figuree6-1.jpg :

最初に浮動小数点で試してください
定点秒でやってみる
あなたが本当にバラバラで、時間とお金がたくさんあるなら、アセンブリで試してみてください

http://www.asc.edu/seminars/optimization/fig1.gif :

メモリ、I/O、または CPU バウンドかどうかを確認します
制限要因となるものを攻撃する

c++ - 一般的な C++ 最適化手法のリスト

18 に答える 18

Related

Reference