🖥️

高速なプログラムを書くために

2024/03/09に公開

C++

はじめに

本記事は自身のプログラムをとにかく速く動かしたいと思っている人のために、4年間のプログラミングで知った高速化手法や、高速化を行う上で知っておいた方がいいと思うことを紹介していきます。
　具体的にそれぞれをどのように実装すればよいのかは他の記事に任せ、本記事では「どういった高速化法があるのか」「高速化する上で何を考えるべきか」を知ってもらうことを目的にしています。
　私自身は普段 C++ と CUDA C++ を用いているので、この記事にはこれらの言語特有な仕様も含まれています。

高速化の効果(私自身)

この項は高速化手法ではないので本論を早く読みたい場合は飛ばしてもらって大丈夫です。私自身の４年間の高速化の成果の話をしていきます。
　趣味で数学をやっていたときに、とある数列を具体的に計算したいと思ってプログラミングを始めたのですが、そこから高速化を4年間行った結果、初めて書いたその数列の各項を求めるプログラムと比較して

GPUを利用したプログラムで 7700万倍 高速化
GPUを利用しないプログラムで 2700万倍 高速化
当時と同じPCで 300万倍 高速化

を実現しました。かなり高い高速化率ですが、途中でPCを買い替えていたり、科学計算でかなり高速化しやすいものだったりしてここまで来ました。
　大きく変化した改良事項とそれぞれの時期は次の通りです。括弧内は初めて作ったコードでの速度を1としたときの各コードの速度の目安です

2020年3月：Javaで作った初めてのプログラム完成 (1)
2020年4月：標準ライブラリの多倍長整数を使ったコード(1万)
2021年12月：アルゴリズム変更・それに伴い作成し改良していた自作多倍長整数が速度で逆転(55K)
2022年3月：上のコードを改良(11万)・PC買い替え(13万)
2022年5月：Go言語での開発開始・標準多倍長整数ライブラリを用い、マルチスレッド化(140万)
2023年9月：アルゴリズム変更・GPGPUを行う(5700万)
2023年10月：同アルゴリズムをC++のCPUのコードにも採用・SIMD化(CPUのみで360万)
2024年3月：アルゴリズム変更(7700万)
2024年3月：同アルゴリズムをC++のCPUのコードにも採用・キャッシュヒット率を改善(CPUのみで2700万)

ここに書いてない改良事項も含めて、このような沢山の改良の結果現在の高速化率になっています。これから紹介する高速化手法や考えはこれらのうち特に効果が高かったものなので、きっと役に立つはずです。

１、最適化のコンパイルオプション

C,C++の高速化では最も簡単で定番のものだと思います。
　最適化の度合いに応じてO1,O2,O3とありますが、基本的にはO2、うまくいかなければO1でいいと思います。私の環境ではO3やOfastを指定してもO2と大して速度は変わらないことが多かったです。
　O2の最適化オプションをつけたときの高速化率は体感で1.3～2倍程で、コードの書き換えを行わなくて良いので非常にコスパは良いです。加えてメモリアクセスの連続性やL2,L3キャッシュを意識してコードを書くとオプションをつけない場合と比較して3,4倍高速化する場合も多いので、これ以降で紹介する高速化手法との相乗効果も期待でき、特別な理由がない限りやるべき高速化です。

２、各演算の重さを知る

これは具体的な高速化手法ではなく、高速化をする上で知っておいた方がいい知識です。
　ビット演算、加減乗除、数学関数など、私たちはコード内で色々な計算を行いますが、私の体感では各演算の計算コストは次の通りです。

(ビット演算) = (加減算) \leqq (乗算) \ll (除算) < (数学関数)

よって除算や数学関数を他の軽い計算で置き換えるのは高速化が期待できますが、加減算や乗算は軽い演算への置換のために追加した条件分岐や演算回数の増加によってむしろ遅くなる可能性が高いです。
　乗算は加減算に比べてSIMD命令にしづらかったり、レイテンシが大きい場合がありますが、2の整数乗倍などのビット演算1つで置き換えられる場合を除いて、軽い演算への置換で速くなることはあまりありませんでした。
　ビット演算のコストは加減算より軽いと言われますが、現在のPC向けCPUにおいておそらくどちらも1クロックで計算されているか、違いがあってもレイテンシで分からなくなる程度です。加減算をビット演算にしてコードが複雑になる位なら、他の高速化を行った方が賢明です。
　また各型の計算速度を知っておくことも大切です。16bit,32bit,64bitなどC,C++には様々な整数型がありますが、これらの演算はSIMD命令などで一度に処理しない限り、私の環境では各整数型の計算コストはどれもほぼ同じです。よって計算コストを下げる目的で小さい型に入れる意味はほとんどありません。しかしメモリ使用量は違いますので、メモリの消費量を抑え、メモリからのデータ引き出し量を減らしたり、キャッシュヒット率を上げたりすることによって、高速化することもあります。メモリに関する詳細は「８、メモリアクセス・キャッシュヒット率」に後述します。

