プログラムを作成し終えてから、しばらく使っていると、行き着くのが速度の改善です。

大量の計算をするプログラムを書いたときに実践した高速化の方法と、ついでに思いついたことをメモしておきます。

この記事について

例として出すコードはGo言語ですが、特に言語を選ばない内容だと思いますので、適宜読み替えてください。

注意事項

高速化は、コードの可読性を犠牲にする場合があるので、効果とメンテナンス性を天秤にかけて、処置するかどうかを決断しましょう。

高速化するときに考えること

まず測る

有効度 ★★★★★

まず測らなければ現実は見えてきませんし、定量的な評価をすることが出来ません。
UIに関しては必ずしも速度の数値が全てではなく、体感というものが大事ですが、それにしてもユーザーが操作出来るようになった時間(TTI: Time To Interactive)などの指標がありますので、数値にすることが大事です。

Go言語であれば、標準でベンチマークのためのツールがついていますので使わない手はありません。

やり方は簡単で、まずテスト用のコードの中にベンチマーク用のコードを書きます。

func BenchmarkXXX(b *testing.B) {
  // 測りたい処理
}

そしてコマンドでベンチマークを起動するだけです。
-benchtimeで対象の関数の処理時間に合わせたテスト時間を設定できます。
実際に関数を何回実行するかは、goコマンドが自動的に決めてくれます。

go test ./path/to/test -bench XXX -benchmem -benchtime 10s 

// 結果
// ５回実行され、１回の実行あたり平均で、2.6秒、累計1.7GBのメモリ使用、4355万回のメモリ確保操作
// 5    2614808707 ns/op    1710808150 B/op 43550518 allocs/op

// 色々やったあとの結果
// 1000回実行され、1回の実行あたり平均で18ミリ秒、累計21MBのメモリ使用、20万回のメモリ確保操作
// 1000 18128649 ns/op 21660504 B/op 209012 allocs/op

また、単純に実行時間やメモリを出すだけではなく、CPUプロファイル、メモリプロファイルの出力と、ソースコードとの対比を確認することもできます。

CPUプロファイルを確認する場合

go test ./path/to/test -bench XXX -benchmem -cpuprofile cpu.prof
go tool pprof cpu.prof

メモリプロファイルを確認する場合

go test ./path/to/test -bench XXX -benchmem -memprofile mem.prof
go tool pprof --alloc_space mem.prof

pprof実行後の操作については、Go Blogが詳しいので、そちらを参照してください。

高速なアルゴリズムを使用する

有効度 ★★★★★
可読性 ★★★★☆

バブルソートとクイックソートの違いを思い浮かべてもらえればわかりますが、
- バブルソートは単純でやることが理解しやすいが、遅い
- クイックソートはやることが解り辛いが、早い
という特性があることが知られています。

しかしながらアルゴリズムのレベルから改善するのは、非常に効果が高いです。

理屈をしっかりとコメントなどで残せば、可読性も犠牲にならず、逆に泥臭い方法よりも可読性が向上することすらあります。

独自の実装を行っていると、単純に世の中のアルゴリズムを適用することが出来ない場合もあるかと思います。
それでもアルゴリズムについて調べていると、ふと自分のプログラムへの応用方法が思いつくときもあるので、他人の実装や文献などを読むといいかもしれません。

高速な言語を使用する

有効度 ★★★★★
可読性 ☆☆☆☆☆

動的言語よりは静的言語。コンパイルが必要なネイティブ言語を使用することで単純に数倍以上の効果を得ることができる場合があります。
これはチームや会社で開発を行っている場合には取りづらい選択肢かもしれません。
リプレースによる効果の見込みと予算と期限と・・・よっぽどパフォーマンスがビジネス上のボトルネックになっていないかぎり決済者がGoサインを出してくれることは難しいかもしれません。
個人開発であれば、単純にやりたいものをやればいいと思います。

Go言語に的を絞れば、Go言語はメモリを意識するプログラミングが出来る方だと思うので、効率よく書こうとすることが単純に高速化に貢献すると思います。

データを差分で管理する

有効度 ★★★★☆
可読性 ★★★☆☆

これは、GitやDockerイメージなどで実践されている方法です。
扱うデータの履歴を管理したい場合、すべての情報を毎回保存していたのでは、メモリ・ディスク消費量が大きくなり、それらの確保にCPUパワーが使われるようになるためパフォーマンス低下を招きます。
データの保持方法を前回の状態＋今回の操作という形で持つことができないか検討する価値は大いにあります。
そして、出来るなら、はじめの設計段階から検討するようにしましょう。ファイルやデータの形式をあとから変更するのは非常に大変です。

並行処理・並列処理が可能な設計をする

有効度 ★★★★★
可読性 ★★★★☆

