最適化 (情報工学)

コンピュータ関連において最適化（英: Optimization）という語は、最適化問題のそれを指すことも多いが、ここでは、コンパイラ最適化などに似た話題について説明する（「情報工学」と記事名には付いているが、全く information engineering の話題ではない）。コンピュータシステムは、主としてコストパフォーマンス上の理由から、効率的に（efficiently）動作することが望ましいことが多い。例えば、コンパイラ最適化は、高速化のためだったり、メモリの使用量を削減するためだったり、電力消費を抑えるためだったりする。最適化の対象となるシステムは、1つのプログラムの場合もあるし、複数のコンピュータの場合もあるし、インターネットのようなネットワーク全体の場合もある。
"optimization" という単語の語源は "optimal"（最適な、最善な）と同じだが、最適化によって真に最適なシステムとなることは稀である。最適化されたシステムは一般にある面でのみ最適となる。プログラムの実行時間を削減するためにメモリ使用量を増やしてでも実行時間を最適化したり、逆にメモリが少ないシステムで実行時間が長くなることを覚悟してメモリ使用量が少ないアルゴリズムを選んだりする。あらゆる場合に最適な方法や設計は存在しないので、技術者は最も重要と思われる観点での最適化のために妥協点を探る。さらに、ソフトウェアを完全に最適にする（それ以上どうやっても最適化できない状態にする）のに要する労力は、その最適化されたシステムを利用することで得られる利益よりも大きい。従って、最適化の工程は完全な最適解に到達する以前に終了させられるのが普通である。幸いなことに、効果の大きい改善は最適化工程の初期に現れることが多い。
最適化は様々なレベルで行われる。最も高いレベルの最適化は設計段階に行われる。設計が最適化されていれば、実装でも効率的なアルゴリズムを利用でき、品質のよいコードになるという利点がある。コンパイラ最適化を使えば、実行ファイルがさらに最適化される。最も低いレベルでは、コンパイラを使わずに人間がアセンブリ言語で最適なコードを書く。コンパイラ最適化の技術の進歩と最近のCPUの複雑さのため、コンパイラよりも最適なコードを人間が書くには大変な技能を要する。そのため、このような最適化を行うプロジェクトは滅多にない。最適化は例外的なケースを考慮しつつ、複雑な妥協点を探ることが多い。従って最適化されたプログラムはプログラマが理解できないほど難解になることも多い。可能であれば等価であることが保証されながらプログラムを変形させるなどの手法でバグの可能性をゼロにすべきだが、できない場合、できてないコードではバグを多く含む危険性がある。

基本

計算処理には効率の異なる複数の実行方法が存在することが多い。例えば、以下のC言語のコードは、1 から N までの整数の総和を計算するものである。
int i, sum = 0;for (i = 1; i <= N; i++)
  sum += i;printf ("sum: %d\n", sum);
演算でのオーバーフローが発生しなく、かつ、N >= 0 ならば、これを以下のような数学的な式で書き換えることもできる。
int sum = (N * (N + 1)) / 2;printf ("sum: %d\n", sum);
最適化（特に自動的に行われる最適化）は、機能的に等価でより効率的な方法を選択することに他ならない。しかし、効果の大きい性能改善は無駄な機能を省いて実際の問題に集中することで実現されることも多い。
最適化は必ずしも自明で直観的なものとは限らない。上の例で「最適化」されたバージョンは N が小さければオリジナルよりも性能が悪い可能性がある。これは、そのコンピュータでの加算とループの性能と乗除算の性能の関係に依存する。

トレードオフ

最適化は一般に性能の様々な観点（実行時間、メモリ使用量、ディスク使用量、帯域幅、電力消費など）の一部だけを改善する。そこには何らかのトレードオフがあり、ある観点を犠牲にして別の観点を最適化することになる。例えば、キャッシュを大きくすれば実行時の性能は改善されるが、キャッシュも含めたメモリ消費は増大する。その他の典型的なトレードオフとしては、コードの読みやすさとコンパクトさなどがある。
プログラマが最適化を行う際に、一部の処理を最適化するには他の処理の効率を悪くしなければならないという決断をせまられることがある。このようなトレードオフは技術的でない理由で必要となることが多い。例えば、競合他社が発表したベンチマーク結果に勝つため、通常のソフトウェアの効率が悪くなるとしてもベンチマークをより効率的に実行する最適化を施すといった場合である。

その他の分野

