Optimized C++ ―最適化、高速化のためのプログラミングテクニック

Table of contents

1. 日本語版へ寄せて
2. 訳者まえがき
3. まえがき
4. 目 次 (1/2)
5. 目 次 (2/2)
6. 1章 最適化とは
   1. 1.1 最適化はソフトウェア開発の一部
   2. 1.2 最適化は効果的
   3. 1.3 最適化しても大丈夫
   4. 1.4 こちらにナノ秒、あちらにナノ秒
   5. 1.5 最適化C++コード戦略のまとめ
      1. 1.5.1 より良いコンパイラを使う、コンパイラをよりうまく使う
      2. 1.5.2 より良いアルゴリズムを使う
      3. 1.5.3 より良いライブラリを使う
      4. 1.5.4 メモリ割り当てとコピーを減らす
      5. 1.5.5 計算を取り除く
      6. 1.5.6 より良いデータ構造を使う
      7. 1.5.7 並行性を高める
      8. 1.5.8 メモリ管理を最適化する
   6. 1.6 まとめ
7. 2章 最適化に影響するマシンの振る舞い
   1. 2.1 C++の嘘と真実
   2. 2.2 コンピュータについての真実
      1. 2.2.1 メモリは遅い
      2. 2.2.2 メモリはバイト単位でアクセスされているのではない
      3. 2.2.3 メモリアクセスによっては他より遅いことがある
      4. 2.2.4 メモリ語にはビッグエンディアンとリトルエンディアンがある
      5. 2.2.5 メモリ容量は有限
      6. 2.2.6 命令実行は遅い
      7. 2.2.7 コンピュータは決定が下手だ
      8. 2.2.8 プログラム実行に複数のストリームがある
      9. 2.2.9 オペレーティングシステム呼び出しは高価
   3. 2.3 C++も嘘をつく
      1. 2.3.1 文がすべて高価なわけではない
      2. 2.3.2 文は順番に実行されない
   4. 2.4 まとめ
8. 3章 性能を測定する
   1. 3.1 最適化マインドセット
      1. 3.1.1 性能は計測されねばならない
      2. 3.1.2 最適化技術者は大物狙いの狩人だ
      3. 3.1.3 90/10ルール
      4. 3.1.4 アムダールの法則
   2. 3.2 実験を行う
      1. 3.2.1 実験ノートをつける
      2. 3.2.2 ベースライン性能を測定し目標を立てる
      3. 3.2.3 測定できるものだけが改善できる
   3. 3.3 プログラム実行のプロファイルを取る
   4. 3.4 長時間実行コードを計測する
      1. 3.4.1 時間計測の「ちょっとした学習」
      2. 3.4.2 コンピュータで時間を測る (1/2)
      3. 3.4.2 コンピュータで時間を測る (2/2)
      4. 3.4.3 測定する際の障害を乗り越える
      5. 3.4.4 Stopwatchクラスを作る
      6. 3.4.5 テストハーネスでホットな関数の時間を測る
   5. 3.5 ホットなコードを探し出すためにコードのコストを見積もる
      1. 3.5.1 C++文それぞれのコストを見積もる
      2. 3.5.2 ループのコストを見積もる
   6. 3.6 ホットスポットを探し出す他の方法
   7. 3.7 まとめ
9. 4章 文字列使用を最適化する：事例研究
   1. 4.1 なぜ文字列が問題か
      1. 4.1.1 文字列は動的に割り当てられる
      2. 4.1.2 文字列は値だ
      3. 4.1.3 文字列はコピーが多い
   2. 4.2 文字列最適化の最初の試み
      1. 4.2.1 一時ストレージをなくすために変更文字列演算を使う
      2. 4.2.2 ストレージを確保することで再割り当てを減らす
      3. 4.2.3 文字列引数のコピーをなくす
      4. 4.2.4 イテレータを使ってポインタ参照外しをなくす
      5. 4.2.5 文字列値の戻り値のコピーをなくす
      6. 4.2.6 文字列ではなく文字配列を使う
      7. 4.2.7 最初の最適化努力のまとめ
   3. 4.3 文字列最適化の第2の試み
      1. 4.3.1 より良いアルゴリズムを使う
      2. 4.3.2 より良いコンパイラを使う
      3. 4.3.3 より良い文字列ライブラリを使う
      4. 4.3.4 より良いアロケータを使う
   4. 4.4 文字列変換をなくす
      1. 4.4.1 C文字列からstd::stringへの変換
      2. 4.4.2 文字符号化間での変換
   5. 4.5 まとめ
