最適化 (情報工学)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

情報工学における最適化: Optimization)は、システムを何らかの観点でより効率的に動作するよう変更することをいう。例えば、プログラムの最適化は、高速化のためだったり、メモリの使用量を削減するためだったり、電力消費を抑えるためだったりする。最適化の対象となるシステムは、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 が小さければオリジナルよりも性能が悪い可能性がある。これは、そのコンピュータでの加算とループの性能と乗除算の性能の関係に依存する。

トレードオフ[編集]

最適化は一般に性能の様々な観点(実行時間、メモリ使用量、ディスク使用量、帯域幅、電力消費など)の一部だけを改善する。そこには何らかのトレードオフがあり、ある観点を犠牲にして別の観点を最適化することになる。例えば、キャッシュを大きくすれば実行時の性能は改善されるが、キャッシュも含めたメモリ消費は増大する。その他の典型的なトレードオフとしては、コードの読みやすさとコンパクトさなどがある。

プログラマが最適化を行う際に、一部の処理を最適化するには他の処理の効率を悪くしなければならないという決断をせまられることがある。このようなトレードオフは技術的でない理由で必要となることが多い。例えば、競合他社が発表したベンチマーク結果に勝つため、通常のソフトウェアの効率が悪くなるとしてもベンチマークをより効率的に実行する最適化を施すといった場合である。

その他の分野[編集]

オペレーションズ・リサーチでは、関数の値を最小または最大にする入力値を決定する問題を最適化と呼ぶ。複数の入力の間に制約が課せられるものもあり、そのような問題を制約つき最適化と呼ぶ。

プログラミングでは、より効率的なソフトウェアを生成するため、アーキテクチャに合わせたコンパイラの設定をしたり、そのアーキテクチャにあわせたコード修正を施すことを最適化と呼ぶこともある。

典型的な問題は様々な解法があり、プログラミングでは「十分によい」解だけを考慮する。

ボトルネック[編集]

最適化ではボトルネックを見つける必要がある。ボトルネックとは、リソースを最も多く消費している重要なコード部分である。経験則として、20%のコードが80%のリソース(CPU時間、メモリ)を消費すると言われる(パレートの法則)。

パレートの法則は様々な現象を指しており、結果の80%が原因の20%から生じることを示している。これは経験則として様々な場面で応用されるが、その多くは誤用である。例えば、ある解決策が80%のケースで適用可能であることを指して、その解決策がパレートの法則に適合しているというのは誤用である。情報工学ではパレートの法則は、リソースの80%が一般に20%の処理で消費されるという観測結果から、最適化に適用される。ソフトウェア工学では、90%の実行時間が10%のコードで消費されると言った方が観測結果に近い。

ボトルネックとなっている処理が非常に単純でそれ以上最適化しようがない場合もある。その場合、その処理がボトルネックとなった要因を探る必要がある。例えば、アーキテクチャ段階での設計に問題がある場合もある。

アーキテクチャに関わる設計はシステムの性能をほとんど決定づける。アルゴリズムの選択は設計の中でも最も効率に影響が大きい。複雑なアルゴリズムやデータ構造は多量の処理には適しているが、単純なアルゴリズムは少量のデータ処理により適している。複雑なアルゴリズムでは設定や初期化に時間がかかり、データが少量の場合に効果が薄れるためである。

場合によっては、メモリを追加することでプログラムが高速化されることがある。例えば、フィルタは入力を1行ずつ読み込んで、結果を即座に出力する。この場合、1行を読み込むだけのメモリがあれば十分だが、そのような方式での性能は一般にあまりよくない。ファイルを一括して読み込めば性能が劇的に改善されるが、メモリをより多く消費することになる。計算結果をキャッシングするのも効果的だが、同様にメモリ使用量が増大する。

最適化する時期[編集]

最適化ではコードの可読性を損ない、性能向上にしか寄与しないコードを追加することがある。これはプログラムやシステムを複雑にし、保守やデバッグがしにくくなる。そのため、最適化や性能チューニングはソフトウェア開発工程の最後のほうで行われることが多い。

