캐시 지역성

캐시 지역성은 메모리를 읽는 순서가 캐시를 얼마나 잘 살려 쓰는지를 가리킵니다. 가까운 메모리를 이어서 읽거나 방금 읽은 값을 곧 다시 읽으면 캐시 지역성이 좋다고 합니다. 지역성이 좋은 코드는 읽기 대부분을 빠른 캐시에서 끝냅니다. 하는 일의 양이 같아도 데이터를 늘어놓은 모양에 따라 속도가 크게 갈립니다.

상세

요리를 하면서 재료가 필요할 때마다 창고까지 걸어가면 요리보다 오가는 데 시간이 더 듭니다. 그래서 창고에 한 번 갈 때 그 선반의 재료를 바구니째 들고 와 조리대에 올려 둡니다. 다음 재료가 바구니 안에 있으면 손만 뻗으면 됩니다. 방금 쓴 소금은 조리대에 있으니 다시 집기 쉽습니다.

캐시 지역성은 코드가 이 바구니를 얼마나 잘 쓰는지를 말합니다. 이 절은 먼저 캐시가 메모리를 덩어리로 가져오는 방식을 봅니다. 그다음 배열과 연결 리스트를 견주어 데이터를 늘어놓은 모양이 무엇을 바꾸는지 봅니다. 끝으로 이 성질을 신경 써야 할 때와 아닐 때를 가릅니다.

캐시 지역성이 말하는 캐시

프로세서가 계산에 쓸 값은 메모리에 있습니다. 메모리에서 값을 가져오는 데는 프로세서가 덧셈 한 번 하는 것보다 훨씬 오래 걸립니다.

그래서 프로세서 안에 작고 빠른 메모리를 따로 두고 자주 쓰는 값의 복사본을 담아 둡니다. 이 메모리를 CPU 캐시라고 부릅니다. CPU(Central Processing Unit, 중앙 처리 장치)는 프로세서를 가리키는 말입니다.

읽을 값이 캐시에 있으면 캐시 히트, 없으면 캐시 미스라고 합니다. 캐시 미스가 나면 프로세서는 메모리에서 값이 올 때까지 기다립니다. 캐시 지역성이 좋다는 말은 캐시 히트가 많고 캐시 미스가 적다는 뜻입니다.

백엔드 개발자에게 캐시라고 하면 데이터베이스 앞에 두는 캐시 서버가 먼저 떠오를 겁니다. 캐시 지역성의 캐시는 그것이 아닙니다. 프로세서 안의 CPU 캐시를 가리킵니다.

캐시 라인

캐시는 메모리에서 값을 한 바이트씩 가져오지 않습니다. 이웃한 바이트 여러 개를 한 덩어리로 묶어 한꺼번에 가져옵니다. 이 덩어리를 캐시 라인이라고 합니다. 앞의 비유에서 바구니에 해당합니다.

값 하나를 읽다가 캐시 미스가 나면 그 값이 든 캐시 라인 전체가 캐시로 올라옵니다. 바로 옆에 있는 값은 따로 가져오지 않아도 이미 캐시에 있습니다. 라인 하나는 정수 여러 개가 들어갈 만한 크기입니다.

공간 지역성과 시간 지역성

프로그램은 메모리를 아무 데나 고르게 읽지 않습니다. 방금 읽은 곳 근처를 읽고, 방금 읽은 값을 또 읽는 경향이 있습니다. 이 경향을 참조 지역성이라고 합니다. 캐시 지역성은 코드가 이 경향을 얼마나 잘 따라 캐시 덕을 보는지를 말합니다.

참조 지역성은 두 갈래로 나눠 부릅니다. 공간 지역성은 한 번 읽은 곳의 이웃을 곧이어 읽는 성질입니다. 배열을 앞에서 뒤로 훑는 반복문이 대표입니다. 캐시 라인이 이웃을 함께 가져오므로 공간 지역성이 좋으면 미스 한 번으로 값 여러 개를 읽습니다.

시간 지역성은 한 번 읽은 값을 머지않아 다시 읽는 성질입니다. 반복문이 도는 동안 작은 조회 표를 거듭 들여다보는 코드가 그렇습니다. 캐시는 한번 올린 라인을 한동안 두므로 다시 읽을 때 메모리까지 가지 않습니다.

캐시는 작아서 새 라인이 들어오면 오래된 라인을 내보냅니다. 이것을 축출이라고 합니다. 다시 읽기 전에 축출되면 시간 지역성의 덕을 못 봅니다. 한꺼번에 다루는 데이터가 캐시보다 훨씬 크면 이런 일이 잦습니다.

