高速なプログラムを書くためのコツ３選

プログラミング歴30年以上のムンペイです。
中学生のときに出会ったメガデモ（※１）に魅せられて高速なプログラムの追求にハマりました。就職後も、DSPの画像処理、ヘテロジニアスマルチコアプロセッサでの性能追求など、仕事でも高速プログラムの開発に携わってきました。
その経験で得た、基本的な高速化のコツを優先順に３つ挙げてみます。

※１: GPUどころかまだGUIのOSも珍しかった時代に、16MHz程度のCPUによるリアルタイム演算で数分間の3D CG動画を再生するプログラムのこと。一説にはプログラムが1MB未満だからメガデモというとか。特にSecond Realityのインパクトは凄かった。YouTubeで動画が見られます。

1. 短く書く

最も基本的なことは、短いプログラムを目指すということです。同じことを実現するもっと簡潔な書き方がないか常に考えます。その心は、処理すべきCPU命令数が少なければ、早く処理が終わるハズという基本的な原則です。

アルゴリズムによる計算オーダー下げはわかりやすい例です。たとえば、C++で1から100までの和を計算する場合、

#include <iostream>

int main() {
    int total = 0;
    for (int i = 1; i <= 100; ++i) {
        total += i;
    }
    std::cout << total << std::endl;
    return 0;
}

よりも、

#include <iostream>

int main() {
    int total = 0;
    int n = 100;
    total = n * (n + 1) / 2;
    std::cout << total << std::endl;
    return 0;
}

が、圧倒的に高速です。理論的な計算量の違いは、命令数の違いにもなっています。

また、理論的な計算量は変わらなくても、よりCPUサイクルを節約できないかということも追求します。ループ内で無駄な処理はないか、この計算はすでにやってないか、などです。

よりよいCPU命令が選べるようにできないか、というのもあります。昔のCPUではたくさんの命令が必要だった処理を、新しいCPUでは少ないサイクルで実行できる命令を持っていることもあります。もっとも通常はCPU命令の選択はコンパイラやインタープリタに任せれば実用十分ですが、ソースコード上で簡潔ならばコンパイラが簡潔な処理を選びやすい傾向はあると思います。

ちなみに、何か変数名を短くしたり改行や空白を詰めたりするのはどうでしょう。JavaScriptのminify処理が代表的ですね。モダンなインタープリタは実行前にコンパイルするので、処理速度にソースコードの文字数は関係ありません。しかし、ソースコードそのものを流通させるコストを節約したい場合や、不特定多数のユーザーが少数回だけ使うためコンパイル結果の再利用が期待できない場合は、minify戦術は価値があります。
一方、コンパイラ言語はもちろん、インタープリタでもバックエンドサーバーのように同じコンピュータで何度も実行する用途の場合はコンパイル結果のキャッシュが効きます。
いずれにしても、私はソースコードの文字数を自分で短くしようとすることはありません。

2. データ構造を適切に選ぶ

先人は、プログラムとはアルゴリズム＋データ構造であると言いました（※２）。２つ目のコツはデータ構造を適切に選ぶことです。

実は、特にメモリ上のデータ構造を適切に選ぶというのは、プログラムで処理しなければならないことを減らす（つまり、１番目のコツを達成する）ために行うものです（※３）。データ構造が適切にできたときは、コードをゼロにできることすらありえます。なかなかできることでは無いのですが、私は常にコードゼロを意識しています。

わかりやすい例として、データを昇順に取り出すという操作を考えてみます。このとき、取り出すという操作と、昇順に並べる、という操作を同時にあるいは順に、とにかく両方行う必要があります。ここでもし、データ構造の工夫により書き込まれたデータがそもそも昇順に保存されていたらどうでしょう。取り出し時は昇順にならべる操作が不要、つまりゼロになりました。

もちろん書き込み時に整列のコストを負担しますので、書き込み回数の方が圧倒的に多いといったユースケースの場合は異なる選択をします。

※２: "Algorithms + Data Structures = Programs", 
Niklaus Wirth, https://en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs

※３: 一方、ディスクやネットワーク向けのデータ構造は、サイズを減らすことやポータブルな読み書きを目的とします。

3. 記憶階層を意識する

ハードウェアの性能を引き出そう、と言い換えてもよいでしょう。

処理はデータの読み書きと演算の繰り返しです。このうち演算はほぼCPUのみで行われますが（いえ、GPUもありますね！）、データ読み書き先はレジスタ、キャッシュメモリ、メインメモリ、ディスク、ネットワークと多数あり、この順にCPUの計算器から遠くなります。遠くなればそこからデータを取ってくるのが遅くなるので、できるだけ遠いメモリとやり取りする機会を減らすことが重要です。

細かい時間はさておき、私は読み書き時間の違いをすごくザックリとイメージしてプログラミングします。具体的にはデータを取り出すのにかかる時間（レイテンシ）をレジスタが1とすると、キャッシュメモリが10、メインメモリが100、ストレージ（SSD）がその100倍、ネットワークがその
100倍、位のオーダーです（※４）。
たとえば、ネットワーク経由で取得したデータを再利用する可能性がある場合、ストレージに保存しておけば次回のデータ取得は99%ほど時短できるな、と言った判断を行います。

※４: こちらの記事に実際の数値がとてもわかりやすくまとめられています。ストレージとネットワークはもっと遅いと認識を改めました https://qiita.com/tarosaiba/items/4a7389d4626c5fb1eba1

その他

実際には、並列化、SIMD，非同期処理など、もっといろいろテクニックを駆使するのですが、多くはこれらの３つのコツを達成するためであると言っても良いと思います。

なお、この手の話をすると可読性を落としてまでやる必要はないという議論が起こることがありますが、トレードオフなので結局は必要性とバランスです。極限の速度が必要な場合は可読性は捨てますが、性能を10%くらい譲れば十分に可読性も良いコードが書けるというのが私の感覚です。

これらの話はまたの機会に。

これにて御免！

（見出しにはUnsplashのchris robertが撮影した写真を使わせていただきました）