개요

이론 정리 - < SOLID 다섯 원칙 > 마지막에 다음은 자료구조 쪽이고 첫 질문은 이거라고 적어뒀다.

std::vector와 std::list 둘 다 순회가 O(N)인데 왜 실제로는 vector가 훨씬 빠른 경우가 많은가

넥토리얼 대비로 CS를 훑는 중인데, 지난 나흘은 메모리와 OOP 쪽이었고 오늘부터 자료구조·알고리즘으로 넘어간다. 깊이 파기보다 범위를 넓히는 쪽을 골랐다. 곧 50분짜리 모의 면접을 한 번 보기로 해서, 한 주제를 오래 붙잡는 것보다 빈 칸을 먼저 없애는 게 낫다고 봤다.

방식은 AI에게 설명하고 틀린 데를 짚어달라고 하는 식으로 갔다. 눈으로 읽으면 다 아는 것 같은데 말로 꺼내면 어디가 뭉개져 있는지가 드러난다. 이번 편의 절반이 그렇게 드러난 것들이다.

위 질문까지는 답을 알고 있다고 생각했다. 연속 메모리라 캐시에 같이 들어온다, 리스트는 다음 노드 주소를 이전 노드에서 읽어야 한다 — 이 두 줄이 내가 들고 있던 답이었고 방향은 맞았다. 문제는 그 뒤였다.

  • 방향은 맞는데 이름이 없던 것 — “병렬 처리가 어렵다”고 말해놓고 뭐가 병렬인지는 나도 몰랐다
  • 다른 물건을 한 덩어리로 섞어놓은 것 — 캐시와 prefetch와 TLB를 구분 없이 끌어다 썼다
  • 정의를 감각으로 대체하고 있던 것 — Big-O를 “가속도” 비슷하게 설명했다. 오늘 제일 크게 고친 자리다
  • 공식은 아는데 왜인지는 모르던 것 — 상각 O(1)의 근거 식은 외우고 있었는데, 그게 왜 호출 하나당 O(1)이 되는지는 설명하지 못했다

그리고 세 번째 항목을 정리하다가 예상 못한 데로 튀었다. 1년 반 전에 이론 정리 - < Big-O, 정렬, DFS/BFS >를 쓰면서 Big-O를 이렇게 적어뒀었다.

Big-O는 알고리즘의 최악의 경우를 가정하여 성능을 평가

이 문장도 손을 봐야 했다.

같은 복잡도인데 실제 속도가 다르다면, 그 차이는 어디에 적혀 있는가? 이번 편은 이 질문으로 계속 돌아온다.

( 이번에도 눈으로 읽고 결과를 추론하는 방식으로 진행했고, 직접 컴파일해서 돌려보지는 않았다. 아래 코드는 전부 개념 예시다 )

1. 방향은 맞았는데 이름이 없었다

내가 알고 있던 건 이 정도였다.

  • vector는 연속 메모리라 주변 데이터가 캐시에 같이 들어오기 쉽다
  • list는 다음 노드 주소를 이전 노드에서 읽어야 하므로 병렬 처리가 어렵다

두 번째 줄이 특히 마음에 걸렸다. “병렬 처리가 어렵다”는 게 무슨 뜻인지 나도 정확히 몰랐다. 스레드 얘기는 아닌 것 같은데, 그럼 뭐가 병렬인가.

여기 붙는 이름이 memory-level parallelism(메모리 수준 병렬성)이었다.

outstanding load

CPU가 메모리 읽기를 요청하고 아직 결과가 안 돌아온 상태를 outstanding load(완료되지 않은 메모리 읽기 요청)라고 부른다. 중요한 건 CPU가 그 결과를 기다리는 동안 멍하니 있지 않는다는 것이다. 주소가 서로 독립적인 읽기라면 여러 개를 동시에 띄워놓을 수 있다.

vector : &v[0], &v[1], &v[2] ... 주소를 계산으로 바로 구할 수 있다
         -> 읽기 요청 여러 개를 동시에 발행 가능
         -> 지연 시간이 겹쳐서 숨겨진다

list   : node->next 를 읽어야 다음 노드 주소를 안다
         -> 이전 읽기가 끝나야 다음 읽기를 시작할 수 있다
         -> 지연 시간이 일렬로 쌓인다

아래쪽이 dependent load chain(의존적 읽기 사슬), 흔히 말하는 pointer chasing(포인터 추적)이다. 내가 “병렬 처리가 어렵다”고 뭉개서 말한 게 정확히 이거였다.