붙어 있는 데이터와 흩어진 데이터

같은 값 여러 개를 배열에 담을 때와 연결 리스트에 담을 때를 견줘 보겠습니다. 두 구조 모두 처음부터 끝까지 훑는 시간이 값 개수 n 에 비례합니다. 시간 복잡도로 적으면 둘 다 O(n) 입니다. 복잡도는 같아도 캐시 미스 횟수는 크게 다릅니다.

배열은 값을 메모리에 빈틈없이 붙여 둡니다. 배열 a 의 첫 값 a[0] 을 읽다 미스가 나면 같은 캐시 라인에 든 a[1] · a[2] · a[3] 도 함께 올라옵니다. 라인 하나에 값이 넷 들어간다면 미스는 값 넷에 한 번꼴로 납니다.

연결 리스트는 값마다 노드를 따로 만들고 포인터로 다음 노드를 가리킵니다. 노드는 만들어진 때에 따라 메모리 여기저기에 놓입니다. 다음 노드가 같은 캐시 라인에 있다는 보장이 없어서 노드마다 미스가 날 수 있습니다.

아래 그림은 라인 하나에 값이 넷 들어간다고 치고 두 구조를 위아래로 놓은 것입니다. 안쪽 네모 하나가 캐시 라인 하나입니다.

flowchart TD
    subgraph ARR["배열"]
        L1["캐시 라인 1 · a[0] a[1] a[2] a[3]"]
        L2["캐시 라인 2 · a[4] a[5] a[6] a[7]"]
        L1 -->|바로 다음 주소| L2
    end
    subgraph LIST["연결 리스트"]
        M1["캐시 라인 ㄱ · 노드 1"]
        M2["캐시 라인 ㄴ · 노드 2"]
        M3["캐시 라인 ㄷ · 노드 3"]
        M1 -->|포인터| M2
        M2 -->|포인터| M3
    end
    ARR ~~~ LIST

배열의 값 여덟 개는 미스 두 번으로 다 읽힙니다. 연결 리스트는 노드 세 개를 읽는 동안 미스가 세 번 날 수 있습니다.

프로세서는 메모리를 차례로 읽는 흐름을 알아채면 다음 라인을 미리 가져오기도 합니다. 이것을 선인출이라고 합니다. 배열을 앞에서 뒤로 훑으면 선인출이 잘 맞아서 미스가 더 줄어듭니다.

연결 리스트는 지금 노드를 읽어야 다음 노드의 주소를 압니다. 그래서 미리 가져올 곳을 정하기 어렵습니다. 포인터를 따라 한 칸씩 건너가는 이런 읽기를 포인터 추격이라고 부릅니다.

포인터로 잇는 구조

트리와 트라이도 노드를 포인터로 잇는 구조입니다. 뿌리에서 잎 쪽으로 한 단계 내려갈 때마다 다른 노드로 건너갑니다. 그때마다 캐시 미스가 날 수 있습니다. 트라이는 글자마다 노드를 하나씩 두므로 긴 문자열을 찾을수록 건너가는 횟수도 늘어납니다.

B-tree는 노드 하나에 키를 여러 개 담습니다. 노드 하나를 읽으면 비교할 키가 한꺼번에 들어옵니다. 내려가는 단계 수도 줄어듭니다. 원래는 디스크를 덜 읽으려고 만든 설계지만 캐시에도 같은 이치로 통합니다.

그래프를 담는 인접 리스트는 정점마다 이웃 목록을 하나씩 두는 방식입니다. 이 이웃 목록을 무엇으로 두느냐에 따라 캐시 지역성이 갈립니다.

동적 배열은 칸이 모자라면 더 큰 배열로 옮겨 가며 늘어나는 배열입니다. 이웃을 동적 배열에 붙여 담으면 목록을 훑을 때 캐시 라인에 딸려 온 이웃을 바로 씁니다. 연결 리스트로 담으면 이웃 하나마다 포인터를 따라가야 합니다.

반복문 순서가 바꾸는 것

구조가 같아도 읽는 순서만으로 캐시 지역성이 갈립니다. 자바의 2차원 배열 int[][] 은 행마다 따로 된 배열입니다. 한 행 안의 값은 붙어 있습니다.

아래 두 반복문은 같은 값을 같은 횟수만큼 더합니다. 오른쪽 주석은 값을 읽는 순서입니다.

int n = 1000;
int[][] g = new int[n][n];
long sum = 0;

