C++ 컨테이너·스레드·-O2 성능 실측 비교

시리즈: C++ 강좌 6/6 (고급). 템플릿을 쓰고 STL 을 다룰 줄 아는 분(5강)이, 이제 C++ 코드를 빠르게 만들거나 여러 코어에서 돌려야 할 때를 위한 글입니다. 다 읽으면 Big-O 만이 아니라 실측으로 컨테이너를 고르고, reserve 와 짧은 문자열 최적화(SSO)로 숨은 할당을 피하고, ThreadSanitizer 로 데이터 경쟁을 잡고, 뮤텍스·원자적 연산·"공유하지 않기" 중에서 고르고, 디버그 빌드가 30 배 느린 이유를 설명할 수 있습니다.

자료구조 수업이나 정보처리기사 공부에서 "연결 리스트는 삽입이 O(1) 이라 빠르다"고 외웠을 겁니다. 틀린 말은 아니지만 요즘 CPU 에서 재 보면 이야기가 꽤 달라집니다. "원자적 연산은 락이 없으니 빠르다", "테스트는 -O0 로 충분하다"도 마찬가지입니다. 이 강의는 그런 통념을 하나씩 지금의 기계에서 확인합니다. 아래는 모두 Apple Silicon Mac(M1 Pro, 하드웨어 스레드 8 개), macOS 26, Apple clang 21.0.0 + libc++ 에서, 따로 적지 않으면 clang++ -std=c++23 -Wall -Wextra -pedantic -O2, 시드 고정·중앙값으로 실행했습니다. GCC, MSVC, Linux, Valgrind 는 돌리지 않았습니다. 다른 CPU 에서는 비율이 달라지겠지만 이유는 같습니다.

컨테이너 다섯 개, 작업 네 가지

표준 시퀀스 컨테이너와 연관 컨테이너를 int 로 쟀습니다. 키는 0..N-1 을 std::mt19937(시드 42)로 섞은 것, 조회 키는 같은 생성기의 이어지는 무작위 값이고, 시간은 모두 5 회 중앙값입니다.

template <class F> double med_ms(F f) {
    std::vector<double> t;
    for (int r = 0; r < 5; ++r) {
        auto a = clk::now(); f(); auto b = clk::now();
        t.push_back(std::chrono::duration<double, std::milli>(b - a).count());
    }
    std::sort(t.begin(), t.end());
    return t[2];
}
// e.g. med_ms([&] { sink = std::accumulate(l.begin(), l.end(), 0LL); });

숫자가 말하는 것:

• list 는 거의 전패. push_back 할 때마다 노드를 할당합니다(25 ms 대 0.7 ms). 합계는 노드가 할당 순서대로 놓여 있을 때는 vector 의 23 배 "정도"였지만, l.sort() 로 연결을 바꾼 뒤에는 같은 합계가 61 ms(다른 실행에서는 52.7 ms)가 됐습니다. 한 걸음마다 예측할 수 없는 주소로 뛰어서 캐시를 놓치기 때문입니다. 연결 리스트 글의 장단점을 숫자로 보면 이렇습니다.
• 중간 삽입은 vector 가 77 배 빠르다. list::insert 가 O(1) 이어도 위치를 찾는 건 둘 다 O(n) 이고, 노드 1 만 개를 따라가는 것은 연속된 int 40 KB 를 memmove 하는 것보다 훨씬 느립니다.
• 앞쪽 삽입만은 deque 차례: 0.04 ms 대 vector 11 ms. vector 는 매번 모든 원소를 밉니다.
• 조회는 unordered_map 이 map 보다 35 배 빠르다. map 은 레드-블랙 트리라 조회 한 번에 포인터를 20 단계쯤 따라갑니다. 정렬된 vector 의 이진 탐색은 그 중간이고, 구축 시간과 메모리에서는 이깁니다.

Java 의 ArrayList 와 LinkedList 도 같은 이야기입니다. Java 컬렉션 실측도 참고하세요.

reserve 와 숨은 할당

libc++ 의 vector 는 빈 상태에서 push_back 하면 용량을 두 배씩 늘립니다. int 를 100 만 번 push_back 하는 동안 operator new 호출 횟수를 셌습니다.

vector<int> 1M push_back, reserve=0: allocations=21 final capacity=1048576
vector<int> 1M push_back, reserve=1: allocations=1 final capacity=1000000

