ソフトウェア高速化するなら絶対マスターしておきたい理論３選

プログラミングを30年以上やっているムンペイです。
30年前のPCに搭載されていたCPUは、コアはもちろん１つでスーパースカラーもないインオーダー実行、クロックも12MHz程度と、今と比べると恐らく10,000倍くらい遅かったかもしれませんが、それでも凄い3D CGやゲームを実現する人たちのプログラミング技術に魅せられ、高速化にハマっていきました。

高速なソフトウェアを目指すなら絶対に知っておきたい理論を３つ、紹介します。

1. ビッグＯ表記／オーダー

最初は、ビッグO（オー）表記（Big O notation） です（※）。
アルゴリズムのパフォーマンスや効率を評価するための数学的な表現で、入力データサイズ（個数）を n としたときに、あるアルゴリズムの計算時間（時間複雑度）やメモリ必要量（空間複雑度）がどの程度になるかを理論的に示すものです。ソフトウェア高速化に取り組む上で非常に重要です。
よく「オーダー」とも言います。
※英語版Wikipediaでは Big O notation ですが、日本語版Wikipediaのページだと「ランダウの記号」という見出しになっています。

ビッグＯ表記による複雑度は、複雑度を n の関数として表した時の最も高次の項について、比例係数を省いて表現します。概ね次のような種類があります。

• O(1) - 定数オーダー：入力サイズに関係なく、常に一定の時間がかかります。

• O(log n) - 対数オーダー：入力サイズが増加しても、実行時間の増加が比較的小さくすみます。二分探索が一例。

• O(n) - 線形オーダー：入力サイズに比例して（線形に）実行時間が増加す。例えば、リストを一つずつ探索する場合。

• O(n log n) - n log n （エヌログエヌ）オーダー：多くの効率的なソートアルゴリズムがこのカテゴリーに属します。

• O(n^2) - 二乗オーダー：入力サイズの二乗に比例して実行時間が増加。例えば、二重ループによる総当たり探索。さらに、三乗オーダー、四乗オーダー、・・・もあります。

• O(2^n) - 指数オーダー：入力サイズに対して実行時間が指数的に増加。組み合わせ問題などで見られます。

• O(n!) - 階乗オーダー：非常に非効率で、大きな入力サイズでは実用的ではありません。

上から順に効率的となります。ビッグO表記を使用して異なるアルゴリズムやアプローチを比較し、最適な選択を行うことは、常に意識意識しておくべき重要事項です。このクラスを一つ効率化できると、n が大きいと数倍程度に留まらない効果があり n が大きくなるほどその差は広がります。
O(n log n)までが「効率的」なアルゴリズムで満足、O(n^2)なら止む無い場合は使う、それ以上（三乗以上や指数、階乗）は原則として実用に耐えないためオーダーを下げる工夫を考えるという判断になります。

2. アムダールの法則

２番目はアムダールの法則（Amdahl's Law）です。
こちらも高速化界隈では有名です。並列化による理論上の最大性能向上を予測するのに使用されます。

法則としては「プログラムの一部分だけを高速化しても、全体のパフォーマンスに与える影響はその部分（並列化できない部分）が占める割合によって限定される。」というものになります。

たとえば、プログラムの90%が並列化可能だとしましょう。これを3000コアのGPUを使って超高速化したとします。しかし、残りの10%が並列化できないので、3000コアもあるのに全体の性能向上は最大でも10倍にとどまるということです。

また、マルチコア／マルチプロセッサの数を増やせばいくらでも追加すれば高速化されるということはないということも言っています。並列化できない部分の実行時間の割合が目立つようになってくるあたりから、追加のプロセッサによる効果は著しく減少します。

高速化したい処理の並列化可能な部分がどれくらいかを調べて、アムダールの法則により理論的な限界を評価し、それで目標を充足するならよし、足りないなら並列化以外の戦略を検討する、といった感じで使います。
また、高速化のステップとして、並列化可能になるような工夫を検討することもあります。

3. グスタフソンの法則

３つ目は、グスタフソンの法則（Gustafson's Law）です。こちらは前述の２つに比べるとちょっとマイナーです。正直に言うと、私はこの名前で意識することはあまりなく、アムダールの法則の裏返しのような捉え方をしています。

法則としては「利用可能なプロセッサの数に応じて問題のサイズを拡大すると、並列化の効果がより顕著になる」といったものです。
アムダールの法則では、（例えばプロセッサを追加して）並列度を高めても効果に限界があるということを示していましたが、グスタフソンの法則ではそれならデータサイズも一緒に大きくすればいいじゃないか、というものです。

例えば、データ１個に対して１の時間がかかり並列化できる処理Ａと、その他に50の時間がかかる並列化できない処理Ｂがあり、50コアまでプロセッサを追加可能とします。
Ａのデータが50個の場合、2コアで処理すると1.33倍、3コアで処理すると1.5倍、と高速化はされますがどんどん増やしても理論上の限界が2倍ですので、（きっと高額な）50コアの利点は十分発揮されません。しかし、Ａのデータが5000個に増えた場合は、50コアで処理することで33倍以上に高速化できます。もっとプロセッサを増やせば、理論的には約99倍まで高速化できます。

実際の応用ではデータサイズを自由に増やせるということもないでしょうから、データサイズから並列度を考えて適切に計算リソースを配分するといった形で利用することになるでしょう。
感覚的には、1,000を超えてきたくらいから並列化のコスパが高まってくる感じです。（もちろん処理の内容にも依りますが）

理論上有利な方が負けることもある？

ビッグO表記による複雑度は絶対マスターです。非常に有効な考え方です。また、ビッグO表記が有効なのは、教科書に載っているようなナニナニ法アルゴリズムだけではありません。自分で書いているプログラムが二重ループになっていれば O(n^2) です。

さて、データがそれほど多くない場合、O(n^2) のアルゴリズムが O(n log n) のアルゴリズムに勝ってしまう場合もあります。これは、オーダーが低いアルゴリズムは処理が複雑な場合も多く、データ１つあたりの処理時間で見ると遅くなるためです。世の中の高度にチューニングされたソフトウェアの中には、データが少ないと見るや、オーダー的には不利だが１つ１つは高速に実行できるアルゴリズムに切り替えるものもあります。プロセッサの性能を限界まで引き出す高速化の世界は広く深いのです。そのあたりの話はまた別の機会に。

これにて御免！

（今回の見出し画像はChatGPTに生成してもらいました）