あらまし
プロファイラとにらめっこしながら気合を入れて最適化していくと、最終的に上位に std::vector<char>::resize() が残った、という経験が度々ある。
該当ケースは大抵 std::vector<char> を一時バッファとして利用しており、頻繁に resize() が呼ばれ、サイズは数十～数百 MB 規模に及ぶ、といった感じである。std::vector の resize() は新規に追加される要素に対してはコンストラクタを呼ぶが、組み込み型の場合はゼロクリアがなされる。大きなメモリ領域へのゼロクリアは重い処理であるため、プロファイル上位に残ることになるのだが、一時バッファは基本的にゼロクリアは不要であり、純粋に時間の無駄である。この無駄をなんとかしたい。
根本的な話として、こういう状況では std::vector<char> は使うべきではないと思う。malloc() & free() を適当に wrap した簡易版 std::vector もどきを作った方がずっとマシである。とはいえ、多くの人が可変長バッファにはとりあえずで std::vector<char> を使うものだし、既存のコードがいろんなところで std::vector を前提としていて置き換えが難しい、みたいなこともよくある。
本記事はそういう状況でなんとかするためにひねり出したバッドノウハウである。
std::allocator_traits の特殊化 (機能せず)
resize() などで追加される新規オブジェクトの構築処理は std::allocator_traits::construct に委ねられている。従って、std::allocator_traits の特殊化を作って何もしない construct() を定義すればゼロクリアしない resize() が実現できる。
…はずなのだが、少なくとも MSVC の実装では組み込み型は std::allocator_traits を無視して memset() でゼロクリアするようになっているようだ。(正確には、std::is_scalar_v<T> が true の型が対象)
このおかげで char でも 1 byte 毎ではなく SIMD 命令などを用いてまとめて高速にゼロクリアしてくれるのだが、今回のケースに限ってはこれが仇となり目論見が破綻した。とはいえ、std::allocator_traits の特殊化はプロジェクト全体に効果が及んで思わぬ被害が出そうなので、どちらにせよ他の方法を取るべきな気もする。
std::allocator_traits を特殊化する場合は以下のような定義を加えることになる。(せっかく検証したのでネタ供養)
namespace std {
template<>
struct allocator_traits<allocator<Hoge>>
{
using allocator_type = allocator<Hoge>;
using value_type = typename allocator_type::value_type;
using pointer = value_type*;
using const_pointer = const value_type*;
using void_pointer = void*;
using const_void_pointer = const void*;
using size_type = size_t;
using difference_type = ptrdiff_t;
using propagate_on_container_copy_assignment = false_type;
using propagate_on_container_move_assignment = true_type;
using propagate_on_container_swap = false_type;
using is_always_equal = true_type;
template <class U> using rebind_alloc = allocator<U>;
template <class U> using rebind_traits = allocator_traits<allocator<U>>;
static pointer allocate(allocator_type& alloc, const size_type count)
{
return alloc.allocate(count);
}
static pointer allocate(allocator_type& alloc, const size_type count, const_void_pointer)
{
return alloc.allocate(count);
}
static void deallocate(allocator_type& alloc, const pointer p, const size_type size)
{
alloc.deallocate(p, size);
}
template <class T, class... Args>
static void construct(allocator_type&, T* const, Args&&...)
{
// ここにカスタム構築処理
}
template <class T>
static void destroy(allocator_type&, T* const)
{
// ここにカスタム破棄処理
}
static size_type max_size(const allocator_type&) noexcept
{
return static_cast<size_t>(-1) / sizeof(value_type);
}
static allocator_type select_on_container_copy_construction(const allocator_type& a)
{
return a;
}
};
}
std::vector のメンバを直接書き換える
reinterpret_cast とかで強引に std::vector の private なメンバ変数を書き換えてどうにかする方法。おそらく大抵の人は最初にこちらを考えるのではないかと思われる。機能はするが、著しく環境依存になってしまうのが問題。マルチプラットフォームを前提とするプロジェクトではやりたくない。
MSVC でも gcc でも以下のような実装でとりあえず動くようだ。
template<class T>
inline void UnsafeResize(std::vector<T>& dst, size_t new_size)
{
// std::vector の内部表現 (環境依存)
struct Representation
{
T* begin;
T* end;
T* capacity;
};
auto& rep = reinterpret_cast<Representation&>(dst);
size_t capacity = (rep.capacity - rep.begin) / sizeof(T);
size_t size = (rep.end - rep.begin) / sizeof(T);
if (new_size <= capacity) {
// 要求サイズが capacity 以下なので終端の変更だけで済む
rep.end = rep.begin + new_size;
}
else {
// 要求サイズが capacity 以上のとき
// allocate
size_t new_capacity = std::max(capacity * 2, new_size);
typename std::vector<T>::allocator_type alloc;
T* new_begin = alloc.allocate(new_capacity);
// 旧データを新領域に移動し、旧領域は削除
memcpy(new_begin, rep.begin, size * sizeof(T));
alloc.deallocate(rep.begin, size);
// ポインタの付け替え
rep.begin = new_begin;
rep.capacity = new_begin + new_capacity;
rep.end = new_begin + new_size;
}
}
余談だが、MSVC (2019) の std::allocator は要求サイズが 4096 byte 以上の場合は挙動が変わるようだ。実際の要求サイズより少し大きめの領域を確保し、32 byte align された場所をユーザに返すようになる。SIMD 化などの際に有利になるからだと思われる。
ユーザに返されたアドレスの一個前、((void*)ptr)[-1] の部分にはポインタが格納されており、このポインタがその領域の本当の先頭 (= operator new で返されたアドレス) を指している。
proxy 型を身代わりにする
コンストラクタで何もしない型の std::vector の場合、reize() 内の初期化処理も行われない。この特性を利用して proxy 型への std::vector へのキャストで初期化を抑止するという方法。
こちらも大概ヒドいが、前述の方法よりは環境の変化に強いはずで、最終的に採用した方法はこちらとなった。
注意すべき点として、ユーザー定義型は resize() 時に memcpy() による高速なコピーが行われない。
std::allocator_traits の項で軽く触れたが、組み込み型の初期化や移動は memset() や memcpy() で高速に行う最適化が入っている。しかし、ユーザー定義型にこれが当てはまらないため、わざわざ 1 byte 毎にコピーするような遅い処理になってしまう。このままでは頻繁に realloc が発生する場合に逆に遅くなってしまうため、realloc 時には自力で memcpy() する処理も入れる。
また、最適化が有効でないとコンストラクタ呼び出しが除去されないため、通常の resize() よりもずっと遅くなってしまう。デバッグビルドのときは通常の resize() を呼ぶようにした方がいいと思われる。(ビルドオプションで挙動が変わるのは危うさもあるが…)
template <class T>
inline void DirtyResize(std::vector<T>& dst, size_t new_size)
{
# ifdef _DEBUG
dst.resize(new_size);
# else
struct Proxy
{
T value;
Proxy() {} // 初期化を抑止
};
static_assert(sizeof(T) == sizeof(Proxy));
if (new_size <= dst.capacity()) {
// 要求サイズが capacity 以下なので終端の変更だけで済む
reinterpret_cast<std::vector<Proxy>&>(dst).resize(new_size);
}
else {
// Proxy は memcpy() されないため、resize() 内で realloc が発生した場合遅くなる。
// 自力で memcpy() することで対処する。
std::vector<T> tmp;
size_t new_capacity = std::max<size_t>(dst.capacity() * 2, new_size);
tmp.reserve(new_capacity);
reinterpret_cast<std::vector<Proxy>&>(tmp).resize(new_size);
memcpy(tmp.data(), dst.data(), sizeof(T) * dst.size());
dst.swap(tmp);
}
# endif
}
結果
それぞれの方法で 1MB, 2MB, ..., 127MB と resize して時間を計測したところ、こうなった。
(ソースはこちら)
// MSVC (私の手元の環境)
std::vector::resize(): 113.97ms
UnsafeResize(): 41.84ms
DirtyResize(): 41.48ms
// gcc (Coliru)
std::vector::resize(): 352.51ms
UnsafeResize(): 193.31ms
DirtyResize(): 171.95ms
このケースでは allocate 回数は少ないため、差はほぼゼロクリアの有無によるものになる。
シビアに速度を求められる状況では無視できない差を生むことが分かると思う。
追記: std::allocator_traits の特殊化 (機能する)
その後の調査で機能する std::allocator_traits の特殊化も実現できた。が、迂遠な実装方法になる上に結局 reinterpret_cast が不可避と思われ、DirtyResize() とあまり状況は変わっていない。とはいえ、std::allocator_traits の特殊化は知っていると応用範囲が広がりそうな感じはある。
実装の詳細はこちらのコメントを参照。
注意すべきなのは、allocator_traits の construct() はデフォルトのコンストラクトだけでなく、コピーや move や emplace によるコンストラクトも委ねられているということ。このため、何もしない construct() があると realloc の際の移動すら何もしなくなり、自力でケアする必要が出てくる。