C++ の小手先の速度改善

これは何？

下記の記事が興味深かったので、C++ でできる小手先の速度改善について書いた。

手段色々

以下に色々小手先の技っぽいもの（小手先じゃないものも含む）を色々書いてみた。

効果がありそうなものもほとんど逆効果のものも書いた。
見出しでは区別できないので気になったら本文読んでね。

シフト演算

C/C++ で符号なし整数の 2倍・半分 などを計算する際にシフト演算で書いたほうが速い、という処理系はほとんどないと思うんだけど、どうだろう。
定数による除算・乗算 はコンパイラが賢くやってくれるので任せるのが良い。u*5 と u+(u<<2) のどちらが良いかはコンパイラに任せたほうがいい。CPU によって違うので。

それと。コードの意味がわかりにくくなるのでお勧めできない。

測定の上でなるほど速くなるということならそうすればいいとは思うけれど、その場合は単に掛け算割り算がしたいだけだとコメントに書いたほうがいい。

コンパイラオプション

gcc の場合、特段の事情がなければ -O2 をおすすめする。
-O3 は -O2 より速いとは限らない。

とはいえ、具体的にこの最適化がまずそうということはないし、-O3 でまずいことが起こる事例をパッとは作れなかったので、お好みで、と思う。

const参照渡し・ポインタ渡し

C++ で、速度のためにポインタ渡しをする状況はちょっと思いつかない。
なにかあるかな。

ポインタでではなく const 参照で渡したいのは

c++

class Foo{略};

void hoge( Foo const & f );
void fuga( Foo const * fp );
Foo piyo();

という状況で hoge( piyo() ); と書けるから。

ポインタで受ける fuga を呼ぶためには一回変数に受けないといけないのでめんどくさい。

もちろん（速度目的ではなく）ポインタの指す先を書き換えてほしいということでポインタを使うことは大いにある。

ムーブセマンティクス

ユーザー定義クラスで適切に定義するとめちゃくちゃ速くなることがある。
ユーザー定義クラス以外では、コンパイラが勝手にやってくれるので、あんまり意識して書く必要はないんじゃないかな。

※ ユーザー定義クラスに適切に move を入れるのはあまり小手先という気がしない。

noexcept

ユーザー定義クラスで move コンストラクタを noexcept にしておくと、std::vector なんかに入れたときに使ってくれるので、適切に定義しておくとめちゃくちゃ速くなることがある。
参照: https://qiita.com/kei10in/items/00f65e68a3d08093aceb

※ noexcept 自体は小手先っぽい話だけど、必要な理由まで考えるとあまり小手先という気がしない。

コンテナ

適切なコンテナを使うのは難しいよね。
先頭や真ん中の挿入削除がたくさんあるのに vector<int> 使ったりすると遅いよね、と思いきや、要素数が最大 7 とかだと list<int> にするとかえって遅そう（測ってません）。

key-value pair だから map のたぐいが速いよね、と思っても、要素数が少なければ vector が速いし。（参考: 小さいサイズの辞書は線形探索でいいかも)

それはそれとして。vector での reserve は重要。
ちゃんとやるかどうかで観測可能なほどの差がでることが多い印象。

※ コンテナを正しく選ぶのは、小手先ではないと思う。

ループ

コンテナのループは、とりあえず range-based-for にしておけばいいと思う。
とはいえ、インデックスやイテレータを使いたいこともある。

for( auto it = v.cbegin() ; it != v.cend() ; ++it )
と書くより、
for( auto it = v.cbegin(), end=v.cend() ; it != end ; ++it )
と、ループが回る前に v.cend() なり v.size() を変数に受けておくとほんの少し速くなる場合がある。微々たる改善かもしれないが、可読性の低下も微々たるものなので悪くはないとおもう。

同じバイナリになることも多そうだけど、以下の例では違いがあると思う。

c++11とか

void foo( std::vector<baz_t> const & v ){
  for(略){
    bar(); // インライン展開されない関数
    // do something
  }
}

この場合、コンパイラは「bar() 内で v が書き換わるかもしれない」と疑わざるを得ない。
終了判定条件に v.cend() や v.size() などの記載をすると、関数呼び出しコストはインライン展開によってゼロになるだろうけれど、間接参照が入る分、変数で受けておく場合と比べるとちょっぴり遅そう。

もちろん観測できるほどの差になるかどうかは別の話。

++i と i++

++i の方が速くなるのは operator++ がインライン展開されない場合に限ると思う。
コンパイラにとってインライン展開が困難な場合は差があるかもしれないけど、普通 iterator はヘッダに定義があるのでどっちでもいい。

とはいえ、i++ と書くべき理由は特にないので返戻値が不要な場合は必ず ++i と書くようにしている。
しかし、その習慣のまま go のコードを書くとコンパイルエラーになる。

ループ外に出す

ループ外でできる計算をループの外に出すのは重要。小手先とは思わない。

地味なところで

c++

auto[c,k] = hoge();
sum = 0.0;
for( auto v:c ){  sum += v/k;  }

と、ループ内で除算するより

c++