// 행을 따라 읽는다
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        sum += g[i][j]; // [0][0] → [0][1]

// 열을 따라 읽는다
for (int j = 0; j < n; j++)
    for (int i = 0; i < n; i++)
        sum += g[i][j]; // [0][0] → [1][0]

위쪽은 한 행을 끝까지 읽고 다음 행으로 넘어갑니다. 붙어 있는 값을 차례로 읽으니 캐시 라인 하나로 값 여러 개를 읽습니다. 아래쪽은 한 열을 따라 내려가므로 값 하나를 읽을 때마다 다른 행의 배열로 건너갑니다. 다음 열로 돌아와 g[0][1] 을 읽을 무렵에는 그 사이 올라온 다른 행의 라인들에 밀려 g[0] 의 라인이 이미 축출됐기 쉽습니다.

두 코드 모두 값 n×n 개를 한 번씩 읽으니 O(n²) 입니다. 그래도 아래쪽은 캐시 미스가 훨씬 많아서 눈에 띄게 느립니다.

담는 타입도 지역성을 바꿉니다. 자바의 int[] 는 정수를 메모리에 붙여 담습니다.

ArrayList<Integer> 는 정수 객체를 가리키는 참조를 담습니다. 정수 객체는 힙 여기저기에 따로 놓일 수 있습니다. 그래서 같은 정수 목록을 훑어도 int[] 쪽이 캐시를 더 잘 탑니다.

신경 써야 할 때와 아닐 때

캐시 미스 한 번은 프로세서에게는 길지만 네트워크 왕복이나 디스크 읽기에 비하면 훨씬 짧습니다. 요청 하나가 데이터베이스와 외부 서비스를 기다리느라 시간을 쓰는 코드에서는 캐시 지역성이 응답 시간을 크게 바꾸지 못합니다. 이 성질이 드러나는 곳은 큰 데이터를 메모리에서 되풀이해 훑는 코드입니다. 대량 집계 · 정렬 · 메모리에 올린 인덱스 조회처럼 프로세서가 쉬지 않고 도는 구간이 그렇습니다.

빅오 표기법은 캐시 미스를 세지 않습니다. 복잡도가 같은 두 방법이라면 어느 쪽이 빠른지를 캐시 지역성이 가를 때가 많습니다. 복잡도가 더 나쁜 쪽이 더 빠르기도 합니다. 원소가 적을 때는 배열을 처음부터 훑는 쪽이 해시테이블 조회보다 빠른 경우도 있습니다.

지역성을 얻는 데는 대가가 따릅니다. 붙여 두는 구조는 가운데에 값을 넣거나 뺄 때 뒤쪽 값을 전부 옮겨야 합니다. 칸이 모자라면 더 큰 곳을 잡아 옮깁니다. 연결 리스트가 흩어지는 대신 얻는 것이 이 끼워 넣기의 쉬움입니다.

어느 쪽이 빠른지는 짐작보다 재 보는 편이 확실합니다. 같은 입력으로 두 방법을 벤치마크로 비교하거나 프로파일링 도구로 캐시 미스 수를 봅니다.

관련 항목

캐시 지역성이 기대는 하드웨어 부품

CPU 캐시 · 캐시 라인 · 메모리 · CPU · 레지스터 · 메모리 계층 · TLB

캐시 지역성을 설명하는 접근 경향

참조 지역성 · 공간 지역성 · 시간 지역성 · 작업 집합 · 순차 접근 · 임의 접근

캐시 지역성을 가르는 캐시 동작

캐시 히트 · 캐시 미스 · 적중률 · 축출 · 선인출

캐시 지역성이 갈리는 자료구조

배열 · 동적 배열 · 연결 리스트 · 트리 · 트라이 · B-tree · 인접 리스트 · 해시테이블 · 개방 주소법

캐시 지역성을 해치는 배치와 문제

포인터 · 포인터 추격 · 참조 · 힙 · 메모리 단편화 · 거짓 공유

캐시 미스를 세지 않는 비용 모델

시간 복잡도 · 빅오 표기법 · 공간 복잡도 · 분할 상환 분석

캐시 미스보다 훨씬 긴 대기

왕복 시간 · 디스크 · 디스크 입출력 · 지연 시간

캐시 지역성을 확인하는 측정 수단

벤치마크 · 프로파일링 · 하드웨어 성능 카운터 · 마이크로벤치마크

캐시 지역성을 살리는 설계 방식

데이터 지향 설계 · 캐시 인식 알고리즘 · 캐시 무관 알고리즘 · 루프 타일링