할당 21 번과 커지는 버퍼 복사 20 번, 대 한 번. push_back 1,000 만 번에서는 5.0~5.9 ms 가 3.1~3.3 ms 가 됐습니다(7 회 중앙값, 두 번 실행). 두 배씩 늘리기가 원래 싸기 때문에 여기서 reserve 효과는 10 배가 아니라 1.6 배입니다. 원소 이동이 비쌀 때나, 쓰지 않는 48,576 칸을 낭비하고 싶지 않을 때 더 중요합니다.

짧은 문자열 최적화: 23 번째 글자의 비용

std::string 은 짧은 문자열을 객체 안에 직접 담고 길 때만 힙을 할당합니다. 이것이 SSO(small-string optimization) 입니다. "짧다"가 몇 글자인지 할당 횟수로 확인했습니다.

std::printf("sizeof(std::string)=%zu  capacity of empty string=%zu\n",
            sizeof(std::string), std::string().capacity());
for (int len : {0, 15, 22, 23, 24, 100}) {
    n_alloc = 0;
    std::string s(len, 'x');
    std::printf("len %3d: allocations=%ld capacity=%zu\n", len, n_alloc, s.capacity());
}

sizeof(std::string)=24  capacity of empty string=22
len   0: allocations=0 capacity=22
len  15: allocations=0 capacity=22
len  22: allocations=0 capacity=22
len  23: allocations=1 capacity=24
len  24: allocations=1 capacity=31
len 100: allocations=1 capacity=103

libc++ 문자열은 24 바이트이고 22 글자까지는 힙을 건드리지 않습니다. reserve 한 vector 에 문자열 100 만 개를 만들면 22 글자는 5.9 ms, 23 글자는 17.7 ms 였습니다(워밍업 1 회 뒤 5 회 중앙값. 22 글자에서 8.2 ms 가 나온 실행도 있었음). 한 글자 차이로 비용이 3 배입니다. 4강 복사 실험에서 32 글자 문자열이 하나씩 할당한 이유도 이것입니다. libstdc++(GCC)는 32 바이트에 15 글자까지 내장합니다(여기서 돌리지 않음).

스레드, std::async, TSan 으로 잡는 데이터 경쟁

std::thread 는 함수를 새 OS 스레드에서 돌리고, 파괴하기 전에 join() 해야 합니다. C++20 std::jthread 는 소멸자에서 자동으로 join 합니다(이 libc++ 에서 동작). std::async 는 작업을 돌리고 std::future 를 주며, get() 은 결과를 기다리고 작업 안의 예외를 다시 던집니다.

auto f = std::async(std::launch::async, [&] { return sum_range(v, 0, h); });
long long right = sum_range(v, h, v.size());
long long total = f.get() + right;

async task on another thread: 1
total=32000004000000 expected=32000004000000 hw threads=8
deferred task on main thread: 1

std::launch::async 는 명시하세요. std::launch::deferred 면 작업이 get() 시점에 호출한 스레드에서 돌아서, "async 인데 병렬이 안 된다"는 단골 버그가 됩니다.

이제 동시성 수업이 꼭 처음에 다루는 버그입니다. 두 스레드가 일반 int 를 증가시킵니다.

#include <thread>
#include <cstdio>
int counter = 0;
void work(){ for(int i=0;i<100000;i++) counter++; }
int main(){
  std::thread a(work), b(work);
  a.join(); b.join();
  std::printf("counter=%d (expected 200000)\n", counter);
}

$ clang++ -std=c++23 -O0 race.cpp -o race0 && ./race0      (5 runs)
counter=102379 (expected 200000)
counter=102276 (expected 200000)
counter=118794 (expected 200000)
counter=102211 (expected 200000)
counter=101185 (expected 200000)
$ clang++ -std=c++23 -O2 race.cpp -o race2 && ./race2      (3 runs)
counter=200000 (expected 200000)

-O0 에서는 증가의 절반이 사라졌습니다. counter++ 는 읽기·더하기·쓰기 세 단계라 스레드끼리 덮어씁니다. -O2 에서는 매번 맞았습니다. 컴파일러가 루프를 counter += 100000 한 번으로 바꿔 경쟁 구간이 아주 작아졌기 때문입니다. 버그는 그대로입니다. 데이터 경쟁은 정의되지 않은 동작이고, 최적화기는 그렇게 바꿔도 됩니다(-O 에 따라 바뀌는 UB 는 C 강좌 5강에 더 있습니다). ThreadSanitizer 는 어느 쪽이든 찾아냅니다.

