Cプログラム高速化研究班を読んだ

このあたりの低レイヤの知識が薄かったのでとっかかりとして良かった。ただ、薄い本であり、この本だけで十分な知見が得られるかというとそんなことはないので、後は実践あるのみ と感じた。

Cプログラム高速化研究班 コードを高速化する20の実験と達人の技

posted with amazlet at 17.08.14

片山善夫
USP研究所
売り上げランキング: 280,025

Amazon.co.jpで詳細を見る

1章 CPUとコンパイラについてちょびっと

１章の内容は自分は知っていたので読み飛ばし。詳解システムパフォーマンス輪読会 6章 CPU および perf stat の内容に近かった。

• キャッシュライン64bytes (8bytes)単位で転送される

• アセンブリ読むときはレジスタの役割表を見ながらじゃないと読み解けなさそう

2章 実行コストの感覚を身につける

• ループ処理を速くするには、単純に if の数を減らすために、中の処理をコピペしてたくさん並べる
  • あとで出て来るが、分岐を減らすだけでなく、CPUに載っている加算器4つを並列で使える効果がある
• cc -S でアセンブリを生成

b = 0
do {
  a += b;
  a += b;
  a += b;
} while (--n > 0);

が

b = 0
do {
} while (--n > 0);

のように最適化されてしまうので、実験ではそれを防ぐために b = atoi(argv[0]) としたり苦労している話。

• 3.2GHz 逆数の0.3ナノ秒がCPUのサイクルタイム
• CPU内部に複数の加算器があるので、変数を分けて最後にマージしたほうが速い(sequentialにコードを書いても)。部品の数だけ並列にやってくれる。変数が一つだと直列になってしまう
• 乗算器は加算器ほどの数が用意されてないし、遅い
• 2の冪数の定数との乗算はコンパイラがシフト演算に最適化する。
  • 2の冪数+1の場合lea命令が使える。変数との乗算は最適化できない
• メモリ 32kb 8way と言ったら 8本あって並列化されてるということ
  • 合計256kbということであってる?
• if (b < 0) a++ 条件成立時の加算より、不成立時のジャンプ命令のほうが遅い。!!
• 分岐命令があると、どちらに飛べばいいかわからなくなるので、先に並列実行しておくことができず、待ちになってしまう。分岐予測して先に実行しておき、間違えたら捨てる。投機的実行
• 64bitでは関数の引数は6個までレジスタに入れて渡される。それ以上はスタック(メモリ上にある) <= だから gdb で見ると optimized out といつも出てるのか

3章 遅いのはどこか

• gprof を使う
  • static link させたものだけプロファイリングされるので、gcc -p -static するな
  • プロファイラ用のライブラリをリンクしないと細かいのは取れない -lc_p
  • gcc に -pg オプションをつけて gmon.out を吐いておかないといけない <= 使いづらいなー

4章 達人の方法論

• メモリのキャッシュラインを気にして matmulの演算順序を変える話
  • matmul のメモリアクセス順序話はどこでもでてくるなぁ
• 加算器が４つ載っている
  • ループの展開(unrolling)で演算器4つ並列で使い切る話
  • 単に分岐命令の数を減らす効果ももちろんある
  • 要素が4の倍数じゃないとダメだからゴミ詰め込みしておかないといけないんだよな
• strcmpは \0 を見つける為に、一文字ずつ比較
  • ワード単位でできないのは、間違えて超えてしまうとセグるから
• memcmp は8バイトずつ比較できる
  • 8バイトでマッチしなかった場合に1バイトずつの比較にfallbackする
  • コンパイラにmemcmpがインライン展開されて１バイトずつの比較になってしまい、逆に遅くなってしまう事例(というかデフォルト挙動)の紹介。-fno-builtin-memcmp で抑制
• sseなら1クロックで16バイトごと処理できる
  • メモリアクセスは速くならないわけだけど、どうなんだ?
• パイプラインのがバッファは64kb
  • 出力先がファイルではなくパイプの場合は、バッファサイズを64kbにすると速い
  • 出力先がファイルか、パイプ化によってバッファサイズを変えるチューニングが効く
• stdioのバッファは変更可能
  • デフォルト4kb
  • 著者が実験した環境では4mbにしてファイルに書き込むほうが速かったようだ。

5章 コンパイラを骨までしゃぶる

gcc の最適化オプションなど。けっこう一般的な知識なので読み飛ばした。

6章 業務システム向けのヒント

半角文字を全角文字に変換するなどの、具体的な話なので必要になったら改めて読むかも。