Posted at

cachegrindを使って高速化してみる

More than 1 year has passed since last update.

細かすぎて伝わらないエラトステネスの篩の高速化に触発されてプログラムを書いていた時にキャッシュを意識しないと高速化できなかったので、cachegrindを使ってその影響を調べてみました。


cachegrindとは

バイナリ書き換えを使用したデバッグツール群Valgrindの中の、キャッシュプロファイラプログラム。valgrind --tool=cachegrindとして実行する。

ぷろんご。


環境


  • Core i7-4771@3.5GHz L3cache:8MB

  • bash on Windows

  • clang 3.8.0-2ubuntu4 -O3 -march=native

  • valgrind-3.11.0


キャッシュを汚さないようになるべく小さなデータ構造を使うと高速化する


まずは普通に実行時間を計測してみる


base.c

#include <stdio.h>

#define MAXVAL 200000000

int main() {
int i, j, count = 0;
static int flags[MAXVAL + 1] = {};
for (i = 2; i <= MAXVAL; i++) {
if (flags[i] == 0) {
++count;
for (j = i * 2; j <= MAXVAL; j += i) {
flags[j] = 1;
}
}
}
printf("%d\n", count);
return 0;
}

flagsの型をlong long, int, short, charのそれぞれに変更して、速度の変化を確認します。計測はtimeコマンドを使い、最低5回計測した平均をとることにします。


bit幅
実行時間

long long
64bit
5.8s

int
32bit
4.7s

short
16bit
4.0s

char
8bit
3.5s

bit幅が短い方が実行時間が短くなっています。フラグに必要な領域は1bitで済むので、以下のようにしてみます。


base_bit.c

#include <stdio.h>

#define MAXVAL 200000000

int main() {
int i, j, count = 0;
static long long flags[(MAXVAL + 1) / 64] = {};
for (i = 2; i <= MAXVAL; i++) {
if ((flags[i / 64u] & (1ull << i % 64u)) == 0) {
++count;
for (j = i * 2; j <= MAXVAL; j += i) {
flags[j / 64u] |= 1ull << j % 64u;
}
}
}
printf("%d\n", count);
return 0;
}

実行結果を以下にまとめてみます。


bit幅
実行時間

long long
64bit
5.8s

int
32bit
4.7s

short
16bit
4.0s

char
8bit
3.5s

bit
1bit
2.3s


余談


  • -march=nativeによる違いは、レジスタ割り当ての違いを除けば、inc esiadd esi, 1に変わるだけでした。inc命令はキャリーフラグを変更しない、つまり前の結果に依存する(パーシャルレジスタストールが起こる)ため、遅くなります。intelの最適化マニュアルにもinc/decはadd/subにしろと書いてあります。


  • flagsは、main関数中のstatic変数としても、global領域の変数としても、あるいは= {}をつけてもつけなくても、速度は変わりませんでした。


  • base_bit.cにおいてi / 64ui % 64uとしている部分があります。C99以降では、割り算の商は0側へ丸められます。このため、64で割るといった場合でも、単純に算術シフト命令を使うわけにはいかず、以下のような命令が生成されてしまいます。


mov edx, r9d  ;; r9d は i が入っている。

sar edx, 31 ;; edx = i<0 ? -1 : 0; と等価。
shr edx, 26 ;; ここまでで、edx = i<0 ? 63 : 0; と等価。
add edx, r9d ;; ここまでで、edx = i<0 ? i+63 : i; と等価。
sar edx, 6 ;; edx >>= 6; により、edx = i / 64; を計算した。

また、余りに関しても全く同様の問題により、単純に下6bitのマスクをとるというわけにいかなくなっています。実際にはiに負の値が入ることはないので、単純に算術/論理シフトや論理積演算をしてもらえれば同じ計算結果になるはずですが、コンパイラには見抜けなかったようです。解決方法としては、


  1. シフト演算子>>とビット積演算子&を使う


  2. iunsignedで宣言する


  3. iunsignedにキャストする

  4. リテラル64(これはint型である)を64uとしてunsigned型のリテラルとする(unsignedを含む二項演算はもう片方もunsignedに変換されます)