この記事ではなく、「最適化問題」の記事にある内容についての話題を混同する者も多い。
プログラミングでは、より効率的なソフトウェアを生成するため、アーキテクチャに合わせたコンパイラの設定をしたり、そのアーキテクチャにあわせたコード修正を施すことを最適化と呼ぶこともある。
典型的な問題は様々な解法があり、プログラミングでは「十分によい」解だけを考慮する。

ボトルネック

最適化ではボトルネックを見つける必要がある。ボトルネックとは、化学反応における律速段階などのアナロジーで説明されるが（反応速度#律速段階も参照）、全体を「流れ」とした見た時に最もその流れが妨げられていて、全体の速さがその部分の速さで決まっている、という部分のことである。
またボトルネックに関する経験則として、全体の1%〜25%のコードが75%〜99%のリソース（CPU時間、メモリ）を消費する（パレートの法則も参照）、といったような傾向がある（当然、ザルに書いたコードほどその傾向は激しく、予めよくわかっている対象について綿密に計画され、さらに改良が重ねられたコードであれば逆になる）。
ボトルネックとなっている処理が非常に単純でそれ以上最適化しようがない場合もある。プログラムとは別のレイヤ、例えば、コンピュータ・アーキテクチャに原因があることもある。
アーキテクチャに関わる設計はシステムの性能をほとんど決定づける。アルゴリズムの選択は設計の中でも最も効率に影響が大きい。複雑なアルゴリズムやデータ構造は多量の処理には適しているが、単純なアルゴリズムは少量のデータ処理により適している。複雑なアルゴリズムでは設定や初期化に時間がかかり、データが少量の場合に効果が薄れるためである。
場合によっては、メモリを追加することでプログラムが高速化されることがある。例えば、フィルタは入力を1行ずつ読み込んで、結果を即座に出力する。この場合、1行を読み込むだけのメモリがあれば十分だが、そのような方式での性能は一般にあまりよくない。ファイルを一括して読み込めば性能が劇的に改善されるが、メモリをより多く消費することになる。計算結果をキャッシングするのも効果的だが、同様にメモリ使用量が増大する。

インタプリタ

インタプリタな処理系（特にPHPのように繰り返し実行され、性能も要求される場合）では、プログラマはコードからコメントや空白を削除し、使われないメソッドや関数の定義を削除してから、コードを配備することがある。これはネットワーク上の転送時間やインタプリタがコードを読み込む時間を少しでも改善しようという一種の最適化である。
このとき、元のコード（コメント付きの整ったコード）を捨ててしまうと、保守性が犠牲となる。そのようなコードは可読性が低く、デバッグや修正や改造が困難となる。従って、元のコードを手元に残しておくことが推奨され、修正を加える必要がある場合は、その元のコードを使うのがよい。
また、コメントや空白を削除することが実行時間の短縮に寄与するかどうかは事前に確かめておく必要がある。場合によっては「労多くして、益少なし」となることもある。一般にソースコードをネットワーク上で転送する JavaScript などのコードの方が、ローカルに実行されるPHPなどよりも効果が大きい。

マクロ

マクロを使ったコード開発での最適化は言語によって異なる。C言語などの高級言語では、マクロは文字列の置換であり、マクロの効果は関数呼び出しのオーバーヘッドを削減する程度でしかない。
しかし、多くの関数型言語でのマクロはコンパイル時の評価と文字列レベルでないコンパイルコードの置換として実装されている。このため、コンパイル時に複雑な計算が可能で、プログラムの処理の一部をコンパイル時に済ませてしまうこともできる。このようなマクロはLISPを起源とするものである。
しかし、他の最適化と同様、このようなツールをどこに利用するのが効果的かをプロジェクトが完了する前に予測することは困難である。

自動最適化と手動最適化