10. 5章 アルゴリズムを最適化する
    1. 5.1 アルゴリズムの時間コスト
       1. 5.1.1 最良時、平均時、および最悪時コスト
       2. 5.1.2 ならし時間コスト
       3. 5.1.3 他のコスト
    2. 5.2 探索と整列を最適化するツールキット
    3. 5.3 効率的探索アルゴリズム
       1. 5.3.1 探索アルゴリズムの時間コスト
       2. 5.3.2 すべての探索はnが小さいなら等しい
    4. 5.4 効率的整列アルゴリズム
       1. 5.4.1 整列アルゴリズムの時間コスト
       2. 5.4.2 最悪時性能のソートを置き換える
       3. 5.4.3 入力データの既知の特性を活用する
    5. 5.5 最適化のパターン
       1. 5.5.1 事前計算
       2. 5.5.2 遅延計算
       3. 5.5.3 バッチ処理
       4. 5.5.4 キャッシュ
       5. 5.5.5 特殊化
       6. 5.5.6 大量データ処理
       7. 5.5.7 ヒント
       8. 5.5.8 期待パスを最適化する
       9. 5.5.9 ハッシング
       10. 5.5.10 ダブルチェック
    6. 5.6 まとめ
11. 6章 動的変数割り当てを最適化する
    1. 6.1 C++変数の復習
       1. 6.1.1 変数の記憶域期間
       2. 6.1.2 変数の所有権
       3. 6.1.3 値オブジェクトとエンティティオブジェクト
    2. 6.2 C++動的変数APIの復習
       1. 6.2.1 スマートポインタは動的変数の所有権を自動化する
       2. 6.2.2 動的変数には実行時のコストがかかる
    3. 6.3 動的変数の使用を減らす
       1. 6.3.1 クラスインスタンスを静的に作る
       2. 6.3.2 静的データ構造を使う
       3. 6.3.3 newの代わりにstd::make_sharedを使う
       4. 6.3.4 所有権を不必要に共有しない
       5. 6.3.5 「マスターポインタ」を使って動的変数を所有する
    4. 6.4 動的変数の再割り当てを減らす
       1. 6.4.1 動的変数を前もって割り当てて再割り当てを防ぐ
       2. 6.4.2 動的変数をループの外で作る
    5. 6.5 不必要なコピーをなくす
       1. 6.5.1 望まないコピーをクラス定義で無効にする
       2. 6.5.2 関数呼び出しでのコピーをなくす
       3. 6.5.3 関数から戻るときのコピーをなくす
       4. 6.5.4 コピーフリーライブラリ
       5. 6.5.5 「コピーオンライト」イディオムを実装する
       6. 6.5.6 データ構造をスライスする
    6. 6.6 ムーブセマンティクスの実装
       1. 6.6.1 非標準的コピーセマンティクス：痛みを伴うハッキング
       2. 6.6.2 std::swap()：貧乏人のムーブセマンティクス
       3. 6.6.3 エンティティの共有所有権
       4. 6.6.4 ムーブセマンティクスの移動部分
       5. 6.6.5 ムーブセマンティクスを用いてコードを更新する
       6. 6.6.6 ムーブセマンティクスの難しいところ
    7. 6.7 データ構造をフラットにする
    8. 6.8 まとめ
12. 7章 ホットな文を最適化する
    1. 7.1 ループからコードを取り除く
       1. 7.1.1 ループの最後の値をキャッシュする
       2. 7.1.2 より効率的なループ文を使う
       3. 7.1.3 カウントアップの代わりにカウントダウンする
       4. 7.1.4 不変なコードをループから取り除く
       5. 7.1.5 不必要な関数呼び出しをループから取り除く
       6. 7.1.6 ループから隠された関数呼び出しを取り除く
       7. 7.1.7 高価で値がゆっくり変わる呼び出しをループから取り除く
       8. 7.1.8 呼び出しのオーバーヘッドを減らすためにループを関数の内側に押し込める
       9. 7.1.9 処理の頻度を減らす
       10. 7.1.10 その他にできること
    2. 7.2 関数のコードを取り除く
       1. 7.2.1 関数呼び出しのコスト
       2. 7.2.2 短い関数はインラインと宣言する
       3. 7.2.3 最初に使う前に関数が定義されている状態にする
       4. 7.2.4 使っていないポリモルフィズムをなくす
       5. 7.2.5 使っていないインタフェースを取り除く
       6. 7.2.6 テンプレートでコンパイル時に実装を選ぶ
       7. 7.2.7 PIMPLイディオムの使用を止める
       8. 7.2.8 DLL呼び出しをなくす
       9. 7.2.9 メンバ関数の代わりに静的メンバ関数を使う
       10. 7.2.10 仮想デストラクタを基底クラスに移す
    3. 7.3 式を最適化する
       1. 7.3.1 式を単純化する
       2. 7.3.2 定数をまとめる
       3. 7.3.3 より安価な演算子を使う
       4. 7.3.4 浮動小数点算術よりも整数算術を使う
       5. 7.3.5 doubleはfloatより速い場合がある
       6. 7.3.6 反復計算を閉形式で置き換える
    4. 7.4 制御フローイディオムを最適化する
       1. 7.4.1 if-else if-elseよりもswitchを使う
       2. 7.4.2 switchやifの代わりに仮想関数を使う
       3. 7.4.3 コストなしの例外処理を使う
    5. 7.5 まとめ