캐시 라인 활용률

캐시는 바이트 단위가 아니라 cache line(캐시 라인) 단위로 메모리를 가져온다. 흔한 예시로 64바이트를 쓴다.

vector<int>라면 한 번 가져온 64바이트에 int 16개가 들어있다. 하나 쓰려고 가져왔는데 다음 15개가 딸려온 셈이다. 이게 spatial locality(공간 지역성)다.

list는 노드가 힙 여기저기에 흩어질 수 있다. 64바이트를 가져와도 그중 실제로 쓸 값은 노드 하나뿐일 수 있다. 나머지는 옆에 있던 남의 데이터거나 padding이다.

여기에 prefetcher(미리 가져오기 장치)가 하나 더 붙는다. 접근 패턴이 규칙적이면 CPU가 알아서 다음 걸 미리 요청해둔다. 순차 접근하는 vector는 이게 잘 먹고, 주소가 튀는 list는 예측할 패턴 자체가 없다.

2. TLB를 캐시와 섞어 쓰고 있었다

vector의 이점을 설명하면서 TLB를 끌어왔는데, 나는 그걸 “주소를 미리 계산해둬서 miss가 적다”는 식으로 말했다. 캐시랑 prefetch랑 TLB를 한 덩어리로 섞어놓은 설명이었다.

셋은 다른 물건이다.

이름 저장하는 것
Cache(캐시) 실제 데이터
TLB(Translation Lookaside Buffer, 주소 변환 캐시) 가상 페이지 → 물리 페이지 변환 결과
Prefetcher(미리 가져오기 장치) 저장하는 게 아니라, 패턴을 보고 미리 요청함

TLB는 데이터를 들고 있는 게 아니라 주소 번역표의 캐시다. vector가 유리한 이유는 “주소를 미리 계산해서”가 아니라, 연속된 가상 메모리를 조밀하게 쓰기 때문에 같은 페이지 변환 결과를 많은 원소가 재사용할 수 있어서다.

같은 결론에 도달하더라도 경로가 틀리면 한 번 더 물어봤을 때 무너진다.

3. padding — 노드 하나가 생각보다 크다

list 노드를 이렇게 놓고 봤다.

struct Node
{
    Node* prev;  // 8 bytes
    int   value; // 4 bytes
    Node* next;  // 8 bytes
};

64비트 환경에서 포인터는 8바이트 경계에 맞춰 놓여야 한다. value가 4바이트라서 그 뒤에 padding(채움 바이트)이 들어갈 수 있다. 실제로 담고 싶은 값은 int 하나인데 노드 하나가 그것보다 몇 배로 커진다.

멤버 순서를 이렇게 놓은 건 padding이 생기는 자리를 보여주려는 것이고, 실제 std::list 구현이 멤버를 어떤 순서로 놓는지는 구현체마다 다를 수 있다.

padding은 컴파일러가 alignment(정렬)를 맞추려고 넣는 빈 공간이지 의미 있는 멤버가 아니다. 그런데 캐시 라인을 가져올 때는 이 빈 공간도 같이 딸려온다. 1번에서 말한 “가져온 64바이트 중 쓸 게 얼마나 되는가”가 여기서 더 나빠진다.

4. Big-O는 가속도가 아니다

오늘 제일 크게 고친 자리다.

나는 Big-O를 입력 크기가 커질 때 비용이 얼마나 빠르게 붙는지, 일종의 가속도처럼 설명했다. 방향 감각으로는 틀리지 않은데, 정의로 쓰면 틀린 말이다.

정확히는 asymptotic upper bound(점근적 상한)다. N이 충분히 커졌을 때 비용이 어떤 차수 이내로 성장하는지를 표현한다. 그리고 여기가 오늘의 핵심인데,

Big-O는 실제 실행 시간의 상수 계수를 표현하지 않는다.

vector와 list가 같은 O(N)인데 실제 속도가 다른 이유가 바로 이거였다. 1번, 2번, 3번에서 본 것들 — 캐시 라인 활용률, 포인터 추적, padding — 은 전부 Big-O 표기에서 지워지는 상수 계수 안쪽에 있다. 지워진 곳에 실제 성능이 살고 있었다.

Θ와 Ω

1년 반 전 글에는 O만 있었다. 이번에 Θ를 처음 듣고 “O(N)의 다른 표기” 정도로 받아들였는데 아니었다.

