[Memory 04] 컨테이너 비용 모델

컨테이너 비용 모델이란 STL 컨테이너가 삽입·순회·조회 과정에서 실제로 소비하는 자원을 할당 횟수, 요소당 메모리 오버헤드, 이동·복사 비용이라는 세 축으로 분해해 예측하는 틀을 말합니다. Big-O 표기는 “몇 단계가 걸리는가"만 말해 줄 뿐, “그 한 단계가 malloc을 부르는가”, “노드 하나에 포인터가 몇 개 붙는가"는 알려주지 않습니다. 핫패스에서 지연이 새는 지점은 대개 이 세 축 중 하나이므로, 컨테이너를 고르기 전에 이 틀로 먼저 값을 매겨 보는 것이 이 트랙의 출발점입니다.

이 장을 읽기 전에

완전한 초보자? 이 장은 이 트랙 인트로와 15장: 메모리·수명·캐시 라인 직관에서 잡은 “힙 할당은 공짜가 아니다"라는 직관을 전제로 합니다. std::vector·std::map·std::unordered_map을 사용해 본 경험과 Big-O 표기만 알면 충분합니다. Tr.02의 STL 컨테이너 비용에서 다룬 메모리 레이아웃·캐시 효율·복잡도 비교를 이미 읽었다면 이 장이 훨씬 빠르게 읽힙니다.

이 장의 깊이: 이 장은 기초 난이도입니다. 컨테이너별 “할당이 몇 번 일어나는가”, “요소 하나당 몇 바이트가 더 붙는가"를 정량적으로 세는 법을 다루고, 이를 근거로 컨테이너를 고르는 판단 기준까지 정리합니다. 다루지 않는 것: 캐시 라인·접근 패턴에 따른 지연 차이(Tr.02 STL 컨테이너 비용, 이 트랙 06장: 캐시 친화적 접근 패턴), 할당 자체를 없애는 풀·아레나 설계(02장)와 커스텀 할당자 구현(03장), std::pmr 적용(04장), 구조체 패딩·정렬(07장)입니다.

당신의 수준에 맞는 경로

수준	읽을 부분	핵심 목표
초보자	“비용 모델이라는 관점” ~ “노드 기반 컨테이너의 오버헤드”	할당 횟수·요소당 오버헤드·이동 비용 세 축을 구분해 이해
중급자	“할당 횟수를 직접 세어보기” ~ “판단 기준”	카운팅 할당자로 실측하고 선택 기준에 적용
전문가	“비판적 시각”	구현체별 차이와 이 모델의 예측 한계를 판단

비용 모델이라는 관점 (배경)

C++ 표준(ISO/IEC 14882, [container.requirements] 절)은 vector::push_back이 **상환 상수 시간(amortized constant time)**이어야 한다고만 규정하고, 그 상수 시간을 만들어내는 **성장 인자(growth factor)**나 메모리 배치는 구현체에 맡깁니다. cppreference: std::vector도 capacity·재할당 조건을 “구현 정의"로 남겨 둔다는 점을 그대로 확인해 줍니다. 이 여백 때문에 GCC libstdc++와 Clang libc++는 2배 성장을, MSVC STL은 1.5배 성장을 채택했고, 이 차이는 지금도 유지되고 있습니다. “상환 O(1)“이라는 복잡도 보장 하나만 보면 세 구현체가 동등해 보이지만, 실제로 힙을 두드리는 횟수와 그때마다 옮기는 바이트 수는 성장 인자에 따라 갈립니다.

이 장에서 쓰는 “비용 모델"은 새로운 이론이 아니라, Tarjan·Cormen 등이 정리한 **상환 분석(amortized analysis)**의 결과를 “할당기 호출 횟수"라는 관찰 가능한 지표로 옮겨 쓰는 실용적 틀입니다. 목표는 증명이 아니라, 컨테이너를 고르기 전에 “이 선택이 힙을 몇 번, 얼마나 두드릴 것인가"를 어림잡는 것입니다.

