캐시 라인

캐시 라인은 프로세서가 메모리에서 데이터를 가져올 때 한 번에 옮기는 분량을 정합니다. 값 하나만 필요해도 그 값이 든 라인 하나를 통째로 가져옵니다. 그래서 바로 옆 값을 읽을 때는 메모리까지 다시 가지 않아도 됩니다.

상세

창고에 나사 하나를 달라고 하면 직원은 나사 한 개를 집어 주지 않습니다. 나사가 든 상자를 통째로 내줍니다. 옆에 든 나사가 곧 또 필요할 테니 창고까지 다시 걸어갈 일이 줄어듭니다.

CPU(Central Processing Unit, 중앙처리장치)는 명령을 실행하는 프로세서입니다. CPU 가 다루는 명령어와 데이터는 메모리에 들어 있습니다. 메모리는 CPU 보다 훨씬 느립니다. 값 하나를 가져오는 동안 CPU 는 기다립니다. 그 시간이면 명령을 여럿 처리할 수 있습니다.

CPU 캐시는 이 기다림을 줄이려고 CPU 곁에 둔 작은 저장 장치입니다. 메모리에서 읽어 온 내용의 복사본을 들고 있습니다. 같은 내용을 다시 찾으면 메모리보다 훨씬 짧은 시간에 내줍니다.

캐시는 바이트 하나를 따로 담지 않습니다. 정해진 크기만큼 이어진 바이트를 한 묶음으로 담습니다. 가져올 때도 내보낼 때도 이 묶음째 옮깁니다. 창고의 상자에 해당하는 이 묶음이 캐시 라인입니다.

흔한 프로세서에서 라인 하나는 64바이트입니다. 4바이트 정수라면 열여섯 개가 라인 하나에 들어갑니다. 정수 배열의 첫 값을 읽으면 뒤의 값 열다섯 개가 함께 캐시에 올라옵니다.

주소를 라인 크기로 자른다

캐시는 메모리 주소를 라인 크기로 잘라 번호를 매깁니다. 라인 크기가 64바이트라면 0번부터 63번 바이트가 라인 0 이고, 64번부터 127번 바이트가 라인 1 입니다. 라인은 언제나 라인 크기의 배수가 되는 주소에서 시작합니다.

CPU 가 주소 70 의 값을 읽으면 70 이 든 라인 1 이 캐시로 들어옵니다. 원한 것은 값 하나지만 들어오는 것은 64바이트 전부입니다.

flowchart TD
    R["CPU 가 주소 70 을 읽는다"] --> a1
    subgraph M["메모리 · 64바이트씩 자른 라인"]
        a0["라인 0 · 주소 0 ~ 63"]
        a1["라인 1 · 주소 64 ~ 127"]
        a2["라인 2 · 주소 128 ~ 191"]
    end
    a1 --> C["CPU 캐시 · 라인 1 의 64바이트가 들어온다"]

주소 하나가 어느 라인에 드는지는 나눗셈 한 번으로 나옵니다. 아래 코드는 주소 70 을 넣어 본 것입니다.

long addr = 70;
long line = addr / 64;     // 1
long start = line * 64;    // 64
long offset = addr % 64;   // 6

몫이 라인 번호입니다. 나머지는 라인 안에서의 위치입니다.

라인 크기는 2의 거듭제곱으로 잡습니다. 그래서 하드웨어는 나눗셈 대신 주소의 아래쪽 비트를 떼어 내 이 계산을 끝냅니다. 64는 2의 6제곱이라서, 64바이트 라인이면 주소의 아래 6비트가 곧 라인 안의 위치입니다.

라인 경계에 걸친 값

값 하나가 라인 둘에 걸칠 수도 있습니다. 8바이트 값이 주소 60 에서 시작하면 앞 4바이트는 라인 0 에, 뒤 4바이트는 라인 1 에 놓입니다. 이 값 하나를 읽으려고 라인 둘을 가져와야 합니다.

컴파일러와 런타임은 이런 일을 피하려고 값을 제 크기의 배수 주소에 놓습니다. 이렇게 놓는 규칙을 정렬이라고 합니다. 8바이트 값을 8의 배수 주소에 놓으면 64바이트 라인의 경계를 넘지 않습니다.

묶음으로 옮기는 세 가지 이유