３、律速部分を調べる

プログラムを走らせたときに、コードのどの行にも満遍なく時間がかかることはほとんどなく、全体の律速となっている処理が存在するはずです。よってこのような律速部分を時間計測などで特定し、その部分を優先して高速化するべきです。コードの全てを高速化できればいいですが、時間は有限なのでそれはできません。
　加えて処理を高速化するためにコードを書き換えるとき、大抵コードは複雑化します。コードが複雑になるほどそれ以上の高速化の難易度は上昇し、可読性の低下、バグの発生を引き起こします。そのためコードを改良していくためには、律速部分に集中して高速化を行い、そうでない部分はライブラリなどを用いてできるだけ簡潔に書いた方が良いです。

４、より速いアルゴリズム

採用するアルゴリズムはできるだけオーダーが小さく、その係数が小さいものであるべきだ、というのは当然知ってると思います。特にアルゴリズムの変更は他の高速化と違いコードが簡潔になる場合もあり、効果も大きいので、非常に良い高速化です。
　しかしアルゴリズムを選ぶ上で意識すべきことはどのアルゴリズムが最速になるかは計算内容やハードによって違うということです。いくらオーダーの小さいアルゴリズムを採用したとしても、30桁程度の数の乗算にカラツバ法やFFTを利用したアルゴリズムを採用するのは逆に遅くなりますし、計算量が半減するアルゴリズムを採用しても、メモリアクセスが律速になっているなら意味はあまりなく、むしろメモリアクセスが連続でなくなり遅くなるということもよくあります。
　逆からいえば、今使っているアルゴリズムよりも計算量が多くても、新しい技術によって高速なアルゴリズムに化けることがあり得ます。例えばメモリの使用量が減らせるが計算量が増えるアルゴリズムがあったときに、メモリ使用量が減ったことでVRAMに乗るようになって、GPGPUに採用できる可能性があります。GPUはCPUに比べて単純な演算能力は高いので、計算量が増えてもハードの力の差で高速に動作することがあります。
　新しいアルゴリズムは一朝一夕で思いつくものではないですし、どれが最良のアルゴリズムかは状況によって異なるので、ネット上に色々なアルゴリズムが転がっているのでそれらで使えるものがないか探しつつ、演算やハードの知識をつけることで各アルゴリズムの強みと弱みを把握することが重要です。

５、ハードのことを知る

上のアルゴリズムの項で書いたように、どのアルゴリズムが高速かはハードによって違いますし、何が律速になりやすいのかもハードによって違うので、高速なコードを書くにはハードの知識が必要です。
　私が書いてきた中で特に使う知識は次の通りです。

CPUの計算力はシングルスレッドで数億～数十億回/s、マルチスレッドで数十億～数百億回/s
GPUの計算力は千億～十兆回/sで、(一般向けは)double型が極端に遅い
GPUは条件分岐などの途中で計算内容が変わる処理が遅い
GPUメモリはCPUメモリに比べて何倍も高速
CPUのキャッシュは1コア当たり1MB前後で、int型で言えば数十万個分

ハードに関してはそれぞれの環境で全く変わるので、各自調べるのが一番ですが、各パーツの公式サイトにスペックは書いてあるのでそれを確認すればよいですし、高速化の過程でおおよその速度感は知ることができると思います。
　重要なのはハードの知識から律速が何かを見極め、最適なアルゴリズムを選び出せるようにすることです。思いついた全てのアルゴリズムを試しに実装することは時間的に不可能ですし、計算コストとメモリアクセスのどちらが律速かが分かれば、高速化手法を考える際にもそこを減らすことに焦点を当てて考えればよくなります。

６、マルチスレッド化

高速化手法の中でもトップクラスに定番の手法だと思います。
　この手法の一番のメリットはどんなコードでもまず間違いなく高速化すること、一番のデメリットはどんなコードでもまず間違いなく複雑になることだと思います。何千スレッドも立ち上げるなら別ですが、数十スレッド程度なら立ち上げのコストはそこまで重くないですし、計算力が単純に増やせるので多少無駄が増えても高速化します。一方スレッド立ち上げや排他制御の分コードは複雑化するので、シングルスレッドのプログラムで限界まで速くした後、最後に実装するのが最も実装しやすいです。
　マルチスレッド化する上で知っておくべきことは、マルチスレッド化するとメモリアクセスが律速になりやすいことです。マルチスレッド化は計算力は大きくなりますが、メモリ自体の速度が上がるわけではないので、相対的にメモリアクセスが律速になります。特に最近のCPUは論理コア数が十数あるのも普通なので、それが顕著です。一応メモリのアクセスにもCPU側で一定の処理が必要なので、元々メモリが律速であるプログラムでもマルチスレッド化で高速化することがありますが、効果はあまり大きくないので他の高速化手法を考えた方が良いです。

７、より速い計算手法

