folly::small_vector — inline storage 분석

1
folly::small_vector<int, 4> v;   // 4개까지 inline
2
v.push_back(1); v.push_back(2);  // heap 할당 0
3
v.resize(10);                    // 이때 heap으로 spill

1
#include <folly/small_vector.h>
2

3
// 기본 — N개까지 inline
4
folly::small_vector<int, 8> v;
5

6
// pretty-print용 SmallVecPolicy
7
using Names = folly::small_vector<std::string, 4,
8
                                  folly::small_vector_policy::policy_in_situ_only<true>>;
9
// in_situ_only=true → heap 사용 불가, capacity 초과 시 throw
10

11
// LLVM 스타일 — heap 폴백 허용
12
folly::small_vector<int, 16> tokens;
13

14
// 사용
15
tokens.push_back(42);
16
tokens.emplace_back(7);
17
for (auto x : tokens) Use(x);

1
// 약식
2
template <typename T, size_t N>
3
class small_vector {
4
  union Storage {
5
    // inline (N개 만큼)
6
    alignas(T) std::byte inlineBuf[sizeof(T) * N];
7
    // 또는 heap
8
    struct {
9
      T*       data_;
10
      size_t   capacity_;
11
    } heap;
12
  } u_;
13

14
  size_t   size_ : sizeof(size_t)*8 - 1;
15
  size_t   isHeap_ : 1;
16
};

1
// 약식
2
void push_back(T v) {
3
  if (size_ < capacity()) {
4
    new (data() + size_) T(std::move(v));
5
    ++size_;
6
  } else {
7
    growAndPush(std::move(v));
8
  }
9
}
10

11
void growAndPush(T v) {
12
  size_t new_cap = capacity() * 2;
13
  T* new_data = static_cast<T*>(malloc(new_cap * sizeof(T)));
14
  // 모든 기존 원소 move
15
  for (size_t i = 0; i < size_; ++i) {
16
    new (new_data + i) T(std::move(data()[i]));
17
    data()[i].~T();
18
  }
19
  if (isHeap_) free(u_.heap.data_);
20
  u_.heap.data_ = new_data;
21
  u_.heap.capacity_ = new_cap;
22
  isHeap_ = 1;
23
  // push
24
  new (new_data + size_) T(std::move(v));
25
  ++size_;
26
}

1
if constexpr (folly::IsRelocatable<T>::value) {
2
  std::memcpy(new_data, old_data, size_ * sizeof(T));
3
  // destructor 호출 안 함 (relocate 의미)
4
} else {
5
  // move + destruct
6
}

1
// LLVM SmallVector
2
llvm::SmallVector<int, 4> llv;
3

4
// boost
5
boost::container::small_vector<int, 4> bv;
6
boost::container::static_vector<int, 4> sv;  // heap 금지
7

8
// abseil
9
absl::InlinedVector<int, 4> iv;
10

11
// std (C++23?)
12
// std::inplace_vector<T, N> — heap 없음, in-situ만

1
// Bad — N이 너무 큼
2
folly::small_vector<int, 1024> v;   // sizeof = 4KB
3
// stack 폭발, 함수 인자 전달 비용 증가
4

5
// Good — 일반적 사용 size에 맞춤
6
folly::small_vector<int, 8> v;

1
// Good — 명시적 reserve로 inline 활용
2
folly::small_vector<std::string, 4> args;
3
args.reserve(args.size() + N);   // N≤4면 여전히 inline

1
// 주의 — pointer/iterator 안정성
2
folly::small_vector<int, 4> v;
3
auto* p = &v[0];                 // inline buffer 안 포인터
4
v.push_back(...); v.push_back(...); ...
5
// inline → heap 전환 시 데이터 옮김, p invalid