첫째는 메모리에 다녀오는 비용의 생김새입니다. 요청을 보내고 첫 바이트를 받기까지가 오래 걸립니다. 첫 바이트가 온 뒤 이어진 바이트를 더 받는 데는 시간이 조금만 더 듭니다. 한 번 갈 때 넉넉히 받아 오는 쪽이 남습니다.

둘째는 프로그램이 메모리를 읽는 버릇입니다. 방금 읽은 값의 바로 옆을 곧이어 읽는 일이 흔합니다. 배열을 앞에서 뒤로 훑거나 객체의 필드를 차례로 읽을 때가 그렇습니다. 이 성질을 공간 지역성이라고 합니다. 라인은 이 성질에 기대어 이웃을 미리 실어 옵니다.

셋째는 캐시가 무엇을 담았는지 적어 두는 비용입니다. 캐시는 담은 데이터마다 그것이 메모리의 어느 주소 것인지 표시를 붙여 둬야 합니다. 이 표시를 캐시 태그라고 합니다. 바이트마다 태그를 붙이면 태그가 데이터보다 커집니다. 라인마다 하나씩 붙이면 그 부담이 작아집니다.

라인이 크면 생기는 손해

라인을 키우면 한 번에 더 많이 실어 옵니다. 배열을 차례로 훑는 코드는 그만큼 덜 기다립니다. 여기저기 흩어진 값을 하나씩 읽는 코드는 반대입니다. 라인에서 한두 바이트만 씁니다. 나머지는 버립니다.

캐시 크기는 정해져 있어서 라인이 커지면 캐시에 들어가는 라인 수가 줄어듭니다. 멀리 떨어진 데이터 여럿을 오래 쥐고 있어야 하는 프로그램은 라인을 더 자주 내보내고 다시 가져옵니다. 라인 크기는 이 두 손해 사이에서 고른 값입니다.

라인을 담는 캐시 칸

지금까지 라인은 메모리 주소를 64바이트씩 자른 구간이었습니다. 캐시 쪽에는 이 라인을 하나씩 담는 칸이 있습니다. 이 절은 그 칸이 라인 말고 무엇을 더 들고 있는지 봅니다.

캐시의 칸은 메모리의 라인보다 훨씬 적습니다. 그래서 한 칸에 이 라인 저 라인이 번갈아 들어옵니다. 칸마다 지금 어느 라인을 담았는지 적어 두어야 하는 까닭입니다.

값을 쓸 때도 캐시가 먼저 받습니다. 많은 캐시는 칸에 든 라인만 먼저 고쳐 둡니다. 메모리에는 그 라인을 칸에서 내보낼 때 적습니다.

그래서 칸마다 64바이트 데이터 말고도 작은 표시 몇 개를 같이 둡니다. 캐시는 이 표시를 보고 라인을 찾고 채우고 내보냅니다.

찾는 주소의 라인이 어느 칸에 들어 있으면 캐시 히트입니다. 캐시가 그 칸에서 바로 값을 내줍니다. 어느 칸에도 없으면 캐시 미스입니다. 이때는 메모리에서 라인 하나를 가져와 칸에 채웁니다.

빈 칸이 없으면 들어 있던 라인 하나를 먼저 내보내야 새 라인이 들어섭니다. 이 일이 축출입니다. 내보낼 라인의 더티 비트가 켜져 있으면 그 라인을 메모리에 먼저 적습니다.

코어 사이를 오가는 단위

요즘 CPU 한 개에는 명령을 실행하는 단위가 여럿 들어 있습니다. 그 단위 하나를 코어라고 합니다. 코어마다 자기 캐시를 따로 들고 있어서, 같은 라인의 복사본이 여러 캐시에 동시에 있을 수 있습니다.

한 코어가 그 라인의 값을 고치면 다른 코어가 든 복사본은 낡은 값이 됩니다. 그래서 하드웨어는 나머지 코어의 복사본을 무효로 만듭니다. 복사본끼리 이렇게 맞추는 규칙을 캐시 일관성이라고 합니다. 이 규칙도 라인 단위로 돕니다.

라인 단위라는 점이 뜻밖의 느려짐을 부릅니다. 스레드 둘이 서로 다른 변수 x 와 y 를 고친다고 해 봅니다. 두 변수는 한 라인에 들어 있습니다. 두 스레드가 서로 다른 코어에서 돌면 아래처럼 됩니다.