세 가지 비용 축

컨테이너 하나를 고를 때 실제로 갈리는 비용은 다음 세 가지로 나눌 수 있습니다.

할당 횟수: N개를 담는 동안 allocate/deallocate가 몇 번 호출되는가. vector는 재할당 시점에만, list·map·set은 삽입할 때마다 호출됩니다.
요소당 메모리 오버헤드: 실제 데이터(sizeof(T)) 외에 컨테이너가 관리용으로 더 붙이는 바이트. 노드 기반 컨테이너는 포인터·색상 비트 등을 요소마다 추가로 짊어집니다.
이동·복사 비용: 재할당·리해시가 일어날 때 기존 요소를 얼마나 옮기는가. 연속 컨테이너는 재할당 때 전체를 이동하고, 노드 컨테이너는 포인터만 재연결하면 됩니다.

이 세 축은 서로 트레이드오프 관계입니다. vector는 할당 횟수가 적은 대신 재할당 시 이동 비용이 크고, list는 이동 비용이 없는 대신 할당 횟수와 요소당 오버헤드가 큽니다. 아래에서 컨테이너별로 이 세 축의 값을 구체적으로 매겨 봅니다.

vector: 성장 인자와 할당 횟수

std::vector는 용량이 부족해질 때만 재할당하므로, N번의 push_back 동안 실제 할당 횟수는 N이 아니라 성장 인자 k에 대한 log_k(N) 수준으로 줄어듭니다. 성장 인자가 2인 구현(libstdc++, libc++)에서 백만 개를 채우면 재할당은 대략 20회(⌈log₂ 1,000,000⌉)에 그치고, 성장 인자가 1.5인 MSVC STL에서는 대략 34회(⌈log₁.₅ 1,000,000⌉)로 더 잦습니다. 대신 재할당 한 번마다 옮기는 총 바이트는 등비수열을 이루어, 요소 하나가 일생 동안 옮겨지는 횟수의 기댓값은 **k/(k-1)**로 수렴합니다 — 성장 인자 2에서는 평균 2회 미만, 1.5에서는 평균 3회 미만입니다. 재할당 횟수는 성장 인자가 클수록 줄고, 이동 총량은 성장 인자가 작을수록 줄어드는 셈이라, 어느 쪽이 유리한지는 “이동 비용이 큰 타입인가"에 달려 있습니다.

1
2
3
4
5
6
N = 1,000,000개를 push_back으로 채울 때 (개념 스케치, 구현 정의)

k = 2.0 (libstdc++/libc++): 재할당 ≈ 20회, 요소당 평균 이동 ≈ 2회 미만
k = 1.5 (MSVC STL):        재할당 ≈ 34회, 요소당 평균 이동 ≈ 3회 미만

→ reserve(N)을 미리 부르면 두 구현 모두 재할당 0회, 이동 0회로 수렴

이 계산이 알려주는 실무 결론은 하나입니다. 삽입할 개수의 상한을 안다면 reserve를 부르는 순간 이 축 전체가 사라진다는 것입니다. 반대로 상한을 모른 채 반복 삽입을 오래 지속하면, 이동 비용이 큰 타입(문자열·큰 구조체)일수록 성장 인자 차이가 실측 지연 차이로 드러날 수 있으므로 대상 컴파일러·표준 라이브러리에서 직접 확인해야 합니다.

deque: 청크 단위 할당

std::deque는 요소를 하나의 연속 블록이 아니라 고정 크기 청크(chunk) 여러 개로 나누어 저장하고, 청크를 가리키는 포인터 배열(맵)을 따로 관리합니다. 앞·뒤에 요소를 추가할 때는 필요한 청크가 없을 때만 새 청크를 할당하므로, 할당 횟수는 N / (청크당 요소 수) 수준으로 vector보다는 많고 list보다는 훨씬 적습니다. 청크 자체는 재할당되지 않으므로 기존 요소가 통째로 이동하는 vector식 이동 비용은 없고, 대신 포인터 배열이 가득 차면 그 배열만 재할당됩니다.

