히트맵 차트에 쓸 2차원 배열이 있다. 열마다 합계를 구해야 해서 바깥 루프로 열을, 안쪽 루프로 행을 돈다. 리뷰어가 "루프 순서를 바꾸면 더 빨라요"라고 남겼다. 덧셈 횟수는 똑같이 행 수 × 열 수다. (입력이 커질 때 연산 횟수가 늘어나는 정도를 나타내는 표기)로 보면 두 코드는 같은 O(행 × 열)이다. 무엇이 다를까?
Big-O는 연산 횟수를 센다. 하지만 연산 하나의 비용이 늘 같지는 않다. 같은 "배열에서 값 하나 읽기"도 그 값이 CPU 가까이에 있느냐 멀리 있느냐에 따라 걸리는 시간이 다르다. 이 장은 그 거리를 세는 법을 본다.
메모리 계층: 가까울수록 작고 빠르다
CPU가 값을 꺼내 오는 곳은 한 군데가 아니다. 계산 중인 값은 CPU 안의 레지스터(register)에 있다. 그 바깥에 캐시(cache)가 몇 단계(L1, L2, L3) 있고, 그 바깥이 메인 메모리(RAM)다. 더 바깥에는 SSD 같은 저장 장치가, 그 바깥에는 네트워크 너머의 다른 컴퓨터가 있다.
| 층 | 크기 | 빠르기 |
|---|---|---|
| 레지스터 | 가장 작다 | 가장 빠르다 |
| CPU 캐시(L1·L2·L3) | 작다 | 빠르다 |
| 메인 메모리 | 크다 | 느리다 |
| 저장 장치(SSD) | 더 크다 | 더 느리다 |
| 네트워크 너머 | 사실상 끝이 없다 | 가장 느리다 |
층마다 걸리는 시간은 하드웨어마다 다르다. 여기서 기억할 것은 방향 하나다. 표의 위쪽(레지스터)이 CPU에 가깝다. 아래층으로 갈수록 크고 싸지만, 한 번 다녀오는 데 드는 시간이 층을 내려갈 때마다 크게 불어난다. 그래서 하드웨어는 "곧 쓸 것 같은 값"을 위층에 미리 올려 둔다. 위층에 원하는 값이 있으면 캐시 적중(hit), 없어서 아래층까지 다녀와야 하면 캐시 실패(miss)다.
캐시 라인: 한 칸을 읽으면 이웃도 따라온다
캐시는 메모리에서 값을 한 칸씩 가져오지 않는다. 이웃한 칸 여러 개를 묶은 덩어리, 캐시 라인(cache line)을 통째로 가져온다. 그래서 방금 읽은 칸의 바로 옆 칸은 이미 캐시에 와 있다. 가까운 곳을 이어서 읽는 성질을 공간 지역성(spatial locality)이라고 한다.
C의 2차원 배열이나 1차원 Float64Array에 담은 격자는 메모리에 이어서 놓인다. 행 우선(row-major)으로 놓으면 0행의 칸들이 먼저, 그다음 1행의 칸들이 이어진다. 행을 따라 읽으면 메모리를 앞에서부터 차례로 읽는 셈이고, 열을 따라 읽으면 한 행 길이만큼씩 건너뛰며 읽는 셈이다. JavaScript의 number[][]는 행마다 따로 놓인 배열의 묶음이지만, 한 행 안의 칸은 대개 이어져 있어 같은 이유로 행을 따라 읽는 쪽이 유리하다.
아주 작은 캐시 모델로 따져 보자. 캐시 라인(이 모델에서는 '줄') 하나에 칸 2개, 캐시 자리 2개다. 메모리를 캐시 라인 크기(2칸)씩 나눈 덩어리를 블록이라 부른다. 칸 번호를 2로 나눈 몫이 블록 번호다. 정리하면 블록은 메모리를 2칸씩 자른 덩어리, 자리는 캐시 안의 빈 곳(이 모델에서 2개), 블록 하나를 자리 하나에 복사해 둔 것이 줄이다. 블록 번호를 자리 수로 나눈 나머지 자리에만 들어갈 수 있다(직접 사상, direct-mapped. 나머지 연산 %는 『개발 수학』 Unit 5). 실제 CPU 캐시는 줄도 자리도 훨씬 많고 들어가는 규칙도 더 복잡하지만, 적중과 실패가 갈리는 이유는 같다. 칸 12개를 이 규칙으로 나누면 이렇다.
| 칸 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 블록(칸 ÷ 2의 몫) | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 |
| 자리(블록 % 2) | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
3행 4열 배열(칸 12개)을 열을 따라 읽으면 0번 칸(블록 0) 다음에 4번 칸(블록 2)을 읽는다. 한 줄 2칸, 자리 2개짜리 직접 사상 캐시에서 4번 칸을 읽고 나면 블록 0은 캐시에 남아 있을까?
선택지와 해설 보기
실험 행으로 돌 때와 열로 돌 때
3행 4열 배열(칸 0~11)을 메모리에 행 우선으로 놓았습니다. 캐시 한 줄에 칸 2개가 들어가고, 캐시에는 자리가 2개 있습니다. 한 번 누를 때마다 칸 하나를 읽습니다. 초록(✓)은 적중, 빨강(×)은 실패입니다.
- 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 자리 0: 빈 자리
- 자리 1: 빈 자리
캐시가 비어 있습니다. 한 칸씩을 눌러 보세요. 적중 0 / 0 (전체 12칸).
- 해볼 것
- 열 순회에서 블록 0이 처음 밀려나는 칸을 찾는다
- 행 순회를 끝까지 넘겨 적중 수를 본다
- 열 순회를 끝까지 넘겨 행 순회와 견준다
행 순회는 짝수 칸에서 실패하며 블록을 가져오고, 바로 다음 홀수 칸에서 그 블록을 그대로 쓴다. 칸 두 개에 한 번만 메모리까지 간다. 열 순회는 0번 칸(블록 0) 다음에 4번 칸(블록 2)을 읽는다. 블록 2는 = 0번 자리에 들어가야 해서 블록 0을 밀어낸다. 1번 칸을 읽으러 돌아왔을 때 블록 0은 이미 없다. 12번 모두 실패다. 가져온 줄의 절반을 쓰지도 못하고 버린 것이다.
실험 캐시 모델로 세어 보는 적중률
배열을 키우고 캐시 크기를 바꿔 보자.
8×8 배열(칸 64개)을 행 우선으로 놓았습니다. 캐시 한 줄에 칸 4개가 들어갑니다. 칸은 메모리 순서대로 그렸고, 초록은 적중, ×가 있는 빨강은 실패입니다. 실제 CPU를 잰 것이 아니라 적중과 실패만 세는 모델입니다.
적중 48 / 64 (75%). 캐시에 담을 수 있는 칸은 16개입니다.
- 해볼 것
- 캐시 자리 4개에서 열 순회로 바꿔 적중률이 얼마나 떨어지는지 본다
- 열 순회 그대로 캐시 자리를 16개로 늘려 본다
- 캐시 자리 4개에서 연결 리스트 순회의 적중률을 본다
8×8 배열(64칸), 한 줄에 칸 4개인 모델로 키우면 캐시 자리 4개에서 열 순회는 64번 모두 실패한다. 자리를 16개로 늘리면 배열 64칸이 통째로 들어가서 열 순회도 행 순회와 같은 48번 적중이 된다. 데이터가 캐시에 다 들어갈 만큼 작으면 순서가 상관없다는 뜻이다. 실무의 데이터는 대개 캐시보다 훨씬 크다. 그래서 2차원 배열은 메모리에 놓인 순서대로, 행 우선이면 바깥 루프를 행으로 도는 것이 기본이다.
배열과 연결 리스트: 이웃해 있느냐, 흩어져 있느냐
배열은 원소를 메모리에 이어 붙여 둔다. 처음부터 끝까지 훑으면 캐시 라인 하나를 가져올 때마다 그 안의 원소를 모두 쓴다. 연결 리스트(linked list)는 노드마다 따로 메모리를 받아 다음 노드의 주소를 들고 있다. 노드가 메모리 어디에 놓일지는 할당할 때 정해져서, 리스트 순서와 메모리 순서가 서로 다르다. 다음 노드로 갈 때마다 새 캐시 라인을 가져와야 할 가능성이 크다. 연결 리스트 자체는 연결 리스트 노트에 있다.
같은 캐시 모델에서 노드 64개를 메모리 64칸에 뒤섞어 놓고 리스트 순서대로 따라가면, 캐시 자리 4개에서 적중은 11번이다. 같은 64칸, 같은 캐시에서 행 순회는 48번이었다. 연산 횟수는 똑같이 O(n)인데 메모리까지 다녀오는 횟수가 크게 다르다. 중간 삽입이 O(1)이라는 연결 리스트의 장점(배열은 중간에 넣으면 뒤를 다 밀어야 하지만 리스트는 앞뒤 연결만 바꾼다)이 실제로는 잘 드러나지 않는 이유가 여기에 있다. 삽입할 자리를 찾아가는 동안 이미 캐시 실패를 많이 겪는다.
언어가 무엇을 이어 붙이는지도 봐야 한다. CPython의 리스트는 연결 리스트가 아니라 가변 길이 배열(variable-length array)이다. 다만 배열에 이어 붙은 것은 값이 아니라 다른 객체를 가리키는 참조다(Python FAQ: 리스트는 어떻게 구현되나). 숫자 값 자체를 빽빽하게 이어 담고 싶으면 표준 라이브러리 array 모듈이 있다(Python 문서: array). JavaScript에서는 Float64Array 같은 형식화 배열(TypedArray)이 연속된 바이트 버퍼(ArrayBuffer) 위에 값을 담는다(MDN: TypedArray). 차트·이미지·오디오처럼 숫자가 아주 많은 데이터에 쓰는 이유다.
시간 지역성과 LRU: 무엇부터 버릴까
방금 쓴 값은 곧 다시 쓸 가능성이 크다. 이 성질을 시간 지역성(temporal locality)이라고 한다. 캐시는 자리가 한정되어 있으니 새 값을 넣으려면 무언가를 버려야 한다. 시간 지역성을 믿는다면 "가장 오래 안 쓴 것"부터 버리는 것이 자연스럽다. 이 규칙이 LRU(least recently used)다. CPU 캐시만의 이야기가 아니다. 브라우저의 HTTP 캐시, 서버 앞의 Redis, 함수 결과를 기억하는 (memoization) 모두 같은 질문을 한다. 앱 쪽 캐시 전략은 LRU 캐시, 캐시 어사이드 노트에 있다.
JavaScript의 Map은 키를 넣은 순서대로 돌려준다(MDN: Map). Python의 dict도 3.7부터 넣은 순서를 보장하고, 지웠다가 다시 넣은 키는 맨 뒤로 간다(Python 문서: dict). 이 성질만으로 LRU를 짤 수 있다. 쓸 때마다 지웠다가 다시 넣어 맨 뒤로 옮기면, 맨 앞이 늘 가장 오래 안 쓴 키다.
실험 Map과 dict로 만드는 LRU 캐시
두 입력에서 Map의 순서가 바뀌는 모습을 따라가 보자.
cache의 맨 앞이 가장 오래 안 쓴 키, 맨 뒤가 가장 최근에 쓴 키입니다. 크기가 CAP을 넘으면 맨 앞을 내보냅니다. 아래 칸은 cache를 그 순서대로 그렸습니다.
const CAP = 2const cache = new Map<string, number>()function get(key: string): number { if (!cache.has(key)) return -1 const val = cache.get(key)! cache.delete(key) cache.set(key, val) return val}function put(key: string, val: number) { cache.delete(key) cache.set(key, val) if (cache.size > CAP) { const oldest = cache.keys().next().value! cache.delete(oldest) }}const ops: [string, string, number][] = [['put', 'a', 1], ['put', 'b', 2], ['get', 'a', 0], ['put', 'c', 3], ['get', 'b', 0], ['get', 'a', 0]]for (const [op, key, val] of ops) { if (op === 'put') put(key, val) else console.log(`get ${key} → ${get(key)}`)}
- CAP
- 2
- 해볼 것
- '읽으면 살아남는다' 입력을 끝까지 실행해 b가 밀려나는 것을 본다
- '안 읽으면 밀려난다' 입력을 끝까지 실행해 a가 밀려나는 것을 본다
크기 2인 캐시에 a, b를 넣고 c를 넣으면 맨 앞의 a가 밀려나지만, c를 넣기 전에 a를 한 번 읽어 두면 b가 밀려난다. 같은 put 세 번이라도 그 사이에 읽었느냐에 따라 살아남는 키가 다르다.
Python에는 함수 결과를 이 방식으로 기억해 주는 functools.lru_cache가 있다. 기본 크기(maxsize)는 128이고, maxsize=None이면 크기 제한 없이 계속 자란다(Python 문서: lru_cache). 순서 조작이 더 필요하면 collections.OrderedDict의 move_to_end와 popitem(last=False)를 쓴다(Python 문서: OrderedDict).
함정 찾기 AI가 짠 열 합계와 캐시 코드, 어디가 느리거나 새고 있을까?
“2차원 배열의 열 합계를 구하는 함수, 상품 가격을 캐시해 두는 함수, 크기 제한이 있는 LRU 캐시 클래스를 짜 줘.”
의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 4개입니다.
확인 문제 장을 덮기 전에 떠올려 보기
1. 행 우선으로 놓인 큰 2차원 배열의 합을 구할 때 더 빠른 순회는?
2. 연결 리스트를 처음부터 끝까지 훑는 것이 배열보다 느리기 쉬운 이유는?
3. Map으로 LRU 캐시를 짤 때, 이미 있는 키를 읽었으면 할 일은?
더 풀어 보기(선택) · 순서 기능 없이 O(1) LRU 만들기
Map·dict가 넣은 순서를 기억한다는 성질을 쓰지 않고 LRU 캐시를 짜 보자. 해시맵(hash map, Map·dict)은 "키 → 값" 찾기에만 쓴다. get(key)와 put(key, val) 모두 O(1)이어야 하고, 크기가 CAP을 넘으면 가장 오래 안 쓴 키를 내보낸다(새 키만 넣는다고 가정한다).
CAP = 2 put a 1, put b 2, get a → 1, put c 3, get b → -1, get a → 1