O(N) : N 차수의 점근적 상한 — 이보다 빨리 커지지는 않는다
Ω(N) : N 차수의 점근적 하한 — 이보다 느리게 커지지도 않는다
Θ(N) : 위 둘이 동시에 성립 — 실제 성장 차수가 N이다

정의로 쓰면 이렇다. 충분히 큰 N에서 양의 상수 c1, c2가 존재해

c1 * N <= T(N) <= c2 * N

를 만족하면 T(N) = Θ(N)이다.

그래서 vector와 list의 전체 순회는 O(N)보다 Θ(N)이라고 쓰는 게 더 정확하다. 상한만 걸린 게 아니라 실제로 N에 비례해서 늘기 때문이다.

1년 반 전 문장 — “최악의 경우를 가정하여”

예전 글에 이렇게 적어뒀었다.

Big-O는 알고리즘의 최악의 경우를 가정하여 성능을 평가

이건 Big-O의 정의와, Big-O를 쓰는 관행을 붙여놓은 문장이다. 두 가지가 섞여 있다.

  • 어느 경우를 분석할 것인가 — 최선/평균/최악 중 무엇을 볼지 고르는 문제
  • 그 경우의 비용을 어떻게 표기할 것인가 — O, Ω, Θ 중 무엇을 쓸지의 문제

이 둘은 서로 독립이다. 평균 경우의 Big-O를 쓸 수도 있고(해시 테이블 탐색이 딱 그렇다), 최악 경우의 Θ를 쓸 수도 있다. Big-O 자체에 “최악”이라는 뜻이 들어있는 건 아니다.

관행적으로 최악 경우를 Big-O로 쓰는 일이 많아서 저렇게 외우게 되는데, 나도 그렇게 외우고 있었다.

5. size와 capacity — reserve와 resize가 다른 이유

std::vector<int> v;

v.reserve(100);
// size == 0
// capacity >= 100
// 여기에 int 100개가 존재하는 건 아니다

v.resize(100);
// size == 100
// 필요한 int 객체들의 수명이 시작된다
  • size : 지금 실제로 수명이 시작되어 존재하는 원소 수
  • capacity : 재할당 없이 원소를 만들 수 있도록 확보된 저장 공간

reserve()는 공간만 잡고 객체를 만들지 않는다. 이 문장을 쓰다가 한 번 과하게 나갔는데, “reserve()는 객체 수명과 전혀 관계없다”고 적으면 틀린다.

기존 원소가 이미 있는 상태에서 더 큰 capacity를 잡으려면 reallocation(재할당)이 일어난다. 그러면 기존 원소들이 새 저장 공간으로 이동하거나 복사되고, 원래 자리의 객체 수명은 거기서 끝난다. 그러니까 정확히는 이렇게 적어야 한다.

reserve()는 추가로 확보한 capacity 부분에 T 객체의 수명을 시작하지 않는다.

여기서 앞 편의 이동 의미론이 그대로 걸린다. 기존 원소를 새 저장 공간으로 옮길 때 무엇이 불려나가는가 — 이동 생성자다. 그 편에서 “이동 생성자는 복사를 편하게 해주는 도우미가 아니라 복사를 안 하려고 있는 것“이라고 적어뒀는데, 재할당이 그 문장이 실제로 걸리는 자리였다.

push_back()이 reserve()를 부르는 게 아니다

설명하다가 “push_back() 할 때마다 내부적으로 reserve()가 호출된다”고 말했는데, 이건 표현이 틀리다.

reserve()는 내가 명시적으로 부르는 멤버 함수다. 자동으로 일어나는 건 그게 아니라 capacity가 부족할 때 vector 내부에서 재할당이 발생하는 것이다. 결과가 비슷해 보여도 부르는 주체가 다르다.

6. 상각 O(1) — 공식은 알았는데 왜인지는 몰랐다

push_back()이 amortized O(1)이라는 건 알고 있었고, 근거로 이 식도 알고 있었다.

1 + 2 + 4 + ... + N/2 < N

그런데 이게 왜 호출 하나당 O(1)로 이어지는지는 설명하지 못했다. 식을 외운 거지 이해한 게 아니었다.

capacity가 기하급수적으로(예를 들어 2배씩) 늘어난다고 하면, 재할당은 매번이 아니라 가끔 일어난다. N개를 넣는 동안 재할당 때문에 기존 원소를 옮긴 총량이 위 식 수준에 머문다. 여기에 원소를 실제로 넣는 비용 N번을 더해도 전체는 O(N)이다.