이 구조 덕분에 deque는 앞쪽 삽입이 잦은 워크로드(예: 슬라이딩 윈도우, 링 버퍼 대용)에서 vector보다 이동 비용이 훨씬 작습니다. 다만 청크 경계를 넘나드는 순회는 포인터 배열을 한 단계 더 거치므로, 순수 순회 지연은 vector보다 불리한 경우가 많습니다 — 이 캐시 관점은 Tr.02 STL 컨테이너 비용에서 다룬 내용과 이어집니다.

노드 기반 컨테이너의 오버헤드

std::list, std::map/std::set, std::unordered_map/std::unordered_set은 요소마다 별도의 힙 노드를 할당합니다. 이 노드에는 실제 데이터 외에 컨테이너가 관리용으로 붙이는 필드가 있고, 이 필드의 크기가 곧 “요소당 메모리 오버헤드” 축입니다.

list: 노드마다 prev/next 포인터 2개(64비트에서 16바이트)를 추가로 가집니다. int 하나(4바이트, 정렬 후 8바이트)를 담는 노드라면 관리용 바이트가 실제 데이터보다 커, 오버헤드 비율이 100%를 넘는 경우가 흔합니다.
map/set: 보통 레드-블랙 트리 노드로 구현되어 색상 비트(패딩 포함 8바이트)와 부모·좌·우 포인터 3개(24바이트)를 더 가집니다. map<int, int>처럼 payload가 작을수록 오버헤드 비율이 커집니다.
unordered_map/unordered_set: 체이닝 구현(libstdc++)에서는 노드마다 캐시된 해시값과 다음 노드 포인터가 붙고, 별도로 버킷 배열(포인터 배열)이 max_load_factor를 넘을 때 vector와 비슷하게 재할당(리해시)됩니다. 이 조건은 cppreference: std::unordered_map의 max_load_factor·rehash 항목에 정리되어 있습니다. 즉 이 컨테이너는 “노드 오버헤드"와 “vector식 배열 재할당"을 동시에 갖습니다.

핵심은 payload(sizeof(T))가 작을수록 이 오버헤드가 상대적으로 커진다는 점입니다. 요소가 이미 큰 구조체(수십~수백 바이트)라면 노드 오버헤드의 비중은 무시할 만하지만, int나 작은 enum을 담는 컨테이너에서는 오버헤드가 데이터 자체보다 클 수 있습니다.

flowchart LR
  subgraph vecLayout ["vector: 연속 배열"]
    v1["payload"] --- v2["payload"] --- v3["payload"]
  end
  subgraph listLayout ["list: 노드 + 포인터 2개"]
    l1["prev|payload|next"] -->|"next"| l2["prev|payload|next"]
  end
  subgraph mapLayout ["map: 노드 + 포인터 3개 + 색상"]
    m1["color|parent|L|R|payload"] -->|"left/right"| m2["color|parent|L|R|payload"]
  end

작은 payload에서 노드 오버헤드를 없애고 싶다면, C++23 std::flat_map이나 정렬된 vector처럼 연속 메모리에 키-값을 직접 늘어놓는 대안이 있습니다. 이 대안의 삽입·삭제 트레이드오프는 Tr.02 STL 컨테이너 비용에서 이미 다뤘으므로 여기서는 “오버헤드 축을 0에 가깝게 만드는 선택지가 있다"는 사실만 짚습니다.

할당 횟수를 직접 세어보기