最適化はコンパイラで自動的に行うこともできるし、プログラマが自ら行うこともできる。局所的な最適化の効果は限定的であり、大域的な最適化の方が効果が大きい。一般に、より優れたアルゴリズムやデータ構造を見出すことが最も強力な最適化となる。
システム全体の最適化は自動化するには複雑すぎるため、人間の手で行うことが多い。その場合、プログラマやシステム管理者が自らコードを修正し、性能を改善する。効率が改善されるとしても、自動最適化に比べれば遥かにコストを要する作業である。
第一にリソースを最も多く消費している箇所（ボトルネック）を見つけるため、プロファイラを利用することが何よりも重要である。プログラマはボトルネックがどこか正確に把握していると思っているものだが、そのような予測は間違っていることが多々ある。重要でないコードの最適化は全体性能に与える効果が少ない。
ボトルネックを特定したら、まずそのプログラムで使われているアルゴリズムを再考するところから最適化が始まる。通常、汎用的アルゴリズムよりも特定の問題に特化したアルゴリズムの方が調整しやすい。例えば、大きなリストをソートする処理では、効率のよい汎用アルゴリズムの1つであるクイックソートを使うのが一般的である。しかし、ソート対象の性質が判っていれば（例えば事前に何らかの順番で並んでいるなど）、その他のアルゴリズムや特製のソートルーチンの方が有効な場合もある。
最善のアルゴリズムが選択されていると判明した場合、コードの最適化が開始される。ループ展開をしたり、なるべく小さいデータ型を使うようにしたり（浮動小数点でなくてもよい計算を整数の計算に直すなど）する。
性能ボトルネックがアルゴリズムの問題やデータ構造の問題ではなく、言語の制限による場合もある。このため、プログラムの重要な部分を異なるプログラミング言語で書き換え、よりマシンに近いアクセスを行う場合がある。例えば、Pythonなどの高級言語でC言語のモジュールを使用して高速化したりする。C言語で書かれたプログラムなら、一部をアセンブリ言語で置換する。D言語などはインラインアセンブラ機能が利用できる。
パレートの法則によれば、書き換えはプログラムのごく一部だけで済む。従って、最適化にかかるコストと全体の性能向上が十分見合う結果となる。
手動の最適化は可読性を損なうことが多い。最適化にあたっては、その文書化と将来の開発への影響の評価が重要である。
自動最適化を行うプログラムをオプティマイザ (optimizer) と呼ぶ。オプティマイザはコンパイラに内蔵されていることが多く、コンパイル中に最適化が行われる。オプティマイザは生成されたコードを特定のプロセッサ向けに最適化することが多い。従って自動最適化はコンパイラ最適化とほぼ同義である。
一部の高級言語（EiffelやEsterel）は中間言語を使ってプログラムを最適化する。
グリッド・コンピューティングや分散コンピューティングでは、稼働率の高いコンピュータから別の稼働率の低いコンピュータにタスクを移すことでシステム全体の最適化を行う。

最適化に要する時間

オプティマイザによっても最適化が行われる。コンパイラで最適化を行うと（最適化しない場合より）時間がかかる。これが問題となるのは一般にプログラムが非常に大きい場合だけである。ジャストインタイムコンパイル方式では、オプティマイザの性能が実行時間の向上の鍵となる。オプティマイザが時間をかければかけるほど生成されるコードはよくなるが、それはつまり貴重なCPU時間をオプティマイザが使用するということを意味する。従って、特にジャストインタイムコンパイル方式では、オプティマイザにかかる時間とそれによって生成コードの性能が改善されて節約される時間のトレードオフが重要となる。

最適化のコスト

ソフトウェア開発プロジェクトでは、コード最適化は新たな機能を追加するわけでもなく、失敗すれば既存の機能を壊してしまうこともある。最適化されたコードの可読性は低いので、最適化によってプログラムの保守性が損なわれることもある。プログラマのリソースを消費して最適化を行うのではなく他の手段に頼るほうがコストパフォーマンスが良い場合がある。例えばWebアプリケーションの場合に最適化するのではなくサーバースペックの強化で対応したり、分散可能な場合にサーバー台数の増加で対応する。メモリ断片化やメモリリークの原因特定と修正を試みるよりも定期的に再起動するなど運用方法の変更で対応する。画像や映像処理は最適化余地の少ないCPU上で動作させるコードを最適化するのではなくGPUなど特化したハードウェアを用いるなど。
つまり、そもそも本当に最適化が必要かどうかも含めて最適化にかかるコストとそこから得られる利益を見極めることが重要である。

分類

コード最適化は、プラットフォーム依存の最適化とプラットフォームに依存しない最適化に分けられる。プラットフォームに依存しない最適化技法は多くのコンピュータで有効な技法である（ループ展開、関数呼び出し回数削減、メモリの効率的使用、条件分岐の整理など）。プラットフォーム依存の技法は、命令レベルの並列性に関するもの、データレベルの並列性に関するもの、キャッシュ最適化技法など、プラットフォームによってパラメータが異なる技法である。