$ clang++ -std=c++23 -g -O1 -fsanitize=thread race.cpp -o race_tsan && ./race_tsan
==================
WARNING: ThreadSanitizer: data race (pid=42472)
  Write of size 4 at 0x000104434000 by thread T2:
    #0 work() race.cpp:4 (race_tsan:arm64+0x10000072c)
  Previous write of size 4 at 0x000104434000 by thread T1:
    #0 work() race.cpp:4 (race_tsan:arm64+0x10000072c)
  Location is global 'counter' at 0x000104434000 (race_tsan+0x100008000)
  Thread T2 (tid=26070715, running) created by main thread at:
    #4 main race.cpp:6 (race_tsan:arm64+0x100000778)
SUMMARY: ThreadSanitizer: data race race.cpp:4 in work()
==================
counter=200000 (expected 200000)
ThreadSanitizer: reported 1 warnings

Apple Silicon macOS 에서도 Apple clang 의 TSan 은 동작합니다. TSan 빌드도 합계는 맞게 찍었고, 진실을 말한 건 보고서뿐이었습니다. 이 Mac 에서 TSan 바이너리는 그 뒤 종료 코드 134 로 끝났으므로 CI 스크립트가 실패로 잡을 수 있습니다. TSan 과 ASan 은 한 빌드에 같이 못 넣습니다(clang++: error: invalid argument '-fsanitize=address' not allowed with '-fsanitize=thread'). 빌드를 두 개 만드세요.

원자적 연산, 뮤텍스, 공유하지 않기 실측

경쟁을 고치는 방법을 비교합니다. 스레드 4 개가 각각 공유 카운터에 1 을 1,000 만 번 더하고(합계 4,000 만), 5 회 중앙값. 스레드는 std::jthread 입니다.

// mutex
run_threads([&](int) { for (int i = 0; i < PER; ++i) { std::lock_guard<std::mutex> g(m); ++n; } });
// atomic
run_threads([&](int) { for (int i = 0; i < PER; ++i) n.fetch_add(1); });
run_threads([&](int) { for (int i = 0; i < PER; ++i) n.fetch_add(1, std::memory_order_relaxed); });
// count locally, publish once
run_threads([&](int) {
    long long local = 0;
    for (int i = 0; i < PER; ++i) { ++local; asm volatile("" : "+r"(local)); }  // barrier: keep the loop
    n += local; });

다섯 가지 모두 결과는 정확히 40,000,000 이었습니다. 중요한 점:

• 경쟁이 심하면 뮤텍스가 기본 원자적 연산을 이겼다. 스레드 하나면 원자적 연산이 더 빠른데(274 ms 대 353 ms), 스레드 4 개가 캐시 라인 하나를 두드리면 fetch_add 마다 그 라인이 코어 사이를 오갑니다. 뮤텍스는 한 스레드가 여러 번 연달아 더할 수 있게 해 줬습니다. "원자적 연산이 항상 빠르다"는 틀렸습니다.
• 진짜 비용은 공유 자체. 공유 카운터를 쓰는 스레드 4 개는 공유 없는 스레드 1 개보다 52~126 배 느렸습니다. 지역 변수로 세고 마지막에 한 번 더하는 방식은 단일 스레드보다 3.6 배 빨랐고, 코어를 제대로 쓴 건 이것뿐이었습니다.
• memory_order_relaxed 는 다른 데이터의 동기화에 쓰지 않는 순수한 카운터라면 맞는 선택입니다. "카운트를 본 뒤에" 다른 데이터를 읽는 스레드가 있다면 기본 순서가 필요합니다.

원칙: 스레드끼리 공유하는 것을 최대한 줄이고, 남은 것은 뮤텍스로 지키고, 원자적 연산은 플래그나 카운터 하나에 씁니다.

-O0 대 -O2: 디버그 빌드는 속도에 대해 거짓말을 한다

같은 파일을 두 번 빌드했습니다. int 1,000 만 개(rng() % 1000, 시드 42), 5 회 중앙값입니다.

