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

目次

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

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 データの特性を利用した配列の探索

データの特性を考慮する

バイナリサーチとリニアサーチを組み合わせた照合

パフォーマンスチューニングの結果