std::vector を少し高速化する

TL;DR

std::vector 使う時は、noexcept な move constructor を実装しよう

リファクタリング中の出来事

リファクタリングしていると、なかなかに酷いコードにあたることもある。
例えば、今回はこんな感じのコードがあった。

struct HugeData {
  /* 動的でメモリを沢山確保 */
}

/* なぜか void* , なぜか固定長配列 */
void* DataArray[10000];

/* 不定期に HugeData が生み出さる */
DataArray[i] = new HugeData();

/* メモリ解放は地道になる */
for (i = 0; i < data_current_size; i++) {
  HugeData* p = (HugeData *)DataArray[i];
  delete p;
}

どこかに static おじさんが隠れてるのではと疑ってたけど、実装者が C++ を何も知らないようであった。(そして既に居なかった)

ありがたいことに、C++ には STL がある。std::vector がある。素直に書き直してみる。

struct HugeData {
  /* 動的でメモリを沢山確保 */
}

/* C++ならSTL Containerにあやかろう */
std::vector<HugeData> DataArray{};

/* HugeDataが欲しいなら、そのまま生成すればいいじゃない */
DataArray.push_back(HugeData{});

/* メモリ解放は一行で終了 */
DataArray.clear();

※正確には、std::vector::clear() はメモリ領域は開放しない。中身の destructor は呼んでくれる。

無駄なメモリ確保が走る

struct HugeData は内部データを動的確保していたため、代入処理時に問題が発生してしまうことは、容易に分かっていた。
そのため、次のように、copy constructor を追加した。

struct HugeData {
  /* copy constructor */
  HugeData(const HugeData& other) {
    /* 内部データを複製する */
    this->internal_data = clone(other.internal_data);
  }
}

HugeData a{};
HugeData b = a; /* これで代入も安全！ */

しかし、これでは std::vector::push_back() を使った際に、性能問題が発生する場合がある。

DataArray.push_back(HugeData{});
/*
  パターン1：追加する際にコピー処理
  1. HugeData x1 を作成
  2. x1 の参照が push_back() に渡される
  3. push_back() は copy_constructor(x1) から x2 をコピー生成、x2 を内部に持つ (処理が重い)
  4. ブロックを抜けるため、x1 が解放される (destructor が走る)
*/

DataArray.push_back(HugeData{});
/*
  パターン2：reallocateする際にコピー処理
  1. std::vector は、内部バッファが足りないため、新しいバッファを確保する
  2. 古いバッファの要素を、新しいバッファに移す
     この際、各要素ごとに、copy constructor が走る (最大2倍の領域が消費される)
  3. 古いバッファの各要素を解放する (destructor が走る)
*/

安全策として copy constructor を書いたのに、かえって処理が遅くなってしまった。

所有権を移譲したなら、内部データも移譲すればいいじゃない

C++11以降では、右辺値参照により所有権が移譲される際の処理を書けるようになった。
詳しくは、cpprefjp を参照で。

struct HugeData {
  /* copy constructor */
  HugeData(const HugeData& other) {
    /* 内部データを複製する */
    this->internal_data = clone(other.internal_data);
  }

  /* move constructor */
  HugeData(HugeData&& other) {
    /* 内部データを移譲する */
    this->internal_data = other.internal_data;
    other.internal_data = std::nullptr;
  }
}

DataArray.push_back(HugeData{}); /* これで、内部データの複製処理が走らない！ */

これで性能問題も解決した・・・と思ったら、どうやら、これだけでは駄目なようだ。

DataArray.push_back(HugeData{});
/*
  1. HugeData x1 を作成
  2. x1 の右辺参照が push_back() に渡される
  3. push_back() は move_constructor(x1) から x2 を移譲生成、x2 を内部に持つ (処理が軽い)
  4. ブロックを抜けるため、x1 が解放される (destructor が走る)
*/

DataArray.push_back(HugeData{});
/*
  1. std::vector は、内部バッファが足りないため、新しいバッファを確保する
  2. 古いバッファの要素を、新しいバッファに移す
     この際、各要素ごとに、copy constructor が走る (最大2倍の領域が消費される)  <-- あれ？？？
  3. 古いバッファの各要素を解放する (destructor が走る)
*/

なぜか、std::vector の reallocate の際は、move constructor ではなく copy constructor が呼ばれてしまう。

例外安全ならば、例外安全であると宣言すればいいじゃない

どうやら内部処理で複製をする際は std::move_if_noexcept (cpprefjp) を使っているようである。
move constructor に noexcept が無いため「移譲処理が例外を投げる恐れがあるなら、コピー処理にするわ」となってしまうようだ。

ということで、例外安全であることを宣言しなければいけない。

struct HugeData {
  /* copy constructor */
  HugeData(const HugeData& other) {
    /* 内部データを複製する */
    this->internal_data = clone(other.internal_data);
  }

  /* move constructor , exception safety */
  HugeData(HugeData&& other) noexcept {
    /* 内部データを移譲する */
    this->internal_data = other.internal_data;
    other.internal_data = std::nullptr;
  }
}

これで、std::vector が reallocate をする際も move constructor が使われるようになり、メモリの無駄な確保を防ぐことができるようになった。

まとめ

std::vector 使う時は、noexcept な move constructor を実装しよう

ところで、最初のリファクタリングのコードだが、突如 global おじさんが登場し、リファクタリングなんて言ってる暇がなくなってしまった。
もっとｸﾘｰﾝでｱﾝﾀﾞｰｽﾀﾝﾀﾞﾋﾞﾘｨﾃなコードを書いてほしかった・・・