13. 8章 優れたライブラリを使う
    1. 8.1 標準ライブラリ利用を最適化する
       1. 8.1.1 C++標準ライブラリの哲学
       2. 8.1.2 C++標準ライブラリを使うときの問題
    2. 8.2 既存ライブラリを最適化する
       1. 8.2.1 変更をできる限り減らす
       2. 8.2.2 機能を変更するよりは関数を追加する
    3. 8.3 最適化したライブラリの設計
       1. 8.3.1 急いでコード化し、ゆっくり後悔せよ
       2. 8.3.2 節約はライブラリ設計での美徳
       3. 8.3.3 メモリ割り当て決定をライブラリの外で行う
       4. 8.3.4 迷ったらライブラリのコードは速度優先にする
       5. 8.3.5 関数はフレームワークより最適化しやすい
       6. 8.3.6 継承階層を平坦にする
       7. 8.3.7 呼び出し連鎖を平坦にする
       8. 8.3.8 設計の層を平坦にする
       9. 8.3.9 動的参照を止める
       10. 8.3.10 「全能関数」に注意
    4. 8.4 まとめ
14. 9章 探索と整列を最適化する
    1. 9.1 std::mapとstd::stringを使ったキー・値テーブル
    2. 9.2 探索性能を改善するツールキット
       1. 9.2.1 ベースライン測定を行う
       2. 9.2.2 最適化する作業を仕分ける
       3. 9.2.3 最適化する作業を分解する
       4. 9.2.4 アルゴリズムとデータ構造を変更または置き換える
       5. 9.2.5 カスタム抽象化に最適化プロセスを使う
    3. 9.3 std::mapを使って探索を最適化する
       1. 9.3.1 std::mapで固定サイズ文字配列キーを使う
       2. 9.3.2 std::mapでCスタイル文字列キーを使う
       3. 9.3.3 キーが値の中にあればマップの従兄弟のstd::setを使う
    4. 9.4 ヘッダを使って探索を最適化する
       1. 9.4.1 シーケンスコンテナでキー・値テーブルを探索する
       2. 9.4.2 std::find()：名前は明らか、O(n)時間コスト
       3. 9.4.3 std::binary_search()は値を返さない
       4. 9.4.4 std::equal_range()を使った二分探索
       5. 9.4.5 std::lower_bound()を使った二分探索
       6. 9.4.6 自前コードで二分探索
       7. 9.4.7 strcmp()を使った自前コードで二分探索
    5. 9.5 キー・値ハッシュテーブルで探索を最適化する
       1. 9.5.1 std::unordered_mapでハッシュする
       2. 9.5.2 固定文字配列キーでハッシュする
       3. 9.5.3 ナル終端文字列キーでハッシュする
       4. 9.5.4 カスタムハッシュテーブルでハッシュする
    6. 9.6 ステパノフの抽象化ペナルティ
    7. 9.7 C++標準ライブラリを使って整列を最適化する
    8. 9.8 まとめ
15. 10章 データ構造を最適化する
    1. 10.1 標準ライブラリコンテナをよく知る
       1. 10.1.1 シーケンスコンテナ
       2. 10.1.2 連想コンテナ
       3. 10.1.3 標準ライブラリコンテナで実験する
    2. 10.2 std::vectorとstd::string
       1. 10.2.1 再割り当ての性能結果
       2. 10.2.2 std::vectorでの挿入削除
       3. 10.2.3 std::vectorでのイテレーション
       4. 10.2.4 std::vectorを整列する
       5. 10.2.5 std::vectorで探索する
    3. 10.3 std::deque
       1. 10.3.1 std::dequeでの挿入削除
       2. 10.3.2 std::dequeでのイテレーション
       3. 10.3.3 std::dequeを整列する
       4. 10.3.4 std::dequeで探索する
    4. 10.4 std::list
       1. 10.4.1 std::listでの挿入削除
       2. 10.4.2 std::listでのイテレーション
       3. 10.4.3 std::listを整列する
       4. 10.4.4 std::listで探索する
    5. 10.5 std::forward_list
       1. 10.5.1 std::forward_listでの挿入削除
       2. 10.5.2 std::forward_listでのイテレーション
       3. 10.5.3 std::forward_listを整列する
       4. 10.5.4 std::forward_listで探索する
    6. 10.6 std::mapとstd::multimap
       1. 10.6.1 std::mapでの挿入削除
       2. 10.6.2 std::mapでイテレーション
       3. 10.6.3 std::mapを整列する
       4. 10.6.4 std::mapで探索する
    7. 10.7 std::setとstd::multiset
    8. 10.8 std::unordered_mapとstd::unordered_multimap
       1. 10.8.1 std::unordered_mapでの挿入削除
       2. 10.8.2 std::unordered_mapでのイテレーション
       3. 10.8.3 std::unordered_mapで探索する
    9. 10.9 他のデータ構造
    10. 10.10 まとめ
