[Boost] static_vectorとsmall_vector

はじめに

数値計算において、要素数が小さい配列を作って計算に利用することがよくあります。
この小さい配列を作成するのにstd::vectorを使うのは、

• ヒープに領域を確保するためスタックを利用するstd::arrayよりも時間がかかる
• 領域の管理自体にメモリが必要である（イテレータ２つ＋キャパシティ）

といった理由で、特に多数の小さな配列を取り扱う場合は非効率的です。

大抵の場合は、ソルバーが数値計算のボトルネックなので気にする必要はありません。
しかし、プログラムをプロファイルした結果、ボトルネックの一つとしてこの小さな配列の生成があることがわかった場合、boost::container::small_vectorやboost::container::static_vectorを使ってみるとパフォーマンスが改善されるかもしれません。

---

注：ボトルネックになることがわかっていない限り、始めから使うのはやめましょう。

8.時期尚早な最適化を行わない
[C++ Coding Standards, Herb Sutter and Andrei Alexandrescu]

boost::container::small_vectorやboost::container::static_vectorは実装が複雑なため、下のようにstd::vectorに比べてデバッグ時の表示が複雑になり、デバッグが難しくなります。（ここではgdb debuggerを使って表示したときの例を示しています。）

boost::container::static_vector<int, 4>の場合：

$1 = {<boost::container::vector<int, boost::container::container_detail::static_storage_allocator<int, 4ul> >> = {m_holder = {<boost::container::container_detail::static_storage_allocator<int, 4ul>> = {
        static internal_capacity = <optimized out>, storage = {dummy = {dummy = "\000\000\000\000\001\000\000\000\002\000\000\000\003\000\000"}}}, m_size = 4}}, static static_capacity = <optimized out>}

std::vector<int>の場合：

$1 = std::vector of length 4, capacity 4 = {0, 1, 2, 3}

boost::container::static_vector

std::arrayと同じくスタックに領域を確保しますが、std::arrayと異なりstd::vectorと同じように使うことができます。
（最大要素数に達するまではpush_backを行うことができるなど）

# include <boost/container/static_vector.hpp>
/* ... */
using boost::container::static_vector;
constexpr auto buff_size = 8; // 最大要素数
static_vector<int, buff_size> v;
for (int i = 0; i < buff_size; ++i) {
  // 最大要素数に達するまではpush_backが可能
  // 最大要素数を超えてpush_backするとstd::bad_allocがthrowされる
  v.push_back(i);
}

std::vectorと同様、最大要素数はcapacity()、現在の要素数はsize()を使って得ることができます。

boost::container::small_vector

boost::container::small_vectorは、LLVMのSmallVectorにインスパイアされて作られたsmall-size optimized vectorです。
LLVMのSmallVectorについて知りたければ、Chandler Carruthの講演を見るといいでしょう。

CppCon 2016: Chandler Carruth “High Performance Code 201: Hybrid Data Structures"

boost::container::small_vectorはstd::vectorと全く同じように使うことができます。
ただその内部で、指定した要素数に達するまではスタックに保存し、それを超えるとヒープに領域を確保するようになっています。

# include <boost/container/small_vector.hpp>
/* ... */
using boost::container::small_vector;
constexpr auto buff_size = 8;
constexpr auto size = 10;
small_vector<int, buff_size> v;
for (int i = 0; i < size; ++i) {
  // 要素数がbuff_sizeを超えるまではスタックに保存する。
  // 要素数がbuff_sizeを超えるとヒープに領域を確保して保存する。
  v.push_back(i);
}

各型のデータサイズ

私のPCで各型の（ヒープを除く）データサイズをsizeofを使って調べて見ました。

# include <iostream>
# include <array>
# include <vector>
# include <boost/container/static_vector.hpp>
# include <boost/container/small_vector.hpp>

int main() {
  using std::array;
  using std::vector;
  using boost::container::static_vector;
  using boost::container::small_vector;

  constexpr auto buff_size = 4;
  using array_t = array<int, buff_size>;
  using vector_t = vector<int>;
  using static_vector_t = static_vector<int, buff_size>;
  using small_vector_t = small_vector<int, buff_size>;

  std::cout << "buff_size              : " << buff_size               << "\n"
            << "sizeof(int)            : " << sizeof(int)             << "\n"
            << "sizeof(array_t)        : " << sizeof(array_t)         << "\n"
            << "sizeof(static_vector_t): " << sizeof(static_vector_t) << "\n"
            << "sizeof(vector_t)       : " << sizeof(vector_t)        << "\n"
            << "sizeof(small_vector_t) : " << sizeof(small_vector_t)  << std::endl;
}

出力

buff_size              : 4
sizeof(int)            : 4
sizeof(array_t)        : 16  // int * 4
sizeof(static_vector_t): 24  // int * 4 + size_t ?
sizeof(vector_t)       : 24  // pointer * 2 + size_t ?
sizeof(small_vector_t) : 40  // int * 4 + pointer * 2 + size_t ?

static_vector/small_vectorを使ってデータを効率的に２次元配列に保存する

有限体積法や有限要素法の計算では、セル・面・節点がどのようにつながっているかというデータが必要となります。
一般的にはこのデータを二次元配列、例えばstd::vector<std::vector<int>>などに保存して使うのですが、データがメモリ上に不連続に配置されるためキャッシュミスが起きやすくなります。

そこで、一つの要素に接続する要素の最大の数Nがわかっていれば、二次元配列をstd::vector<boost::container::static_vector<int, N>>として定義することで、データをメモリ上に連続に配置することができ、キャッシュミスが起きにくくなります。
もし一つの要素に接続する要素の最大の数がわからなければ、大部分の要素をカバーできる適当な数Nを使い、二次元配列をstd::vector<boost::container::small_vector<int, N>>として定義すれば、ほとんどのデータがメモリ上に連続に配置されます。