などが考えられます。これらはどれも一長一短です1が、ソースコードの変更がなるべく少なくなるようにここでは4.を選択しました。

実際どのくらい遅くなるかというと、全部64と書いた場合が2.68s、全部64uと書いた場合が2.36sと、10%以上変わってくることが分かります。


cachegrindでキャッシュヒット率を見る


bit幅
実行時間
LLd misses(read)
LLd misses(write)
LLd misses(sum)

long long
64bit
5.8s


int
32bit
4.7s
6.3%(12.5M/200M)
68.7%(430M/627M)
53.6%(443M/827M)

short
16bit
4.0s
3.1%( 6.3M/200M)
60.1%(376M/627M)
46.3%(383M/827M)

char
8bit
3.5s
1.6%( 3.2M/200M)
52.3%(328M/627M)
40.0%(331M/827M)

bit
1bit
2.3s
17.2%(176M/1027M)
0.0%( 818/200M)
14.4%(176M/1227M)

※配列のサイズが大きすぎてmmapに失敗

やはりbit数の小さい型を使うにつれてキャッシュミスが減っていることが分かります。特にreadはintshortcharときれいにミス率が半減しています。一方でbitは傾向が大きく違いますが、複合代入命令を使っているところでは、参照回数・キャッシュミス回数はread側に計上され(書き込む前に読み込みが発生するため)、write側には計上されないこと、bt命令をなぜかwrite回数に計上していることが原因であると考えられます2。このようにread/writeや参照回数を見ていてもあまり意味のある結果が得られないため、以下では、ミス回数を中心に見ていきたいと思います。


if文のコストとキャッシュミスのコスト、どっちが高い?


知っている合成数 × 今見ている素数 のパターンは、既にフラグが立っているはずなので、これはフラグを起こさなくてよい。


を用いた最適化をする場合、if文のコストがかかります。逆にそれをしない場合、flagがすでに立っているところのflagを立てようとしてキャッシュミスするという残念なことになる可能性があります。このトレードオフについて、調べてみます。


if.c

#include <stdio.h>

#include <math.h>
#define MAXVAL 200000000

int main() {
int i, j, f, s, count = 2;
int max = (int)sqrt(MAXVAL) + 1;
static int flags[MAXVAL + 1] = {};
for (i = 5, f = 4; i <= max; i += (f = 6 - f)) {
if (!flags[i]) {
++count;
s = MAXVAL / i;
for (j = s - !(s & 1); j >= i; j -= 2) {
if (!flags[j]) flags[j * i] = 1;
}
}
}
for (; i <= MAXVAL; i += (f = 6 - f))
if (!flags[i])
++count;
printf("%d\n", count);
return 0;
}

ifなしのコードは、14行目(最内for文の中)のif文をなくすだけです。


bit幅
ifあり

ifなし

実行時間
LLd misses
実行時間
LLd misses

long long
64bit
1.15s

1.83s

int
32bit
0.88s
102.4M
1.58s
166.0M

short
16bit
0.68s
76.4M
1.31s
142.7M

char
8bit
0.56s
58.0M
1.12s
119.8M

bit
1bit
0.57s
23.4M
0.64s
58.3M

ifなしの方がキャッシュミスが発生しやすく、それにより無駄な時間がとられていることが分かります。flagを1bitにした場合は、この影響が小さくif文のオーバーヘッドの方が大きいと考えていましたが、この計測によればまだifありの方が速いようです。


if_no2x.c

#include <stdio.h>

#include <math.h>
#define MAXVAL 200000000
#define BITS (sizeof(int) * 8)
#define FLAGS_NUM (MAXVAL / BITS + 1)

static int flags[FLAGS_NUM] = {};

inline static void upflag(int i) {
i = i / 2 - 1;
flags[i / BITS] |= 1 << (i % BITS);
}

inline static int getflag(int i) {
i = i / 2 - 1;
return (flags[i / BITS] >> (i % BITS)) & 1;
}

