最適化！ - それは何ですか？どうしたの？

Question

「高度に最適化されたコード」や、そのようなものを最適化する必要のある開発者についてよく聞く人がいます。しかし、独学で新しいプログラマーとして、私はそのようなことについて話すとき、人々が正確に何を意味するのか本当に理解したことはありません。

ケアの一般的な考え方を教えてください。また、いくつかの読書資料をお勧めします。冗談と説教は自由に行えます。

Answer 1

最適化とは、速度などのコンピュータプログラムを改善しようとすることです。最適化には、コンパイラがプログラムを改善して速度を向上させること、または同じように実行する人間が関与する可能性があるため、この質問は非常に幅広いです。

Answer 2

は、「何らかの形でより良いものを作る」という意味にゆっくりと使用する用語です。私たちはめったに何かを「最適化」しません。

最適化は、プログラムの一部を最適化するために行った変更です。 A 完全に最適化されたプログラムは、通常、開発者がウィンドウから読みやすさを捨てて、「壁の時間」を最小限に抑えるためにアルゴリズムを再現していないことを意味します。 （これは、「最適化されたコード」読みにくいことは、それだけでトレンドだという要件はありません。）

一つは、のために最適化することができます。

• メモリ消費 - プログラムまたはアルゴリズムの実行時のサイズを小さくしてください。

• CPU消費量 - 計算量を計算量が少なくするようにします。

• ウォール時間 - 代わりに、コンピュータのためのより良いあなたのアプリを作ることを、あなたはそれが簡単に人間がそれを読むために作ることができます - それは読みやす速く何か

• を作るために取るものは何でも。

一般的な（かつ過度に一般化された）コードを最適化するための技術は、次のとおり

• 変更性能特性を改善するためのアルゴリズム。 O（n^2）時間またはスペースを取るアルゴリズムをお持ちの場合は、そのアルゴリズムをO（n * log n）を取るアルゴリズムに置き換えてみてください。

• メモリ消費を軽減するには、コードを調べて無駄なメモリを探します。たとえば、文字列集約型アプリケーションを使用している場合、元の文字列からメモリを割り当てたりコピーしたりする代わりに、部分文字列参照（文字列へのポインタとその境界を定義するインデックスを含む参照）を使用することに切り替えることができます。

• できるだけ多くの中間結果をキャッシュします。たとえば、一連のデータの標準偏差を計算する必要がある場合は、std devを知る必要があるたびに、その1回の数値結果を保存します。

Answer 3

一般的なアイデアは、あなたがコンパイルフェーズであなたのソースツリーを作成するときに、それを解析してコードを生成する前に、あなたが特定の経験則に基づいて、追加のステップ（最適化）を行うことで、あなたは一緒に枝を折りたたみます使用されていないブランチを削除するか、複数回使用される一時変数に余分なノードを追加します。コードのこの部分のようなものの

思う：その2人の子孫を持つ+のノードが同一であることは明らかであろうパーサーに

 - 
    *  + 
    + 3 b c 
    b c 

に翻訳さ

a=(b+c)*3-(b+c) 

それらは一時変数tにマージされ、木は書き直されるでしょう：

N OWより良いパーサは、tは整数であるため、ツリーがさらにに単純化することができていることがわかります。最後になり

 * 
    t  2 

、あなたは上のコード生成ステップを実行したいの中間コード

int t=b+c; 
a=t*2; 

tはレジスタ変数としてマークされています。これはまさにアセンブリのために書かれたものです。

最終的に1つの注意点があります。ランタイムスピード以上に最適化することができます。また、メモリ消費量を最適化することもできます。展開ループや一時的なコピーを作成するとコードのスピードアップに役立ちますが、メモリ使用量も増えるので、目標とはトレードオフになります。

Answer 4

私が最近した最適化（不適切な決定を修正）の例です。非常に基本的ですが、単純な変更からでも良い利益を得ることができ、最適化は魔法ではないことを示しています。

アプリケーションでは、いくつかのLinkedListデータ構造があり、fooのさまざまなインスタンスを保持するために使用されていました。

アプリケーションが使用されていたとき、LinkedListedにオブジェクトXが含まれているかどうかを頻繁に確認していました.Xの数が増えたため、アプリケーションの実行速度が遅くなっていました。

プロファイラーを実行し、リストに含まれる各アイテムを繰り返して、最後に到達するか一致が見つかるまで 'myList.Contains（x）'コールにO（N）コールがあることに気付きました。これは間違いなく効率的ではなかった。