どちらもマルチコア・マルチCPUを有効活用するために必要な考え方です。
システム上の役割をクラスなどのオブジェクトに分割するまでは良いのですが、それらが並行に実行できるように、キューイング・メッセージのやり取り機能を適切に備え、処理をブロックしない設計にしなければ、そこがボトルネックとなってしまいます。
処理するデータが大きい場合は分割し、並列処理が出来るかも検討しましょう。

計算結果をキャッシュする(メモ化)

有効度 ★★★★☆
可読性 ★★★★☆

入力パラメータに対するハッシュをキーとして、計算結果をキャッシュしておけば、次回移行の計算で同じパラメータでの計算が行われるときにキャッシュを使用して、一瞬で答えを返すことが出来るので、実行速度が改善されます。
使えるメモリと相談しなければならないのと、どれだけ同じパラメータでの計算が行われる想定して、有効な方法なのか検討が必要です。

配列の要素をカウントするといった処理も頻繁に行うのであれば、キャッシュとは少し感覚は違いますが、トータルの個数をあらかじめ要素の追加削除に合わせて増減させておくことで、要素を総なめする必要がなくなり高速になります。
LinkedListを作るときにcountを求めるために、Linkをたどって数えるよりcountを別途持っておくほうが効率的なのと同じです。

データ形式を見直す

有効度 ★★★☆☆
可読性 ★★★☆☆

所持アイテムを管理するデータを考えます。

• 所持アイテムはa-zの26種類。同じアイテムは区別しない。
• 所持アイテムはソートしても、しなくてもよい。
• 所持アイテムは出し入れを頻繁に行う。

type Items []string
// contains, count, removeとかいろいろ実装してあることにする

items := Items{"a", "b", "c", "d", "a", "a", "b"}

// 普通に実装すると、どれも線形探索をすることになる
// ソート済みなら二分探索木が最速だが、出し入れが多いならソートのコストが重い
items.contains("a") // true
items.remove("c")
items.count("a") // 3

このデータなら、mapを使うほうが高速にデータを扱えます。
キーがアイテム名、 値はアイテムの所有数です。

type ItemMap map[string]int
// contains, count, removeとかいろいろ実装してあることにする

itemsMap := ItemMap{}
itemsMap["a"] = 3
itemsMap["b"] = 2
itemsMap["c"] = 1
itemsMap["d"] = 1

// containsはkeyで検索して、カウントが1以上ならtrue
itemsMap.contains("b") // true

// addはkeyのカウントを1増やす
itemsMap.add("a") // 3 -> 4
// removeはkeyのカウントを1減らす
itemsMap.remove("c") // 1 -> 0

必要な最低限のメモリを一気に確保する

有効度 ★★★☆☆
可読性 ★☆☆☆☆

var a1  []int = make([]int, 0) //キャパシティの指定なし
var a2  []int = make([]int, 0, 10) //キャパシティの指定あり
append(a1, 1)

Go言語ではmakeで配列を用意しますが、内部的な実装としては、キャパシティを指定しない場合はある程度余裕を持ったキャパシティが確保されます。そして、appendを行う際にキャパシティが不足するようなことになれば、

• 現在のキャパシティのおよそ倍の容量の配列を新たに生成
• 今の配列をコピー
• ポインタを新しい配列に変更

という手順が行われるため、頻繁にこの動作が行われると実効速度の低下に繋がります。
また、扱うデータの個数があらかじめわかっている場合は、必要なメモリを一気に確保することで効率が上がります。
たとえ配列の要素数が100と50程度の差でも何千万回とメモリ確保が行われる場合は確実に効いてきます。

よくある例では、N×Mの２次元座標のデータを確保しようとするときは、１次元配列と考えて、 make([]int, N * M, N * M)といった具合に、一括でメモリを確保しましょう。

そして、可能ならば、無駄なメモリ確保を減らすために、一度確保したメモリを使い回すことも有効です。
しかし、使い回しがコードの広範囲に渡るのはメンテナンス性を大きく損なうので避けるべきかと思います。

deferをやめる

有効度 ★☆☆☆☆
可読性 ★☆☆☆☆

Go言語特有の内容ですが、他の言語にもこういった機能はあると思います。マネージド◯◯というやつです。
deferはとても便利で、後処理などを確実に実施してくれます。
しかし、deferあり・なしで計測してみると、結構なコストを支払っていることがわかります。
繰り返し実行される関数でdeferをやめて、コードパスを単純化し、確実に終了処理を行うようにすれば高速化します。

配列データのStringerインターフェース実装

いつもテンプレートとして参照するので書いておきます。

func (a *Array) String() string {
    bufLen := len(a) // 配列の内容に合わせてキャパシティを指定
    buf := make([]byte, 0, bufLen)
    for _, v := range a {
        buf = append(buf, v.String()...)
    }
    return string(buf)
}