Optimized C++ 下読みノート ¶

ここ数年 C++ の本をまったく読んでいなくて、何かリハビリになるものがないかと思って手にとった一冊。この本は自分が浦島太郎状態であることを知らせてくれた。

以下、下読みのときにとったメモを写しておく。このあと本書を熟読することがあれば、使える形のノートとして更新する。

著者:: Kurt Guntheroth
訳者:: 黒川利明
出版社:: オライリー・ジャパン
発行年:: 2017 年
ISBN:: 978-4-87311-792-8
関連 URL:: 詳細

1 章最適化とは ¶

この章は最後のまとめを一読すれば差し当たり間に合う。

2 章最適化に影響するマシンの振る舞い ¶

この章もまとめを一読しておけばよい。

3 章性能を測定する ¶

最適化の式 (p. 29) は誤植かもしれない。次の式でないと以降の説明の筋が通らない：

\[S_T = \cfrac{1}{1 - P + \cfrac{P}{S_P}}.\]
囲み記事の線形探索 vs 二分探索の話は理解できる。
最適化は収穫逓減プロセスだ。
測定時にはライブラリーのデバッグ版とリンクしないこと。適切なビルドオプションを指定する。
(C++11) std::chrono という名前空間があり、そこでは時間計測に関する機能が備わっている。

4 章文字列使用を最適化する ¶

(C++11) std::string の実装としては COW が許されていない。
ここでムーブ代入演算子の話が出てくる。
+=, reserve() の話は理解できる。
次の const & で値渡しよりも 8% 遅くなったというのは驚く。
文字列の文字にアクセスするのに、添字よりイテレーターのほうが効率的というのも意外だ。
文字列を return するよりも引数にセットするほうが効率的というのは理解できる。
const char* を採用すると明らかに速いわけだが、当然安全性とのトレードオフだ。
(C++14) std::string_view
アロケーターの話が少し出てくる。

5 章アルゴリズムを最適化する ¶

Skiena 本をアルゴリズムの教科書として推薦している。あれは面白かった。
アルゴリズムの議論なので \(O(f(n))\) 表記を多用する。
すべての探索は \(n\) が小さいならば等しい。理解できる。
ソートの話題は注意して読んだほうが良さそうだ。ツリーソート、ティムソート、イントロソートなど、初めて耳にするアルゴリズムが出てくる。
- ティムソートは Python の標準のソートだ。最良 \(O(n)\) で平均と最悪が \(O(n\log n)\) だという。
- イントロソートとはクイックソートとヒープソートのハイブリッドアルゴリズムだ。これが C++11 以降の std::sort の実装になっているらしい。
- フラッシュソートという、基数ソートの変形アルゴリズムがある。
§5.5 の最適化のパターン。小節全体の価値が高い。

6 章動的変数割り当てを最適化する ¶

(C++11) thread_local というキーワードがある。これで修飾された変数は、それが存在するスレッドに限定して一度だけ初期化される？
オブジェクトには値であるか、エンティティーであるかという意味があるとみなす。
(C+11) nullptr というキーワードがある。
std::unique_ptr<T>
動的変数の所有権を共有することは高くつく。納得できる。
std::shared_ptr<T>
std::array<T>
std::make_shared()
所有権を不必要に共有しない。
動的変数の再割り当てを減らすには reserve() のようなものを利用する。この知識は今でも有効。
ループ内で動的割り当てをしないで、外でやる。これは当然だ。
(C++11) delete キーワードをコピーコンストラクターと代入演算子の各宣言のケツに書ける。この場合、これらの宣言は public とする。
RVO
深いコピー vs 浅いコピー
§6.6 move semantics は学ぶことがたくさんある。
std::swap の考えを推し進めるとムーブの概念に至るようだ。
ムーブは値にもエンティティーにも効く。
Effective Modern C++ 推奨。これはまだ読んでいないな。
ムーブは難しいところがある。
ムーブコピーコンストラクター・代入演算子を noexcept でなければならない。
std::swap のムーブによる実装例。なるほど。
RVO と右辺値参照が干渉し合う。ここのところ難しい。

7 章ホットな文を最適化する ¶

この章は常識的なことが丁寧に述べられているように思える。

PIMPL をやめる。現代ではコンパイル時間が高速化したというのが理由。なんと……。
定数同士の演算を連結させるようにまとめることで、コンパイル時に値を評価、決定させる。
double は float より速いと考えてよい。FPU の仕組みがそのようになっている。確かに float は OpenGL のプログラムを除けば使ったことがない。

8 章優れたライブラリを使う ¶

標準ライブラリーに関する諸注意と自分でライブラリーを設計するときの助言。

とにかく平坦に設計する。
全能関数（神関数）は高価だ。
囲み記事の printf と puts の話は覚えておく。

9 章探索と整列を最適化する ¶

std::string をキーとする std::map の考察。
- (C++11) std::map の初期化構文。
- キーである文字列を工夫することで最適化できる。例えば固定長 C 形式文字列を採用するとか。
std::binary_search() は探索の成否しかわからない。
std::equal_range() の衝撃の性能。
std::lower_bound() が std::map と互角。
(C++11) std::unordered_map 系を使うときはハッシュをどうするかという問題が起こる。
std::sort() vs std::stable_sort() だが、この性能比較表は想像とかなり違う。これを見ただけでも本書を手にして良かった。

10 章データ構造を最適化する ¶

std::unordered_ 系連想コンテナーを学習する機会があれば、ここを読み返そう。

(C++11) std::unordered_ 系連想コンテナー。
囲み記事の <random> を見ると、かなり高度な乱数生成機能があるようだ。
std::list のコピーはコピー代入演算子よりも（空のオブジェクトに）末尾要素追加系のメソッドを呼び出す方が速い。なぜだ。
std::forward_list はメモリ制約がよほど厳しいプロセッサーでない限り勧められない。

11 章 I/O を最適化する ¶

語られることがあまりない API が現れて面白い。

istreambuf_iterator と rdbuf() がさっそくコード例に現れる。
tellg() と seekg() を上手く使えばストリームの「長さ」を得られるというのは盲点だった。というか Python ではよくやっているのに。
pubsetbuf() と sgetn() という、標準仕様書でしかお目にかかったことのない機能の利用例も見られる。
カスタムストリームバッファーを作ることは役に立たない。
std::endl は出力をフラッシュする。そしてフラッシュ処理は高くつく。なので、単に改行したいだけならば改行文字を出力するだけにとどめるのがよい。
最後に std::cout の性能を高めるのに std::ios_base::sync_with_stdio() が利用できることを述べている。もう少し丁寧に理解したい。

12 章並行性を最適化する ¶

Todo

並行プログラミングはまったく知らないので保留。せっかくだから今学ぼうという機運がない。

13 章メモリ管理を最適化する ¶

new, delete 全般の説明。
C 由来のメモリ管理関数。
専用マネージャー作成。固定サイズブロック。これは new と delete の提供をも含む。
標準アロケーターのカスタマイズ。
アロケーターは元々はメモリ管理だけを意味するものではなく、Windows で言えば near とか far とかの修飾を煩わせないような工夫も備えていた。
同サイズを要求するマネージャーが特に効果的だ。
良くて 30% 程度。