このコードを最適化するために私は何をしましたか？ほとんどのLinkedListデータ構造をHashSetsに切り替えました。これはO（1）の '.Contains（X）'呼び出しを行うことができます。

Answer 5

私はほとんど実用的なアドバイスなしで怒ってしまいます。

メジャーファースト。最適化は、重要な場所に行う必要があります。 高度に最適化されたコードは、多くの場合、保守が難しく、問題の原因となります。とにかくコードが実行を遅くさせない場所では、私は賢明に最適化の維持可能性を好みます。侵入型（計装型）と非侵入型（低オーバーヘッドの統計的）の両方のプロファイリングに慣れてください。プロファイリングされたスタックを読んで、排他的な時間が含まれる場所、特定のパターンが表示される理由、および問題点を特定する方法を理解することを学びます。

を測定できないものは修正できません。あなたのプログラムは、いくつかのパフォーマンス・インフラストラクチャーを通じて、それが行うこととそれが必要とする時間を報告してください。私はWin32のバックグラウンドから来ているので、私はパフォーマンスカウンターに慣れています。私はコード全体にそれらを振りかけるのに非常に寛大です。私もautomatized the code to generate themです。

最後に、最適化に関するいくつかの言葉。最適化についての議論は、コンパイラが自由に最適化するものに焦点を当てています。私の経験では、「高度に最適化されたコード」に対する最大の利益源は、他の場所に完全にあります。メモリアクセス。現代のアーキテクチャでは、CPUはメモリがパイプラインに供給されるのを待っている間、ほとんどの時間空転しています。 L1およびL2キャッシュミスの間に、TLBミス、NUMAノード間アクセス、さらにはディスクからページをフェッチする必要があるGPFさえも、最新のアプリケーションのメモリアクセスパターンは、最も重要な最適化の1つです。私はわずかに誇張しています。もちろん、メモリアクセスの局所性には効果がない反例のワークロードがあります。しかし、ほとんどのアプリケーションになります。具体的には、これらの手法が意味することは簡単です。データをメモリに集約して、単一のCPUが必要なすべてを含む厳しいメモリ範囲で動作できるようにします。キャッシュラインや現在のページ外のメモリを高価に参照する必要はありません。実際には、列ではなく行で配列にアクセスするという単純なことを意味します。

私はあなたがこの論文は、近代的なCPUアーキテクチャのために特別に設計されたキャッシュに敏感なアルゴリズムは、水の中から古い以前のベンチマークを吹くことができる方法を提示1995年にAlpha-Sort paper presented at the VLDB conferenceまで読んで推薦：

私たちは、その現代的なアーキテクチャを主張します アルゴリズム設計者に 階層の再利用を再検査する必要があります。 AlphaSortは、私はあなたが（講演スライドのための本から、またはGoogleの）最初の理論のビットを読むことをお勧め

Answer 6

...良いキャッシュに 局所性を得るために、クラスタ化 データ構造を使用しています。

• データ構造をアルゴリズムとは何ですか？O（）表記法はどのように計算するのですか？ O-complexityを下げるために使用できるデータ構造とアルゴリズムはどれですか？
  Book：Thomas H. Cormen、Charles E. Leiserson Ronald L. Rivest

• コンパイラおよびアセンブリ - コードを機械語命令

• コンピュータ・アーキテクチャに変換する方法 - CPU、RAM、キャッシュ、分岐予測は、アウトオブオーダー実行を...

• 動作をどのように動作しますかシステム - カーネルモード、ユーザーモード、スケジューリングプロセス/スレッド、ミューテックス、セマフォ、メッセージキュー

それぞれのビットを読んだ後、あなたはすべての差分の基本的な知識を持っている必要があります最適化のさまざまな側面。

注：私はこれを編集して、人々がブックのおすすめを追加できるようにしました。

Answer 7

コードを最適化することは、同じ結果をより短時間で得ることです。完全に最適化されたということは、アイデアがなくなったことを意味しています。私は、「完全に最適化された」コードの主張に大量の侮辱を投げます！そんなことはない。

あなたのアプリケーション/プログラム/モジュールをより速く実行したいですか？先に述べたように、最初に行うことは、プロファイリングとも呼ばれる測定です。最適化する場所を推測しないでください。あなたはそれほどスマートではなく、あなたは間違っています。私の推測はいつも間違っており、私の年の大部分はプロファイリングと最適化に費やされています。だから、あなたのためにそれを行うには、コンピュータを取得します。 PCの場合、VTuneは優れたプロファイラです。 VS2008にはプロファイラが組み込まれていると思いますが、私はそれを調べていません。それ以外の場合は、パフォーマンスカウンタを使用して関数と大量のコードを測定します。 MSDNでパフォーマンスカウンターを使用するためのサンプルコードがあります。