この項で指す計算手法というのはBarrett reductionやMontgomery乗算のように、コード全体のアルゴリズムを変えてしまうものではなく、計算コストのかかる処理を局所的に定数倍高速化してくれるような計算手法を指します。つまりアルゴリズム変更というほどではない計算方法の改善です。
　これに関しては自分のコードで使える先人が考えた計算手法がないか調べるのが一番速いです。小規模な計算高速化手法はすでに他の人が考えてそれを発信している可能性が高いので、自分で考えるよりも調べる方が効率的です。それにより浮いた時間を使ってハードの勉強や律速部分の調査、後述するキャッシュヒット率の改善など環境依存の強い部分の高速化を行った方が結果的に高速化できます。

８、メモリアクセス・キャッシュヒット率

ここまでの高速化手法で書いたように、高速化を繰り返すとメモリ速度やメモリのレイテンシが律速になる場合がかなり出てきます。これを解決できなければ計算力は余っているのに速度が頭打ちしてしまいます。そこでメモリの負担を減らすようにコードを書くことも大切です。
　メモリの負担を減らすために一番分かりやすい方法はそもそもメモリアクセスを減らすことです。例えばある配列Aの各要素と、その10倍の値を毎回計算で用いる場合、10倍の値をあらかじめ計算して別の配列Bに格納しておけば、確かに計算量は減りますがメモリアクセスは倍になります。このときメモリアクセスが律速ならば、計算のたびに10倍の値をAの要素から求める方が高速になります。このように多少計算が増えても、メモリアクセスを単純に減らせるのなら高速化し得ます。
　他にもメモリアクセスを行うアドレスを連続にすることも効果的です。配列に対して順番にアクセスしたり、CPUで言えば64bit、GPUで言えば128～320bit程度の単位で連続するデータを引き出しているので、そのような単位でデータを扱ったりすることによりメモリの負担を減らすことができます。データのアクセス順序を変えるだけで高速化することも多いですし、連続したメモリアクセスはSIMD命令とも相性が良く、コンパイラの最適化でSIMD命令が使われやすくなることにもつながるので、予想以上に高速化する場合もありおすすめな高速化手法です。
　そして上の２つよりも高度な手法になりますがキャッシュヒット率を上げること、要はそもそもメモリアクセスをしなくていいコードを書くことはメモリ律速を回避する上で非常に強力な手法となります。ハードの項で書いたように現在のCPUは1コア当たりMB単位のL2,L3キャッシュがあるので、十万程度の配列ならL2,L3キャッシュに乗ってしまいます。よって1次元配列程度ならメモリにほとんどアクセスせず、キャッシュからデータを引き出して計算ができる可能性があります。特にL2キャッシュはコアごとに存在するためマルチスレッド化するほど実質的に増えるので、マルチスレッド化でメモリ律速とならずコア数にほぼ比例して速度を上げられることもあります。ゆえにキャッシュヒット率を上げることはマルチスレッド化で特に効果を発揮します。

９、SIMD命令・GPUの活用

この2つはかなり特殊なので、そもそも労力をかけて実装するべきかは場合によります。環境依存も強いので1～8で挙げた計算手法で十分な計算速度が確保できるなら、実装しない方が可読性も上がりますし再利用しやすいです。
　まずSIMD命令についてですが、私自身がAVX,AVX2しかほぼ経験がないのでこの2つに関する話が中心です。SIMD命令のメリットはGPUを使わずCPU上で実行ができること、デメリットは使えるCPUが限られることです。とはいえintelのHaswell(第4世代)以降のCPU、AMDのRyzenCPUはAVX,AVX2に対応しているので、ここ10年程度のPCのCPUなら大抵使えるはずです。後述のGPGPUではコードを大きく書き換える必要がありますが、SIMD命令は通常のC++のコードの計算の一部をSIMD命令に書き換えるだけでよいので、実装しやすいです。
　加えてSIMD命令の強みとして仮にSIMD命令を使わなくても、それを意識してコードを書くと高速化する場合があることが挙げられます。コンパイラの最適化によりSIMD命令を使うようにしてくれることがあるので、明示的に書かなくても速度が上がることがあります。ただしSIMD命令で行える計算は限られているので、どのような関数があるのか把握しておく必要があります。参考文献の[1]にgccでSIMD命令を扱うための関数一覧があるのでこれを参照することを推奨します。
　次にCUDAやOpenCLなどによるGPUの活用、いわゆるGPGPUについてですが、GPGPUのメリットはCPUに比べてはるかに高い演算能力が得られること、デメリットは既存コードを大きく変える必要がある上に使える演算の制限も大きいことです。ハードの項で書いたようにGPUの演算能力はCPUの10～100倍ほども高いので、その能力を生かせるコードを書くことができれば大幅な高速化が可能です。仮に性能を引き出しきれなくとも、数倍程度の高速化なら十分に実現できます。しかしCPUを用いるコードに比べて制限が多く、どこのGPUかで扱える言語も環境も変わるのでSIMD命令以上に環境依存が強いです。ゆえにGPGPUは高速化率は非常に高いですが、その分扱いづらい面が大きいので、使用が有効な場面は限られます。