容量チェックをしないpush_back()
（久しぶりすぎて、はてなDiaryの使い方忘れた…）
vector<>::push_back()を使って要素を追加していく場合、push_back()の内部では必要な容量を確保する処理が行われます。
struct T { ... }; vector<T> v; for (size_t i = 0 ; i < N ; ++i) { v.push_back(T{}); // 毎回内部バッファの容量をチェックし、足りなければreallocation }
多くの要素を追加する場合には、あらかじめreserve()などで適当な容量を確保していなければ、メモリアロケーションやリアロケーションが頻発することになり、非効率的です。
v.reserve(N); for (size_t i = 0 ; i < N ; ++i) { v.push_back(T{}); // 毎回内部バッファの容量をチェックするが、足りているのでreallocationは起こらない }
ではreserve()すればまったく問題無いかというとそうでもなく、確保済みのメモリ領域に空きがあるかどうかのチェックはどうしても必要になります。
このチェック自体はそれほど重たいものではありませんが、非常に沢山の要素を追加する場合には多少の影響があるようです。
さて、おおよそどの程度の要素が追加されるかあらかじめ予想できる場合、そもそもreserve()とpush_back()のような迂遠なことをしなくても、resize()とdata()を使って値を突っ込んでいけば良いわけです。
v.resize(N); auto* p = v.data(); for (size_t i = 0 ; i < N ; ++i) { p[i] = move(T{}); // 内部バッファの容量チェックは一切行わない }
…が、どうしてもpush_back()を使いたい！というケースもあると思います。
（「ある」ということにして下さい。後が続かないので。）
そうした場合に簡単に使えるラッパーコンテナを作ってみました。
こんな感じに使えます。
#include "nochecking_sequence.hpp" using xxcxx::nochecking; vector<T> v; v.resize(N); auto w = nochecking(v); for (size_t i = 0 ; i < N ; ++i) { w.push_back(T{}); // 内部バッファの容量チェックは一切行わない }
今回は試していませんが、emplace_back()も同じ要領でできると思います。
手元のマシンで小さなオブジェクト（std::stringが１つ入っている程度）を100万回push_backして計測したところ、以下のような結果になりました。
| 方式 | 実行時間[sec] |
|---|---|
| reserve()なし | 0.085938 |
| reserve()あり | 0.054688 |
| nochecking() | 0.046875 |
…多少は効果があるようですね。
ちなみに、-O3を付けない場合はreserve()に負けてしまいます。ラッパーオブジェクトの生成に時間が掛かるようです。
さらに、push_back()の後からresize()で切り詰める*1と、なぜかreserve()版と同程度の速度まで下がります。何故だろう…。
ソースコードはこちらから参照下さい*2。
https://github.com/kentdotn/cxx-experiment/tree/master/nochecking_container
