オライリージャパン
売り上げランキング: 174,171
Optimized C++ を読んだメモ。途中で RubyKaigi の発表準備などがあって読むのを中断してしまっていたが再開。他にも読みたい本が出てきたので8章以降はさらっと流し読みして読んだことにしてしまった。
目次
Oreilly のサイト からどうぞ
2章 最適化に影響するマシンの振る舞い
メモリは遅い
- + や * の数よりも、変数の load/store の方が遅いので、そちらの回数の方が重要なことが多い
- メモリはバイト単位でアクセスされているのではない. 64 bytes をまとめてフェッチしたり
2.4 まとめ
- メモリへのアクセスが、プロセッサの他のコストを上回る。
- アンアラインドアクセスはすべてのバイトが同じ語にある場合の2倍時間がかかる。
- 頻繁に使われるメモリ位置はあまり使われない位置よりも高速にアクセスされる。
- 連続したメモリは離れた場所のメモリより速くアクセスされる。
- キャッシュのために、全体プログラム稼働時の関数の実行が、テスト環境時での実行よりも遅 くなる。
- 実行スレッド間で共有されるデータへのアクセスは、非共有データへのよりもはるかに遅い。
- 計算は決定よりも速い。
- あらゆるプログラムが他のプログラムとコンピュータ資源を争奪している。
- プログラムが起動時に、あるいは、高負荷で実行しなければならないなら、性能は負荷をかけ て測らねばならない。
- あらゆる代入、関数引数初期化、関数の戻りにおいて、大量のコードを隠蔽する関数であるコ ンストラクタが呼び出される。 • 文によっては、大量の計算を隠蔽する。文の形式はいかに高価かを示さない。 • 同期コードは、並行スレッドがデータを共有するときに、利用可能な並行性の量を減らす。
3章 性能を測定する
- 例えば、プログラムの実行に100秒かかるとしよう。プログラムが1つの関数fの呼び出しで80秒かかっていることを見つけたとする。f のコードを書き直して30%速くしたとする。全体の実行時間はどれだけ改善するだろうか。
- => 関数1つを30%改善して、全体のプログラムの実行時間が22%改善する。
C++ の文にかかるコストを大雑把に見積もるには、メモリの読み書きの個数を数えるのが役立つ。
本質的な足し算そのものより、メモリアクセスの方が圧倒的に遅い。
例えば、文 a = b + c; においてa、b、cを整数とすると、位置bとcでメモリからの読み込み、位置aで和のメモリへの書き込みがあるはずだ。この文のコストは従って3メモリアクセスとなる。
ベンチで同じ関数を回すと、キャッシュに載って速くなる
実用ではそんな使い方はされないのでウソの計測になりうる
3.7 まとめ
- 性能は計測されねばならない。
- テスト可能な予測をして、その予測をメモしておく。
- コード変更を記録する。
- 実験をすべて文書化しておけば、すぐに繰り返すことができる。
- プログラムの実行時間の90%は、コードの10%で行われる。
- 測定は真度が高く、かつ精度が高くなければならない。
- 分解能は正確度とは違う。
- Windowsでは、関数clock()が信頼できる1ミリ秒計測を提供する。Windows8以降では、 関数GetSystemTimePreciseAsFileTime() がマイクロ秒以下の tick を提供する。
- 大幅な性能向上だけを受け入れることで、開発者は方法論について余計な心配をしなくて済 む。
- C++の文にかかる時間を見積もるには、その文で実行されるメモリ読み書きの回数を数える。
4章 文字列
4.5 まとめ
- 文字列は動的に割り当てられ、式では値として振る舞い、実装には多くのコピーが必要なので、コストがかさむ。
- 文字列を値ではなくオブジェクトとして扱うと、割り当てとコピーの頻度が減る。
- 文字列のスペースを確保しておくと、割り当てのオーバーヘッドが減らせる。
- 文字列へのconst参照を関数に渡すと、値渡しとほとんど同じだが、より効率的になる。
- 実引数のストレージを参照として再利用する方法で関数から結果文字列を返すようにすると、新たなストレージを割り当てるより効率的になる。
- たまにしか割り当てオーバーヘッドをなくさないのも最適化である。
- 異なるアルゴリズムのほうが最適化が容易であったり、本質的により効率的なことがある。
- 標準ライブラリクラス実装は汎用的で単純だ。それは必ずしも高効率ではなく、特別な使用状 況では最適でもない
5章 アルゴリズムを最適化する
探索と整列を最適化するツールキットには次の3つだけが含まれる。
• 平均時の時間コストが劣るアルゴリズムを、より良い平均時時間コストのアルゴリズムで置き換える。
• データについての追加知識(例えば、データが通常整列しているか、ほとんど整列している) を用いて、そのような特性を備えたデータで優れた最良時コストのアルゴリズムを選び、その ような特性のデータで最悪時コストのアルゴリズムを避ける。
• アルゴリズムの性能を定数倍改善するために手を加える。
ソート
- 入力データが整列済みかほとんど整列済みなら、普通は受け入れがたい性能の挿入ソートでも優れた O(n) 性能を示す。
- ティムソートと呼ばれる比較的最近登場したハイブリッドソートもデータが整列済みかほとんど整列済みなら優れた O(n) 性能を示し、その他の場合には最適な O(n log2 n) 性能を示す。ティム ソートは Python の標準ソートだ。
- イントロソートという最近のソートは、クイックソートとヒープソートのハイブリッドだ。イン トロソートは、クイックソートから始めるが、偏った入力データのために再帰の深さが深くなりすぎるとヒープソートに切り替える。イントロソートは、最悪時にも妥当な O(n log2 n) 性能を保証 し、平均時実行時間はクイックソートの効率的実装を活用して平均コストを低減する。C++11 以降、イントロソートが std::sort() の実装として選ばれている。
- フラッシュソートと呼ばれる最近提案されたソートは、特別な確率分布を持つデータに優れた O(n) 性能を示す。フラッシュソートは基数ソートの変形だ。データが確率分布のパーセンタイルに基づいてバケツにソートされる。データが一様分布していると、フラッシュソートの単純版が実行される。
7.5 まとめ
- 文レベルの最適化は、文のコストを増大させる要因がない限り、それだけの価値があるほどの 性能改善をもたらさない。
- ループでの文のコストはループの反復回数分増大する。
- 関数での文のコストは、関数が呼び出される回数分増大する。
- 頻繁に使われるイディオムのコストは、イディオムが使われる回数分増大する。
- C++文(代入、初期化、関数引数評価)には、隠れた関数呼び出しが含まれるものがある。
- OSへの関数呼び出しは高価となる。
- 関数呼び出しオーバーヘッドをなくす効果的な方法は、関数をインライン展開することだ。
- 現在では、PIMPLイディオムの必要はほとんどない。現在のコンパイル時間は、PIMPLが 発明された当時の 1%まで短縮されている。
- double算術演算はfloat算術演算より高速なことが多いだろう。 <= 多いってのは嘘じゃない？????メモリサイズが倍になるしな
8章 優れたライブラリを使う
現在は、ライブラリ機能の新提案は、標準化委員会に取り上げられる前に数年間 Boost Library(http://www.boost.org)に置かれるようになっている。 <= そうなんだ
標準ライブラリは最良のネイティブ関数ほどには効率的でない。性能をギリギリまで上げるには、ネイティブ呼び出しまで踏み込んで、速度達成のために可搬性を犠牲にするしかない。
8.4 まとめ
- 関数とクラスは、別の方法では提供できないか、非常に広範囲に複数のOSで再利用されるか どちらかの理由で C++ 標準ライブラリに入れられた。
- 標準ライブラリ実装にはバグがある。 • 「標準適合実装」などは存在しない。
- 標準ライブラリは最良のネイティブ関数ほどには効率的でない。
- ライブラリを更新するときには、変更をできる限り減らす。
- インタフェースの安定性がライブラリの価値の核心だ。
- ライブラリ最適化のためにテストケースは重要だ。
- 良いライブラリ設計は、他のC++コード設計と同じだが、より大きな効果を生む。
- ほとんどの抽象化は、3層のクラス導出で十分だ。
- ほとんどの抽象化実装は、3段の入れ子関数呼び出しで十分だ。
(関数呼び出しのオーバーヘッドを減らすために構造を３層までに制限するというのは過激だなぁ)
9章 探索と整列を最適化する
std::map のキーを c str にする。とか固定長 string クラスを作ってそれにする、とか。
std::equal_range, std::lower_bound を用いた２文探索
9.8 まとめ
- C++における機能の取り合わせは、実装選択に手を加えなくても良い自動化と表現から、性能に精密な制御を加えるところまで広範囲にわたる連続性を提供している。この選択の自由度 が、C++ プログラムを性能要求に合致するよう調整可能にしている。
- ほとんどの最適化の価値があるアクティビティでは、人間がすべてしっかり覚えておけないほ ど、十分多くの部品からなる。紙のほうが記憶に適している。
- 26個のキーのテーブル探索のテストで、文字列キーのstd::unordered_mapは文字列キーの std::map より 52%しか速度は向上しなかった。ハッシュが性能の覇者だという話とは随分異 なる。驚くべき結果だ。
- ステパノフの抽象化ペナルティは、C++標準ライブラリのような高生産性ツールを使うときの税金のようなものだ。
10章 データ構造を最適化する
10.10 まとめ
- ステパノフの標準テンプレートライブラリは効率的なコンテナとアルゴリズムの最初の再利用可能ライブラリだった。
- コンテナクラスのO性能はすべてのことを示していない。コンテナによっては他より何倍も速いことがある。
- std::vectorは、挿入、削除、イテレーション、ソート演算で最速のコンテナだ。
- 整列済みstd::vectorでstd::lower_boundを使った探索は、std::mapと遜色ない。
- std::dequeはstd::listより少ししか速くない。
- std::forward_listはstd::listより速くない。
- ハッシュテーブルstd::unordered_mapはstd::mapより速いが、評判通りの桁違いの速さで はない。
- インターネットからは、標準ライブラリコンテナをシミュレートするコンテナの情報が豊富に 得られる。
11章 I/Oを最適化する
11.4 まとめ
- インターネットにある「高速」I/Oコードは、そのサイトがあなたに何を売り込もうとしてるかはともかく、必ずしも速いわけではない。
- rdbufのサイズを増やすと、ファイル読み込みで数%の性能向上になる。
- 私の最短読み込み時間は、前もってファイルサイズに割り当てた文字列バッファに読み込む std::streambuf::sgetn() によるものだ。
- std::endlは出力にフラッシュする。コンソール出力でなければ、高価だ。
- std::coutはstd::cinとstdoutに結び付けられている。結び付きを切断すると性能が向上す る。
12章 平行性を最適化する
テンプレート関数 std::async() は、スレッドのコンテキストで呼び出し可能オブジェクトを実 行するが、実装ではスレッドを再利用できる。標準は、std::async() がスレッドプールを使って 実装できると示唆している
12.6 まとめ
- マルチスレッドC++プログラムは、競合を含まなければ逐次一貫性を示す。
- 大規模で発言力のある設計コミュニティは、明示的同期と共有変数を悪いアイデアだと考えて いる。
- クリティカルセクションでのI/Oは、最適化につながらない。
- 実行可能スレッドの個数は、プロセッサコアの個数以下に抑える。
- 短いクリティカルセクションを競合する理想的なスレッドの個数は2。
13章 メモリ管理を最適化する
クラス専用カスタムメモリアロケータの勧め。固定サイズブロックメモリマネージャを自前実装して使うのはよくあるパターン。
13.5 まとめ
- 性能改善には、メモリマネージャよりももっと成果の出るところがあるかもしれない。
- デフォルトメモリマネージャを置き換えることのプログラム全体への性能改善は、複数の大規模オープンソースプログラムで無視できる程度から 30%の範囲だった。
- 同じサイズを要求するメモリマネージャは、特に書きやすく実行が効率的となる。
- 特定のクラスのインスタンスのすべての割り当て要求は、同じバイト数を要求する。
- operator new()は、クラスレベルでオーバーライドできる。
- 標準ライブラリコンテナク ス、std::list、std::map、std::multimap、std::set、 std::multiset はみな、多くの同じ節点のデータ構造を作成する。
- 標準ライブラリコンテナは、クラス専用operator new()と同様にメモリ管理をカスタム化で きる能力を備えた Allocator 引数を取る。
- カスタムメモリマネージャやアロケータを書くのは効果的だが、メモリマネージャ呼び出しを取り除く最適化には劣る。