세 축 중 “할당 횟수"는 말로 추정하지 않고 직접 셀 수 있습니다. std::allocator가 요구하는 최소 인터페이스(allocate/deallocate, 변환 생성자)만 구현한 카운팅 할당자를 만들면, 컨테이너 코드를 한 줄도 바꾸지 않고 템플릿 인자만 바꿔 실제 allocate 호출 횟수와 총 바이트를 셀 수 있습니다. 이 패턴은 표준이 정의하는 AllocatorAwareContainer 요구사항을 그대로 활용합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <atomic>
#include <cstddef>
#include <iostream>
#include <list>
#include <map>
#include <unordered_map>
#include <vector>

inline std::atomic<size_t> g_alloc_calls{0};
inline std::atomic<size_t> g_alloc_bytes{0};

template <typename T>
struct CountingAllocator {
  using value_type = T;
  CountingAllocator() = default;
  template <typename U>
  CountingAllocator(const CountingAllocator<U>&) {}

  T* allocate(std::size_t n) {
    g_alloc_calls.fetch_add(1, std::memory_order_relaxed);
    g_alloc_bytes.fetch_add(n * sizeof(T), std::memory_order_relaxed);
    return static_cast<T*>(::operator new(n * sizeof(T)));
  }
  void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }
};
template <typename T, typename U>
bool operator==(const CountingAllocator<T>&, const CountingAllocator<U>&) { return true; }
template <typename T, typename U>
bool operator!=(const CountingAllocator<T>&, const CountingAllocator<U>&) { return false; }

template <typename Fn>
void measure(const char* label, Fn fn) {
  g_alloc_calls = 0;
  g_alloc_bytes = 0;
  fn();
  std::cout << label << ": allocate() " << g_alloc_calls
            << "회, 총 " << g_alloc_bytes << " 바이트\n";
}

int main() {
  constexpr int N = 100000;

  measure("vector (reserve 없음)", [] {
    std::vector<int, CountingAllocator<int>> v;
    for (int i = 0; i < N; ++i) v.push_back(i);
  });

  measure("vector (reserve 있음)", [] {
    std::vector<int, CountingAllocator<int>> v;
    v.reserve(N);
    for (int i = 0; i < N; ++i) v.push_back(i);
  });

  measure("list", [] {
    std::list<int, CountingAllocator<int>> l;
    for (int i = 0; i < N; ++i) l.push_back(i);
  });

  measure("map", [] {
    std::map<int, int, std::less<int>,
             CountingAllocator<std::pair<const int, int>>> m;
    for (int i = 0; i < N; ++i) m.emplace(i, i);
  });

  measure("unordered_map (reserve 없음)", [] {
    std::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
                        CountingAllocator<std::pair<const int, int>>> um;
    for (int i = 0; i < N; ++i) um.emplace(i, i);
  });
}

g++ -O2 -std=c++17 counting_alloc.cpp -o counting_alloc로 빌드해 실행하면(x86-64, GCC 13 기준), vector (reserve 없음)은 성장 인자에 따른 log 수준의 호출 횟수를, vector (reserve 있음)은 정확히 1회를, list·map·unordered_map은 N에 근접하거나(map, 각 삽입마다 노드 1개) N보다 조금 많은(unordered_map, 노드 할당 + 리해시) 호출 횟수를 출력하는 것을 직접 확인할 수 있습니다. 이 카운팅 할당자는 실제 operator new/operator delete를 그대로 호출하므로 성능 오버헤드는 원자적 카운터 증가뿐이며, 측정 결과는 표준 라이브러리 구현·컴파일러 버전에 따라 달라질 수 있으므로 배포 환경에서 재현하는 것이 안전합니다.

흔한 오개념

**“reserve만 하면 vector가 항상 이긴다”**는 절반만 맞습니다. reserve는 삽입할 개수의 상한을 미리 알 때만 효과가 있고, 상한을 몰라 과대 추정하면 메모리를 낭비하며, 과소 추정하면 재할당이 그대로 남습니다. 상한을 모르는 채로 반복해서 크기가 바뀌는 컬렉션이라면 애초에 다른 축(청크 기반 deque, 풀 할당)을 검토해야 합니다.