16. 11章 I/Oを最適化する
    1. 11.1 ファイル読み込みのためのレシピ
       1. 11.1.1 節約的関数シグネチャを作る
       2. 11.1.2 呼び出し連鎖を縮める
       3. 11.1.3 再割り当てを減らす
       4. 11.1.4 より大きな単位で― より大きな入力バッファを使う
       5. 11.1.5 より大きな単位にする― 一度に1行読み込む
       6. 11.1.6 呼び出し連鎖を再度縮める
       7. 11.1.7 役に立たない事柄
    2. 11.2 ファイル書き出し
    3. 11.3 std::cinから読み込みstd::coutに書き出す
    4. 11.4 まとめ
17. 12章 並行性を最適化する
    1. 12.1 C++並行機能の復習
       1. 12.1.1 さまざまな並行処理機能の紹介
       2. 12.1.2 並行プログラムのインタリーブ実行
       3. 12.1.3 逐次一貫性
       4. 12.1.4 競合
       5. 12.1.5 同期
       6. 12.1.6 アトミック性
    2. 12.2 C++並行処理機能の復習
       1. 12.2.1 スレッド
       2. 12.2.2 promiseとfuture
       3. 12.2.3 非同期タスク
       4. 12.2.4 mutex
       5. 12.2.5 ロック
       6. 12.2.6 条件変数
       7. 12.2.7 共有変数のアトミック演算
       8. 12.2.8 今後予定されている将来のC++並行処理機能
    3. 12.3 C++スレッドプログラムの最適化
       1. 12.3.1 std::threadよりstd::asyncを使う
       2. 12.3.2 コアと同じ個数の実行可能スレッドを作る
       3. 12.3.3 タスクキューとスレッドプールを実装する
       4. 12.3.4 別のスレッドでI/Oを実行する
       5. 12.3.5 同期なしのプログラム
       6. 12.3.6 起動とシャットダウンからコードを除く
    4. 12.4 同期をより効率的に行う
       1. 12.4.1 クリティカルセクションの範囲を減らす
       2. 12.4.2 並行スレッドの個数を限定する
       3. 12.4.3 途方もない大群を避ける
       4. 12.4.4 ロック護送列を避ける
       5. 12.4.5 競合を減らす
       6. 12.4.6 単一コアシステムでビジーウェイトしない
       7. 12.4.7 永遠に待ってはならない
       8. 12.4.8 自分でmutexを作ると非効率
       9. 12.4.9 生産者出力キューの長さを制限する
    5. 12.5 並行処理ライブラリ
    6. 12.6 まとめ
18. 13章 メモリ管理を最適化する
    1. 13.1 C++メモリ管理APIの復習
       1. 13.1.1 動的変数のライフサイクル
       2. 13.1.2 メモリ管理関数がメモリを割り当てて解放する
       3. 13.1.3 new式で動的変数を作る
       4. 13.1.4 delete式で動的変数を削除する
       5. 13.1.5 明示的デストラクタ呼び出しは動的変数を破壊する
    2. 13.2 高性能メモリマネージャ
    3. 13.3 クラス専用メモリマネージャを提供する
       1. 13.3.1 固定サイズブロックメモリマネージャ
       2. 13.3.2 ブロックアリーナ
       3. 13.3.3 クラス専用operator new()を追加する
       4. 13.3.4 固定ブロックメモリマネージャの性能
       5. 13.3.5 さまざまな固定ブロックメモリマネージャ
       6. 13.3.6 非スレッドセーフメモリマネージャは効率的だ
    4. 13.4 カスタムな標準ライブラリアロケータを提供する
       1. 13.4.1 極小C++11アロケータ
       2. 13.4.2 C++98アロケータの追加定義
       3. 13.4.3 固定ブロックアロケータ
       4. 13.4.4 文字列の固定ブロックアロケータ
    5. 13.5 まとめ
19. 索 引 (1/4)
20. 索 引 (2/4)
21. 索 引 (3/4)
22. 索 引 (4/4)