ドナルド・クヌースは、時宜を得ない(しばしば、早すぎる段階での)最適化を戒める言をいくつも記している。一例を挙げれば、

  • 「ほんとうの問題点は、プログラマたちが誤った場所と誤った時点での効率について苦労して、多くの時間を浪費してしまったということにあります。プログラミングでは、時を得ない最適化は諸悪の根源なのであります。(すべてではないにしても、少なくとも悪の大部分と言えるでしょう。)」(1974年、チューリング賞受賞講演より。『ACMチューリング賞講演集』p. 56、『文芸的プログラミング』p. 30)

クヌースはアントニー・ホーアに由来するとしているが、ホーアは否定している(アントニー・ホーア#語録を参照)。ダイクストラに由来するのではないかとする説があり、ホーアもそう述べている。なお、クヌースが1974年に「未熟な最適化は諸悪の根源である」と書いているもうひとつの文献は、ダイクストラのGo To Statement Considered Harmfulに対して書かれた、Structured Programming with go to Statements[1]である。

これについて Charles Cook は次のように述べている。

  • 「賛成だ。コードのボトルネックがどこなのかが判明する前に細かい最適化に時間を費やすのは無駄だ。しかし逆にシステムレベルのソフトウェアを設計するときは、性能問題を常に念頭に置くべきだ。よいソフトウェア開発者はこれを自動的に行っており、どこの性能が問題となるかを感覚的に感じ取ることができる。経験の浅い開発者は、後の工程でのちょっとした微調整で問題が全て解決するという間違った信念を持っていることがある」[2]

「時期尚早な最適化」という言葉は、プログラマが個々のコードの設計時に性能への考慮をすることを指している。そのような小手先の最適化を最初から行っていると、コードが複雑化してその機能の本質を見誤り、コードが汚くなったり、バグを作りこんだりする。

よい手法とは、設計をまず行い、その設計からコードを書き、プロファイル/ベンチマークを実施して最適化すべき箇所を特定することである。単純で簡潔な設計であれば、この手法での最適化が容易であり、プロファイリングによって予想外の性能問題(時期尚早な最適化では思いもよらなかった問題)が明らかとなることもある。

実際には、ソフトウェアの設計の初期段階から性能目標を念頭に置く必要があるが、プログラマは設計目標と最適化のバランスを保つ(最適化での伸びしろを考慮してコードを書くときの時期尚早な最適化を控える)。

インタプリタ[編集]

インタプリタな処理系(特にPHPのように繰り返し実行され、性能も要求される場合)では、プログラマはコードからコメントや空白を削除し、使われないメソッドや関数の定義を削除してから、コードを配備することがある。これはネットワーク上の転送時間やインタプリタがコードを読み込む時間を少しでも改善しようという一種の最適化である。

このとき、元のコード(コメント付きの整ったコード)を捨ててしまうと、保守性が犠牲となる。そのようなコードは可読性が低く、デバッグや修正や改造が困難となる。従って、元のコードを手元に残しておくことが推奨され、修正を加える必要がある場合は、その元のコードを使うのがよい。

また、コメントや空白を削除することが実行時間の短縮に寄与するかどうかは事前に確かめておく必要がある。場合によっては「労多くして、益少なし」となることもある。一般にソースコードをネットワーク上で転送する JavaScript などのコードの方が、ローカルに実行される PHP などよりも効果が大きい。

マクロ[編集]

マクロを使ったコード開発での最適化は言語によって異なる。C言語などの高級言語では、マクロは文字列の置換であり、マクロの効果は関数呼び出しのオーバーヘッドを削減する程度でしかない。

しかし、多くの関数型言語でのマクロはコンパイル時の評価と文字列レベルでないコンパイルコードの置換として実装されている。このため、コンパイル時に複雑な計算が可能で、プログラムの処理の一部をコンパイル時に済ませてしまうこともできる。このようなマクロはLISPを起源とするものである。

しかし、他の最適化と同様、このようなツールをどこに利用するのが効果的かをプロジェクトが完了する前に予測することは困難である。

自動最適化と手動最適化[編集]

最適化はコンパイラで自動的に行うこともできるし、プログラマが自ら行うこともできる。局所的な最適化の効果は限定的であり、大域的な最適化の方が効果が大きい。一般に、より優れたアルゴリズムを見出すことが最も強力な最適化となる。

システム全体の最適化は自動化するには複雑すぎるため、人間の手で行うことが多い。その場合、プログラマやシステム管理者が自らコードを修正し、性能を改善する。効率が改善されるとしても、自動最適化に比べれば遥かにコストを要する作業である。

第一にリソースを最も多く消費している箇所(ボトルネック)を見つけるため、プロファイラを利用することが何よりも重要である。プログラマはボトルネックがどこか正確に把握していると思っているものだが、そのような予測は間違っていることが多々ある。重要でないコードの最適化は全体性能に与える効果が少ない。

ボトルネックを特定したら、まずそのプログラムで使われているアルゴリズムを再考するところから最適化が始まる。通常、汎用的アルゴリズムよりも特定の問題に特化したアルゴリズムの方が調整しやすい。例えば、大きなリストをソートする処理では、効率のよい汎用アルゴリズムの1つであるクイックソートを使うのが一般的である。しかし、ソート対象の性質が判っていれば(例えば事前に何らかの順番で並んでいるなど)、その他のアルゴリズムや特製のソートルーチンの方が有効な場合もある。

最善のアルゴリズムが選択されていると判明した場合、コードの最適化が開始される。ループ展開をしたり、なるべく小さいデータ型を使うようにしたり(浮動小数点でなくてもよい計算を整数の計算に直すなど)する。

性能ボトルネックがアルゴリズムの問題やデータ構造の問題ではなく、言語の制限による場合もある。このため、プログラムの重要な部分を異なるプログラミング言語で書き換え、よりマシンに近いアクセスを行う場合がある。例えば、Pythonなどの高級言語C言語のモジュールを使用して高速化したりする。C言語で書かれたプログラムなら、一部をアセンブリ言語で置換する。D言語などはインラインアセンブラ機能が利用できる。

パレートの法則によれば、書き換えはプログラムのごく一部だけで済む。従って、最適化にかかるコストと全体の性能向上が十分見合う結果となる。

手動の最適化は可読性を損なうことが多い。最適化にあたっては、その文書化と将来の開発への影響の評価が重要である。

自動最適化を行うプログラムをオプティマイザ (optimizer) と呼ぶ。オプティマイザはコンパイラに内蔵されていることが多く、コンパイル中に最適化が行われる。オプティマイザは生成されたコードを特定のプロセッサ向けに最適化することが多い。従って自動最適化はコンパイラ最適化とほぼ同義である。

一部の高級言語(EiffelEsterel)は中間言語を使ってプログラムを最適化する。

グリッド・コンピューティング分散コンピューティングでは、稼働率の高いコンピュータから別の稼働率の低いコンピュータにタスクを移すことでシステム全体の最適化を行う。

最適化に要する時間[編集]

状況によっては、最適化にかかる時間が問題となることもある。

ソフトウェア開発プロジェクトでは、コード最適化は新たな機能を追加するわけでもなく、失敗すれば既存の機能を壊してしまうこともある。最適化されたコードの可読性は低いので、最適化によってプログラムの保守性が損なわれることもある。つまり、最適化にかかるコストとそこから得られる利益を見極めることが重要である。

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

分類[編集]

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

引用[編集]

  • 「個々の操作を特定の順に実行させることは非常に興味深く奇妙な問題である。その上で全てを入力する余裕はない。どのような計算でもプロセスの遷移のための多種多様な配置が可能であり、様々な考慮の上でそれを選択しなければならない。基本的な目的は計算を完了するまでの時間を最小にする配置を選択することである」 - Ada Byron's notes on the analytical engine 1842.
  • 「情報処理における罪の多くは(必ずしも達成されることのない)効率の名においてなされる。そこには盲目の愚かさも含まれる」 - W.A. Wulf
  • 「細かい効率のことは忘れて、時間の97%について考えよう。時期尚早な最適化は諸悪の根源だ。それでも残り3%についても機会を逃すべきではない」[3] - ドナルド・クヌース
  • 「ボトルネックは思いもよらない場所に存在するので、ボトルネックの箇所を特定するまで性能最適化(ハック)してはいけない」 - ロブ・パイク
  • 「プログラム最適化の第一法則: 最適化するな。プログラム最適化の第二法則(上級者限定): まだするな。」 - Michael A. Jackson

関連項目[編集]

脚注[編集]

  1. ^ 該当部分は邦訳版『文芸的プログラミング』p. 52
  2. ^ The Fallacy of Premature Optimization by Randall Hyde
  3. ^ ドナルド・クヌース: Structured Programming with Goto Statements. Computing Surveys 6:4 (1974), 261–301.

参考文献[編集]

外部リンク[編集]