**“노드 기반 컨테이너는 무조건 느리다”**도 과장입니다. 요소가 크고 이동 비용이 비싼 타입(이동 생성자가 없거나 비싸게 구현된 타입)이라면, vector의 재할당이 매번 전체 데이터를 복사하는 것보다 노드 컨테이너가 포인터만 재연결하는 편이 총 비용이 더 낮을 수 있습니다. “캐시가 이긴다"는 일반론은 payload가 작고 이동이 저렴할 때 성립하는 경향이지, 모든 타입에 대한 절대 법칙이 아닙니다.

**“Big-O가 같으면 비용도 같다”**는 이 장 전체가 반박하는 오개념입니다. vector와 deque의 뒤쪽 삽입은 둘 다 상환 O(1)이지만, 실제 할당 횟수·이동 총량·캐시 동작은 다릅니다. 복잡도는 “몇 단계인가"만 말하고, “그 단계가 얼마나 무거운가"는 이 장의 세 축으로 따로 확인해야 합니다.

판단 기준

flowchart TD
  q1["삽입/삭제가
핫패스에서 빈번한가?"]
  q2["요소 크기가 크거나
이동 비용이 큰가?"]
  q3["키 탐색이
주 용도인가?"]
  q4["정렬 순서가
필요한가?"]
  rVector["vector + reserve"]
  rNode["list 등 노드 컨테이너
(포인터만 재연결)"]
  rSorted["정렬 vector / flat_map
(Tr.02 04장)"]
  rHash["unordered_map + reserve"]
  rTree["map / set"]

  q1 -->|"아니오"| q3
  q1 -->|"예"| q2
  q2 -->|"예"| rNode
  q2 -->|"아니오"| rVector
  q3 -->|"예"| q4
  q3 -->|"아니오"| rVector
  q4 -->|"아니오"| rHash
  q4 -->|"예, N 작음"| rSorted
  q4 -->|"예, N 큼/삽입 빈번"| rTree

상황	권장	이 장 기준 근거
삽입 개수 상한을 안다	vector + reserve(N)	할당 횟수 1회, 이동 비용 0
상한 모른 채 장기 누적	deque 또는 풀 할당(02장) 검토	청크 단위 할당으로 이동 비용 분산
payload가 작고(수 바이트) 이동이 저렴	vector/정렬 vector	노드 오버헤드 비율이 payload보다 커지는 상황 회피
payload가 크고 이동이 비쌈	list/map 등 노드 컨테이너	재할당 시 대량 이동보다 포인터 재연결이 저렴
키 탐색 위주, 순서 불필요	unordered_map + reserve	리해시 횟수를 미리 줄여 축 두 개(할당·이동) 동시 절감
할당 횟수 자체가 병목으로 측정됨	02장 풀/아레나, 04장 pmr	컨테이너 선택이 아니라 할당 경로 자체를 바꿔야 하는 단계

비판적 시각: 한계와 트레이드오프

이 비용 모델은 어림값이지 정밀한 예측이 아닙니다. 성장 인자·노드 레이아웃·리해시 조건은 모두 구현체(libstdc++/libc++/MSVC STL) 정의 사항이라, 이 장에서 든 log_k(N)이나 오버헤드 바이트 수는 방향성을 잡는 근사치로만 써야 합니다. 실제 malloc/free 구현(glibc malloc, jemalloc, tcmalloc — 16장에서 다룹니다)이 작은 할당을 어떻게 재사용하는지에 따라 “할당 횟수가 많다"는 사실이 실제 지연으로 얼마나 이어지는지도 달라집니다. 또한 이 장은 할당·오버헤드·이동이라는 세 축만 다루고 캐시 미스·프리페치 같은 하드웨어 단의 영향은 의도적으로 배제했으므로, 최종 판단은 반드시 이 장의 카운팅 결과와 Tr.02·이 트랙 06장의 지연 측정을 함께 봐야 신뢰할 수 있습니다.