교훈은 세 가지입니다. 첫째, STL 코드는 인라인이 전제입니다. -O0 에서는 operator[], 반복자 ++, 람다 호출이 전부 진짜 함수 호출이라 std::accumulate 가 -O2 보다 60 배 느렸습니다. C++ 속도를 디버그 빌드로 판단하지 마세요. 둘째, 기본 비교의 std::sort 는 거의 그대로였습니다. libc++ 가 최적화된 것을 라이브러리에 미리 넣어 두기 때문입니다(5강). 람다 비교는 여러분의 플래그로 컴파일됩니다. 셋째, ranges 가 자동으로 공짜는 아닙니다. -O2 에서 filter | transform 은 33.6 ms, 같은 조건의 일반 루프는 1.2 ms 였고, 후자는 컴파일러가 분기 없는 벡터 명령으로 바꿨습니다. 핫 패스에 뷰를 쓰기 전에 재 보세요. 캐시 효과와 lldb 로 조사하는 법은 C 강좌 6강에 있습니다.

흔한 실수 → 실제로 일어난 일 → 해결

솔직한 한계와 버전 메모

• 실행 환경은 Apple clang 21.0.0 과 libc++(_LIBCPP_VERSION 220106), M1 Pro 한 대, macOS 26 뿐입니다. GCC/libstdc++, MSVC, Linux, Valgrind(helgrind)는 돌리지 않았습니다. 비율은 CPU 캐시와 코어 수에 따라 달라지고, 10% 정도까지의 차이는 실행마다의 흔들림 범위입니다.
• 이 Mac 의 steady_clock 은 약 42 ns 단위라서 1 마이크로초 미만의 시간은 싣지 않았습니다.
• 버전: std::thread, std::async, std::mutex, std::atomic 은 C++11, std::jthread 는 C++20(여기서 __cpp_lib_jthread 201911). std::hardware_destructive_interference_size(C++17)는 정의되어 있었습니다. std::execution::par 병렬 알고리즘은 이 libc++ 에 없었고, import std; 는 unknown type name 'import' 로 실패했습니다(이 툴체인에는 표준 라이브러리 모듈이 들어 있지 않음).
• SSO 한계 22 글자, 확장 비율 2 배, 미리 컴파일된 std::sort 는 libc++ 구현 사항입니다.
• TSan 종료 코드 134 는 여기서 관찰한 값입니다. 문서상 기본 동작은 경쟁을 보고하면 0 이 아닌 코드로 끝나는 것입니다.

연습 문제

1. race.cpp 를 어떤 최적화 수준에서도 200000 을 출력하고 TSan 이 아무것도 보고하지 않도록 고치세요. 변경은 최소로.

2. 실행하지 말고 libc++ 에서 각 루프의 힙 할당 횟수를 예측한 뒤, 횟수를 세는 operator new 로 확인하세요.

for (int len : {10, 30}) {
    std::vector<std::string> v;
    v.reserve(1000);
    for (int i = 0; i < 1000; ++i) v.push_back(std::string(len, 'x'));
}

정답

1. 카운터를 원자 변수로 바꿉니다.

#include <atomic>
std::atomic<int> counter{0};
void work(){ for(int i=0;i<100000;i++) counter++; }
// print with counter.load()

-fsanitize=thread 빌드에서 counter=200000 (expected 200000), 경고 없음, 종료 코드 0 이었습니다. std::atomic<int> 의 counter++ 는 원자적 fetch_add 입니다. 속도를 원한다면 실측 절의 지역 합계 버전이 더 낫습니다.

2. 10 글자는 1 번(reserve 한 버퍼뿐. 10 글자는 SSO 버퍼에 들어감). 30 글자는 1001 번(버퍼 + 문자열마다 한 번). push 한 임시 객체는 vector 로 이동되고, 힙 문자열의 이동은 포인터를 넘길 뿐입니다. reserve 가 없으면 30 글자에서 1011 번으로, 버퍼가 1, 2, 4, …, 1024 로 커지는 11 번이 더해집니다.

시리즈를 마치며

C++ 강좌는 여기까지입니다. 1강부터 따라왔다면 이제 새니타이저를 켜고 빌드와 디버깅을 하고, RAII 와 스마트 포인터로 자원을 소유하고, 템플릿 오류를 읽고, 성능 판단을 실측으로 뒷받침할 수 있습니다. 새로 배우는 동료에게 권한다면 1강부터 보여 주세요.

• 이전: C++ 강좌 5강: 템플릿, STL 알고리즘, ranges
• 그 전: 2강, 3강, 4강
• 관련: C 성능: 캐시, make, lldb, Swift 메모리와 -O 성능, 프로그래밍 학습 로드맵