int main() {
int i, j, f, s, count = 2;
int max = (int)sqrt(MAXVAL) + 1;
for (i = 5, f = 4; i <= max; i += (f = 6 - f)) {
if (!getflag(i)) {
++count;
s = MAXVAL / i;
for (j = s - !(s & 1); j >= i; j -= 2) {
if (!getflag(j))
upflag(j * i);
}
}
}
for (; i <= MAXVAL; i += (f = 6 - f))
if (!getflag(i))
++count;
printf("%d\n", count);
return 0;
}


ごくわずかに修正して、2の倍数用のbitを削りました。ここまで来るとさすがにキャッシュヒット率が上がるのでif文をなくした方が速度が上がるようです。


bit幅
ifあり

ifなし

実行時間
LLd misses
実行時間
LLd misses

long long
64bit
1.15s

1.83s

int
32bit
0.88s
102.4M
1.58s
166.0M

short
16bit
0.68s
76.4M
1.31s
142.7M

char
8bit
0.56s
58.0M
1.12s
119.8M

bit
1bit
0.57s
23.4M
0.64s
58.3M

halfbit
0.5bit
0.60s
12.2M
0.55s
34.1M


余談


  • 手元のノートパソコンでは1bitの場合はif文を削除した方が速く、Ishotihadus氏のMacでも同様の結果が得られていたのですが、今回の環境ではif文があったほうが良いようです。

  • 平方根はコンパイル時に計算されている(14144という数値が埋め込まれている(<=maxのところが<14144にコンパイルされる) )のでそもそも速いとかはありませんでした。そういえば-lmをつけてコンパイルしていないような……。


キャッシュをヒットさせるためにブロック化する

fujitanozomu氏がコメントに記載した、ブロック化を行ったコードについてもcachegrindで確認してみましょう。

このコードは、$\sqrt N$までifなしで篩った後、それらの倍数の篩いをブロック化して行っているようです。フラグはcharで持っていて、bit演算を使っていないようです。

ブロックサイズ
実行時間
LLd misses
D1 misses
備考

200000000
3.85s
434.10M
437.85M
実質ブロック化なし

10000000
1.05s
101.63M
231.42M

8388608
0.89s
6.32M
222.01M
L3キャッシュは8MB(ただし共有)

7340032
0.80s
6.34M
226.57M

6291456
0.74s
6.28M
222.01M

4194304
0.58s
6.28M
221.96M

2097152
0.57s
6.27M
221.71M

1048576
0.56s
6.26M
219.77M

262144
0.46s
6.25M
211.41M

65536
0.40s
6.25M
159.83M

40960
0.39s
6.25M
107.38M

34048
0.26s
6.25M
39.27M

32768
0.23s
6.25M
13.86M
L1dキャッシュは32KB

16384
0.27s
6.25M
8.64M

8192
0.30s
6.25M
6.33M

ブロックサイズをちょうどL1キャッシュのサイズ32KBに設定するとD1 missesがかなり減って高速になっています。それよりブロックサイズを減らすと分岐回数の増加などにより、徐々に遅くなるようです。


まとめ

高速化をしたいときはアセンブリを見たりプロファイラを見たりするものですが、キャッシュの威力はとても強いのでキャッシュプロファイラも使いましょう。





  1. シフト演算子は、「見慣れない」とか「最適化はコンパイラに任せろ」との意見があり、また、ループ変数をunsignedで宣言することは賛否両論です(たとえば、Google C++スタイルガイド)。整数昇格は多くの落とし穴を生んできました。 



  2. base_bit.cのlong longcharshortに置き換えた場合、機械語としては複合代入命令ではなく二つの命令に分割されました。この時、参照回数は200Mに627Mを加えた827Mとなったため、この予測はおそらくあっていると思われます。逆に、intに置き換えた場合は複合代入命令にコンパイルされ、参照回数は200Mのままでした。次に、コンパイル時にアセンブリ言語で出力し、bt命令の部分にもう一度bt命令を挿入したところ参照回数が400Mになったので、write参照回数200Mの原因はbt命令です(cachegrindのバグ?)。read回数は外周のforループの200M+内周の複合代入命令627Mで合わせて827Mのはずですが、1027Mになる理由はわかりませんでした。