[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>`の場合：

```terminal:
$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>`の場合：

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


# [`boost::container::static_vector`](https://www.boost.org/doc/libs/1_67_0/doc/html/boost/container/static_vector.html)

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

```cpp
#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`](https://www.boost.org/doc/libs/1_67_0/doc/html/boost/container/small_vector.html)

`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"](https://youtu.be/vElZc6zSIXM)

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

```cpp
#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`を使って調べて見ました。

```cpp
#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>>`として定義すれば、ほとんどのデータがメモリ上に連続に配置されます。