핵심은 마지막 한 걸음이었다.

전체 N번의 push_back 비용 = O(N)
-> 이걸 N개의 연산으로 나눈다
-> 연산 하나당 O(1)

즉 amortized analysis는 가끔 비싼 연산의 값을 전체 연산 수로 나눠서 분산시키는 것이다. 공식이 아니라 비용 분산이 본체였다.

그래서 이건 여전히 참이다.

특정 한 번의 push_back()은 재할당 때문에 O(N)일 수 있다.

프레임 단위로 돌아가는 게임에서는 이 “가끔”이 하필 이번 프레임에 걸리는 게 문제가 된다. 평균은 괜찮은데 특정 프레임만 튀는 상황 — 지난주 유니티 14편에서 프레임 스파이크를 쫓던 게 같은 모양이었다.

한 가지 덧붙이면, C++ 표준은 성장 배율을 몇 배로 하라고 강제하지 않는다. 2배라거나 1.5배라는 이야기는 구현체마다 다를 수 있어서, 그 숫자를 단정하는 대신 “기하급수적으로 늘어난다”까지만 들고 있기로 했다.

정리

방향은 맞았던 것

  • vector가 연속 메모리라 캐시에 유리하다 — 맞다. 이름만 없었다
  • list는 다음 노드 주소를 이전 노드에서 읽어야 한다 — 맞다. 이게 pointer chasing이다
  • 재할당이 일어나면 기존 포인터가 위험해진다 — 맞다. 왜인지는 다음 편에서 더 판다

이름을 새로 붙인 것

  • memory-level parallelism — “병렬 처리가 어렵다”고 뭉개던 자리
  • outstanding load — 독립적인 읽기는 여러 개를 동시에 띄울 수 있다
  • spatial locality / cache line 활용률 — 가져온 64바이트 중 얼마나 쓰는가

틀리게 잡고 있던 것

  • TLB는 데이터 캐시가 아니라 주소 변환 캐시다. prefetch와도 다른 물건이다
  • Big-O는 가속도가 아니라 점근적 상한이다. 상수 계수는 표현하지 않는다
  • Θ는 O의 다른 표기가 아니다. 상한과 하한이 모두 성립하는 경우다
  • Big-O에 “최악의 경우”라는 뜻이 들어있는 건 아니다. 어느 경우를 볼지와 어떻게 표기할지는 별개 축이다
  • reserve()가 객체 수명과 무관하다고 말하면 과하다. 재할당이 끼면 기존 원소의 수명은 끝난다
  • push_back()이 reserve()를 부르는 게 아니다. 내부에서 재할당이 일어나는 것이다

이번에 새로 얹은 것

  • padding은 alignment를 맞추려는 빈 공간이고, 캐시 라인에 같이 실려온다
  • 상각 O(1)은 공식이 아니라 비용을 연산 수로 나누는 것이다
  • 표준은 vector 성장 배율을 강제하지 않는다

1년 반 전에 쓴 글을 다시 열어볼 생각은 없었는데, “가속도” 얘기를 하다가 그때 뭐라고 적었나 궁금해져서 열어봤다가 문장 하나를 고치게 됐다. 그때는 정의를 옮겨 적는 게 목적이었고, 지금은 vector와 list 중 뭘 쓸지 고르려고 같은 표기를 보고 있다. 목적이 달라지니까 같은 문장에서 안 보이던 게 보였다.

다음은 재할당이 실제로 뭘 깨뜨리는지다. 5번에서 “기존 원소의 수명이 끝난다”까지 왔으니, 그 원소를 가리키던 iterator는 그때 어떻게 되는가가 다음 자리다.

참고 자료

소감

같은 O(N)인데 왜 다르냐는 질문 하나로 시작했는데, 답이 “Big-O가 지워버린 곳에 있다”로 끝났다. 그러다 1년 반 전 글까지 열어보게 됐고 거기 적어둔 정의도 손봐야 했다..! 그때 정리는 정의를 옮겨 적는 데까지였고 그 자체로 틀린 건 아니었는데, 지금 필요한 건 뭘 쓸지 고르는 기준이라 같은 문장이 부족하게 느껴졌다. 예전 글이 부끄럽다기보단, 1년 반 만에 질문이 바뀐 게 눈으로 보여서 좀 재밌었다.