「最適化 (情報工学)」の版間の差分

削除された内容追加された内容

インライン

2020年7月5日 (日) 22:52時点における版

コンピュータ関連において最適化（英: 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行を読み込むだけのメモリがあれば十分だが、そのような方式での性能は一般にあまりよくない。ファイルを一括して読み込めば性能が劇的に改善されるが、メモリをより多く消費することになる。計算結果をキャッシングするのも効果的だが、同様にメモリ使用量が増大する。

最適化する時期

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

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

「ほんとうの問題点は、プログラマたちが誤った場所と誤った時点での効率について苦労して、多くの時間を浪費してしまったということにあります。プログラミングでは、時を得ない最適化は諸悪の根源なのであります。（すべてではないにしても、少なくとも悪の大部分と言えるでしょう。）」（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などよりも効果が大きい。

自動最適化と手動最適化

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

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

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

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

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

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

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

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

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

一部の高級言語（EiffelやEsterel）は中間言語を使ってプログラムを最適化する。

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

最適化に要する時間

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

最適化のコスト

ソフトウェア開発プロジェクトでは、コード最適化は新たな機能を追加するわけでもなく、失敗すれば既存の機能を壊してしまうこともある。最適化されたコードの可読性は低いので、最適化によってプログラムの保守性が損なわれることもある。「リファクタリング」と同様に、機能が保存されていることのテストが少なくとも必要とされる。

トリビアルな覗き穴最適化などはある程度以上のコンパイラならば実装しており、プログラマが手作業でそれと同等程度の最適化を施すのはバグの元でしかなく、意味が無いだけでなく有害である。例えば x = a + b * 4 のようなコードを x = a + b << 2 のように「最適化」してしまうのが典型的な失敗例であり、こういった最適化をプログラマの良い習慣であると評価しているような組織があったらそれはある種のシグナルである。

プログラマのリソースを消費して最適化を行うのではなく他の手段に頼るほうがコストパフォーマンスが良い場合がある。例えばWebアプリケーションの場合に最適化するのではなくサーバースペックの強化で対応したり、分散可能な場合にサーバー台数の増加で対応する。メモリ断片化やメモリリークの原因特定と修正を試みるよりも定期的に再起動するなど運用方法の変更で対応する。画像や映像処理は最適化余地の少ないCPU上で動作させるコードを最適化するのではなくGPUなど特化したハードウェアを用いるなど。

分類

コード最適化は、プラットフォーム依存の最適化とプラットフォームに依存しない最適化に分けられる。プラットフォームに依存しない最適化技法は多くのコンピュータで有効な技法である。プラットフォーム依存の技法は、命令レベルの並列性に関するもの、データレベルの並列性に関するもの、キャッシュ最適化技法など、プラットフォームによってパラメータが異なる技法である。

しかし、現代のコンピュータのマイクロアーキテクチャでは、本来プラットフォームに非依存のはずの改善ですら、逆効果の場合がある。たとえば一般論的には、多数の条件分岐がある場合、確率の高いほうから振り分けたほうが、少ない数の比較で済むから効率が良いはずである。ところが、分岐予測により「予測が当たった場合のペナルティは0で、外れた場合のペナルティは大きい」というマシンが現代ではありえる。ネットワーク時代のために多用されるデータ圧縮・展開の基本的な技法であるハフマン符号は、パターンの出現がうまく分布していた場合、確率の高い順に 50%, 25%, 12.5%, 6.25%, ... というような出現率の分類をすることになるから、そのようなマシンで確率の高いほうから振り分けてしまうと、むしろ分岐予測が外れやすい側から試しているという結果になり、改善のはずが逆効果になるかもしれない。

他にも、変に数式や計算法をいじるよりも、倍精度浮動小数で素直に計算してしまったほうが、現代のマイクロプロセッサはそこに注力して高性能化されているので速い、ということもある。結局、計算のオーダーが変わるようなアルゴリズム的改善を除けば、「最適化のつもり」が本当に改善になっているのかは、どんな場合であれ実際に測定しなければわからない、と、予防的に考えておくのが正解である。

格言

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

脚注

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

参考文献

Jon Bentley: Writing Efficient Programs, ISBN 0-13-970251-2.
ドナルド・クヌース: The Art of Computer Programming

外部リンク

Programming Optimization
C,C++ optimization
C optimization tutorial
Software Optimization at Link-time And Run-time
"A Plea for Lean Software" by Niklaus Wirth
Description from the Portland Pattern Repository
Performance tuning of Computer Networks
An article describing high-level optimization
Optimization for video games (gpu and cpu)

[1] 該当部分は邦訳版『文芸的プログラミング』p. 52

[2] The Fallacy of Premature Optimization by Randall Hyde

[3] ドナルド・クヌース: Structured Programming with Goto Statements Archived 2009年8月24日, at the Wayback Machine.. Computing Surveys 6:4 (1974), 261–301.

[1]

[2]

[3]