sequenceDiagram
    participant A as 코어 1 · x 를 고친다
    participant B as 코어 2 · y 를 고친다
    Note over A,B: x 와 y 가 한 라인에 들어 있다
    A->>B: x 를 고쳤다 · 네 복사본은 무효
    B->>A: 그 라인을 다시 보내 달라
    A->>B: 라인을 보낸다
    B->>A: y 를 고쳤다 · 네 복사본은 무효
    A->>B: 그 라인을 다시 보내 달라
    B->>A: 라인을 보낸다
    Note over A,B: 고칠 때마다 되풀이된다

두 스레드는 서로의 변수를 건드린 적이 없습니다. 그런데도 한쪽이 고칠 때마다 다른 쪽 복사본이 무효가 됩니다. 라인은 두 코어 사이를 계속 오갑니다. 이 현상을 거짓 공유라고 합니다.

거짓 공유는 두 변수를 서로 다른 라인에 떼어 놓으면 풀립니다. 두 변수 사이에 빈 바이트를 끼워 넣어 거리를 벌리는 식입니다. 패딩은 이렇게 끼우는 빈 바이트입니다.

데이터 배치가 라인을 쓰는 방식

백엔드 코드에서 캐시 라인을 직접 부르는 일은 없습니다. 대신 데이터를 메모리에 어떻게 놓느냐가 라인 하나에 쓸모 있는 값이 몇 개 드는지를 정합니다.

배열은 값을 이어서 놓습니다. 정수 배열을 앞에서 뒤로 훑으면 라인 하나를 가져올 때마다 그 안의 정수 열여섯 개를 남김없이 씁니다.

연결 리스트는 노드를 메모리 여기저기에 흩어 놓습니다. 다음 노드로 넘어갈 때마다 다른 라인을 가져와야 할 수 있습니다. 가져온 라인에서 쓰는 것은 노드 하나뿐입니다. 나머지 바이트는 버립니다.

두 구조가 같은 값을 담아도 훑는 데 걸리는 시간은 크게 갈립니다. 계산하는 양은 같습니다. 메모리에 다녀오는 횟수가 다를 뿐입니다.

신경 쓸 때와 잊어도 될 때

캐시 라인은 켜고 끄는 설정이 아닙니다. 프로그램이 도는 내내 하드웨어가 이 단위로 움직입니다. 그래서 대부분의 코드는 라인을 몰라도 제대로 돕니다.

따져 볼 만한 때는 둘입니다. 많은 데이터를 되풀이해 훑는 일이 전체 시간의 큰 몫을 차지할 때가 하나입니다. 여러 스레드가 이웃한 변수를 쉴 새 없이 고칠 때가 또 하나입니다.

요청마다 데이터베이스나 네트워크를 기다리는 서비스라면 기다리는 시간이 훨씬 큽니다. 라인을 따져서 줄어드는 시간이 눈에 잘 안 띕니다.

라인 크기는 프로세서마다 다를 수 있습니다. 64바이트라고 못 박아 짠 코드는 라인 크기가 다른 프로세서에서 기대한 효과를 못 낼 수 있습니다.

관련 항목

캐시 라인을 담고 옮기는 저장 장치

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

캐시 라인에 붙는 표시

캐시 태그 · 유효 비트 · 더티 비트 · MESI

캐시 라인과 나란히 쓰이는 데이터 크기 단위

바이트 · 워드 · 페이지 · 블록 · 섹터

캐시 라인이 기대는 프로그램의 성질

참조 지역성 · 공간 지역성 · 시간 지역성 · 선인출 · 순차 접근

캐시 라인을 찾고 채우고 내보내는 과정

캐시 히트 · 캐시 미스 · 축출 · 집합 연관 · 직접 사상 · write-back · write-through

캐시 라인 단위로 도는 다중 코어 규칙과 그 부작용

캐시 일관성 · 거짓 공유 · 캐시 핑퐁 · 코어 · 멀티코어 · 스레드

캐시 라인을 의식해 고르는 데이터 배치

배열 · 연결 리스트 · 구조체 · 정렬 · 패딩 · 데이터 지향 설계

캐시 라인과 함께 주소를 다루는 장치

TLB · MMU · 가상 메모리 · 물리 주소 · CPU