あなたのサイクルはどこに行くのですか？メインメモリからデータが来るのを待っている可能性があります。 L1 & L2キャッシュを読んでください。キャッシュの仕組みを理解することは、戦闘の半分です。ヒント：より緊密でコンパクトな構造を使用して、より多くのキャッシュラインに適合させます。

最適化は非常に楽しいです。そして決して終わらないこともあります。

最適化に関する素晴らしい本は、「グレートコードを書く：Randall Hydeの機械を理解する」です。

Answer 8

プログラムを最適化することを意味しますが、それはより速くプログラムを作るの

唯一の方法は、それが以下をやらせているより速く実行します：

• 少ない演算を使用するアルゴリズムを見つけます（N^2の代わりにN log N）
• あなたのマシンの遅いコンポーネントを避けてください（メインメモリの代わりにキャッシュにオブジェクトを保存するか、またはdの代わりにメインメモリにオブジェクトを保存してください） isk）;メモリ消費を削減することは、ほとんど常に助けになります！

またルール：最適化の機会を探している

• 、80-20ルールに準拠する典型的なプログラム・コードの20％が、実行時間の80％を占めます。
• 対策試行された最適化の前後の時間。しばしば十分なほど、最適化はしません。
• プログラムが正しく実行された後でのみ最適化してください。

また、を表示さプログラムがより速くなるために作る方法があります。

• バックエンドタスクとは別のGUIのイベント処理は、フロントエンドの「スナッピー」を維持するためのバックエンド計算とのユーザー視覚的な変更の優先順位付け
• 長い操作を実行している間に何かを読むようにユーザーに指示します（インストーラーによって表示されるスライドショーに気づきましたか？）

Answer 9

最適化を開始する前に、アプリケーションで正しい結果が得られていることを確認してください。

Answer 10

これは良い質問です。

通常、ベストプラクティスは、1）必要な処理を行うためのコードを書いてください.2）それが問題の場合にのみ、パフォーマンスを処理してください。プログラムが「十分に速い」場合、それは問題ではありません。

プログラムの速度が十分でない場合（待機するような場合）、パフォーマンスチューニングをいくつか試みてください。パフォーマンスチューニングはプログラミングに似ていません。プログラミングでは、最初に思ってから何かをします。パフォーマンスチューニングでは、まず考え方は間違いです。それはと推測します。です。

修正するものを推測しないでください。プログラムが何をしているのかを診断する。 誰もがそれを知っていますが、主にそれはとにかく行います。 「X、Y、Zの問題はありますか」と言うのは当然ですが、初心者だけが推測に基づいて動作します。プロは「しかし、私はおそらく間違っている」と言います。

パフォーマンスの問題を診断するさまざまな方法があります。

最も簡単なのは、アセンブリ言語レベルでプログラムをシングルステップ実行するだけです。ショートカットを使用しないでください。そうすれば、プログラムが不必要なことをしている場合、は同じことをしており、痛いほど明らかになります。

もう1つは、プロファイリングツールを入手することです。他の人が言うように、測定、測定、測定。

個人的に私は測定を気にしません。パフォーマンス上の問題を特定する目的で、あやふやな顕微鏡だと思います。私はthis methodとthis is an example of its useを好む。

幸運。

ADDED：この演習を数回行うと、コーディングプラクティスがパフォーマンス上の問題を引き起こす傾向があることがわかり、直感的に回避できます。 （これは、早期の最適化とは微妙に異なります。これは、最初にパフォーマンスを気にする必要があると仮定しています。非常に問題は避けるように努めています。）しかし

Answer 11

、私は本当に正確な事柄について話すとき、人々が意味何をすべきか理解したことがありません独学、新しいプログラマーとして。

私はあなたと秘密を共有しましょう：誰もしません。私たちが数学的に何を知っていて、何が遅いのかが分からない特定の分野があります。しかし、ほとんどの場合、パフォーマンスは複雑すぎて理解できません。コードの一部を高速化すると、別のコードを遅くする可能性があります。3つのいずれかに該当する場合を除きしたがって

は、一つの方法は、他のよりも高速であることを示しています誰もが、彼らはただ推測している良い可能性があります：

1. 彼らはデータを持っている
2. 彼らがしています彼らが知っているアルゴリズムを選択するのは数学的に高速です。
3. 彼らは、数学的に高速なデータ構造を選択しています。