auto[c,k] = hoge();
sum = 0.0;
auto kinv = 1.0/k;
for( auto v:c ){  sum += v*kinv;  }

と、ループ外で逆数をとってループ内では乗算にする方が速い場合が多かったり（CPU等色々による）。
必ずしも同じ値にはならないわけだけど、それでよければ乗算にするのは常套手段と思う。

コンパイル時に計算させる

constexpr と書かなくてもコンパイラに「あ、これ実行時にやらなくていいやつじゃん」とバレればコンパイル時に計算してくれる。

たとえば PI が円周率定数で a が変数だとして。
sin(a*PI*0.5)
と書くと掛け算が２回実行されてしまうが、
sin(a*(PI*0.5)) とか sin(PI*0.5*a)
だと PI*0.5 がコンパイル時に終わるので実行時の掛け算は一回で済む。
※ 計算結果がおなじになるとは限らない。誤差の出方・無限大になりやすさで違いがあると思う。

インライン展開

インライン展開は極めて重要。
インライン展開無しには C++ は成立しない、ぐらいに思っている。

ただ。
関数の inline 指定子は、もはや「インライン展開してね」という意味ではなく「関数定義が複数あるように見えてもエラーにしないでね」という意味だと理解しておいたほうがいいかもしれない。

インライン展開するかどうかは、基本的にコンパイラが決める。
inline 指定子があろうとなかろうと（Link time code generation が有効なら、翻訳単位が別であっても）コンパイラがインライン展開したいと思ったらするし、コンパイラの気が向かなかったらインライン展開されない。

とはいえ、強制インライン指定で速くなったりする事例もある。

キャッシュの利用

CPU によって動作も容量も違うので難しい。
「CPU によって」の部分も、ARM か x64 か、みたいな粒度ではなく、Core の 第xx世代以降からこういう動作に変わったとか、このモデルは L3 キャッシュが xx MB だとか、そういう感じ。

近くのメモリをアクセスするようにする、みたいな一般論はあるけど、この件であまり真剣に戦ったことはないのでよく知らない。

xor による変数の入れ替え

x, y が同じ長さの符号なし整数として

c++

x ^= y; y ^= x; x ^= y;

で入れ替えるという話。加減でもできる。

アセンブラでこの計算を使う場面は稀にあるかもと思うけど、C/C++ で速くなるストーリーはあまり想像できない。
遅くなることは容易に想像できる。

基本的に std::swap を使っておけば万全。上記の ^= を使った実装が役に立つ場面にはなかなか出会えないと思う。

likely / unlikely

私は書いたことないけど、 likely unlikely というマクロでコンパイラにヒントを与えることができて、状況によっては計算時間を半分にできるらしい。
参考: https://qiita.com/kaityo256/items/8a0c5376fad17907e1f6

SIMD の利用

x86_64 + gcc の場合 -O3 にするとコンパイラができる範囲で SIMD を使ってくれるらしい。
とはいえ、SIMD コードにすると繰り返しが少ない（3回とか）のループだとむしろ遅くなる。そしてコンパイラはループの繰り返し数を知らないことが多い。

likely とか使うとコンパイルに教えられるのかな？（未調査）

もちろん自力で SIMD を使うコードを書いてもいい。
その場合、C/C++ でどういう意味のコードなのかを残しておかないとわからなくなりがちだと思う。

マルチコアマルチスレッドの利用

OpenMP をうまく使えば 8コアとかなら最大 8倍（ふつうはせいぜい4倍ぐらいかな）速くなる。
しかし、うまく使わないとクラッシュしたり計算結果がおかしくなったり（毎回おかしくなるならいいんだけど、1万回に1回おかしくなるとかだと本当に困る）する。

あと。
マルチスレッド用の sort アルゴリズムを使えば速いとか、そういうのもある。
ほぼ、 std::sort に並列実行オプションつけるだけなので気軽に使える。
参考: https://qiita.com/Nabetani/items/2dc2264764e2c68e7bcf

新しい C++ を使う

C++ のバージョンを上げるだけで速くなることがある。
実行が遅くなることはないと思う。

参考: C++11 以降は、C++98 よりも 100倍以上速いことがある

まとめ

小手先ということなら

• そのコードでメモリの確保や開放が起こるかどうか。
• そのコードでメモリのコピーが起こるとしたら何バイトぐらいか。

あたりを意識しておくと良いように思う。

もちろん小手先ではないアルゴリズムそのものの改善の方がずっと強い。
アルゴリズムの改善なら 千兆倍速くなることだって普通にある。

1990年代まではわりと人間が頑張って最適化していたように思うけど、現代の gcc / clang / Visual Studio なんかを使っているのであれば、小手先面では人類の出番はあまりない。

小手先の最適化は基本的に全部コンパイラに任せるのがいい。

どうしても小手先の最適化をしたくなった場合

• その最適化が本当に必要であることを確認する
• その最適化に効果があることを測定する
• その最適化でわかりにくくなったコードにコメントをちゃんと書く

などの対応が必須と思う。

なんて書いたけど、ついつい小手先の最適化しがちではある。