Cプログラム高速化研究班

プログラムの背後で、CPUはどのような働きをしているのでしょうか？本書はその原理と仕組みを簡単な実験で確かめ、コードを研ぎすます方法を紹介します。

【著者あとがきより】
高速なプログラムが求められる場面は少ないながらも厳然として存在し、いざ性能が必要になったときに対応できる技術者が非常に少なくなっているのが気がかりです。特に、業務システムなどの数値演算系以外の分野では、絶滅危惧種と言ってよいのではないでしょうか。
その原因のひとつは、高級言語と統合開発環境の普及によって、機械命令レベルのプログラム実行を意識しなくてもすむようになっていることです。どのように実行されるかを意識しないので、実行コストが高い処理が平気で使われています。もうひとつの原因は、アルゴリズムに対する理解不足です。
開発するプログラムが高度化、パターン化してきているため、アルゴリズムについて学ぶ機会がなくなっているのではないでしょうか。
本書は、プログラムを高速化する個々の方策を並べるのではなく、方策を見つけるための道筋を示すように心がけました。

目次

序章 高度に進んだ技術は魔法と見分けがつかない

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

1.1 高速道路と横断歩道
1.2 コンパイラは何をしているのか
　コンパイル後のアセンブリ言語プログラムを覗く
　最適化オプションを付けるとどうなるか
1.3 CPUは何をしているのか
　命令セットアーキテクチャとマイクロアーキテクチャ
　命令はどのように実行されるのか
　命令パイプライン
　キャッシュメモリ
　もっとキャッシュ
　キャッシュブロックの置換アルゴリズム
　スーパースカラ実行
[1章は重箱の隅なのか]

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

2.1 プログラムの実行コスト
2.2 計る・測る・謀る
　本書のアプローチ
2.3 ベンチマークテストプログラムの最適化を防ぐ
　操作の「おまとめ」を防ぐ
　初期値設定の最適化を防ぐ
　単純な繰り返し操作の最適化を防ぐ
　本書のベンチマークテストプログラム
2.4 検証――遅いのはどの操作?
2.5 基本の加算と代入
　単純な代入（レジスタ間の転送）
　単純な代入（データの競合がある場合）
　定数の代入
　変数どうしの加算
　変数に定数を加算
2.6 乗算は遅い
　変数どうしの乗算
　変数に定数を乗算
2.7 除算はとっても遅い
　変数で除算（レジスタどうしの演算）
　定数2、4で除算
　2のべき乗以外の定数で除算
　符号なし整数の場合はどうか
　2のべき乗で除算するときはシフト演算がお得
2.8 メモリへのアクセス
　小さい配列へのアクセス（狭い範囲のメモリ操作）　
　大きい配列へのアクセス（広い範囲のメモリ操作）
　デスクトップ向けCPUとの比較
2.9 コンディションで差がでる条件分岐
　else節のないif文
　else節のあるif文
2.10 32/64ビット環境で違う関数呼び出し
2.11 実験のまとめ
[愛がほしくば愛を差し出せ]

3章 遅いのはどこか

3.1 gprofを使ったプロファイリング
　gprofの使い方
3.2 何がどれだけ時間を喰っているか
　ライブラリ関数のプロファイルも取得する
　時間喰いの関数たち
　ライブラリ関数の呼び出し回数を表示させるには
3.3 何が何を呼び出しているか
3.4 プロファイリングの仕組み
3.5 そのほかのプロファイラ
[達人の技を伝える教育システム]

4章 達人の方法論

4.1 達人はどこに目をつけるか?
　ハードウェア編
　コンパイラ／ミドルウェア編
　アルゴリズム編
4.2 ［ハードウェア編］配列とキャッシュメモリの活用
　行列の積を計算する
　配列操作の順番を入れ替える
　ループを展開する
　行列のタイリング
4.3 ［ライブラリ編］遅い関数をめぐる紆余曲折
　なぜstrcmp関数は遅いのか
　最適化の落とし穴
4.4 ［ハードウェア編］SIMDを用いた文字列比較
4.5 ［ライブラリ編］入出力方法いろいろ比べ
　行データの入力方法を比べる
　出力方法はどうだろう
　パイプ入出力の特殊事情
　パイプ入出力 vs. ファイル入出力
4.6 ［アルゴリズム編］バイナリサーチと平衡二分探索木
　大量データのソート
[そこまでやる? ね、ね、そこまでやるの?]

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

5.1 レベル分けされている最適化オプション
　GCCの最適化オプション
　「最適化なし」はデバッグに役立つ
　未定義動作がないことを想定しているレベル2以上の最適化
5.2 最適化・レジスタ・外部変数
5.3 共通部分式削除を知ってプログラムすっきり
5.4 ポインタと強度低減
5.5 インライン関数でユーザー関数も展開
[他人に差をつけろ!]

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

6.1 ソートと文字列操作をねらえ
6.2 小数点数の計算と文字列／数値の変換
　ブロック入出力とフィールド分割
　小数部付きの数を集計する
　整数を文字列に変換する
　パフォーマンスチューニングの結果
6.3 半角文字から全角文字への変換
　文字のバイト数を判別する
　ASCII文字と半角カナ文字の判別
　ASCII文字から全角文字への変換
　半角カナから全角文字への変換
　パフォーマンスチューニングの結果
　文字のバイト数を調べる別の方法
　より道UTF-8
6.4 データの特性を利用した配列の探索
　データの特性を考慮する
　バイナリサーチとリニアサーチを組み合わせた照合
　パフォーマンスチューニングの結果
[あとがきに代えて]