예전에 이상한 경험을 했다.
똑같은 알고리즘인데 실행 속도가 10배 차이 났다.
한 번은 0.1초, 한 번은 1초.
코드는 똑같았다.
컴파일러도 같았다.
CPU도 같았다.
대체 뭐가 문제일까?
답은 “데이터 접근 순서”였다.
배열을 가로로 읽느냐, 세로로 읽느냐의 차이였다.
그때 처음으로 캐시 메모리에 대해 찾아봤다.
CPU와 RAM 사이에는 엄청난 속도 차이가 있다.
CPU는 1사이클에 여러 연산을 한다.
RAM은 수백 사이클이 걸려서야 데이터를 가져온다.
이 격차를 메우기 위해 등장한 게 캐시다.
캐시는 CPU와 RAM 사이의 “임시 저장소”다.
자주 쓰는 데이터를 여기에 미리 가져다 놓는다.
그러면 CPU가 RAM까지 갈 필요 없이 캐시에서 바로 가져온다.
엄청나게 빠르다.
캐시는 3단계로 나뉜다.
L1 캐시
CPU 코어에 붙어 있다.
가장 빠르다.
1-2 사이클이면 접근한다.
하지만 용량이 작다.
보통 32-64KB 정도.
L2 캐시
L1보다 느리지만 더 크다.
10-20 사이클 정도.
용량은 256KB-512KB.
코어마다 하나씩 있다.
L3 캐시
가장 느리지만 가장 크다.
40-75 사이클.
용량은 수 MB에서 수십 MB.
모든 코어가 공유한다.
RAM
캐시에 없으면 여기까지 간다.
수백 사이클.
용량은 GB 단위.
엄청나게 느리다.
시간으로 환산하면 이렇다.
L1 캐시: 1초
L2 캐시: 10초
L3 캐시: 40초
RAM: 5분
SSD: 1시간
HDD: 1주일
만약 CPU가 데이터를 기다리는 시간을 사람 시간으로 바꾸면 이렇다.
L1에서 가져오면 1초.
RAM에서 가져오면 5분.
HDD에서 가져오면 1주일을 기다려야 한다.
이 차이가 얼마나 큰지 느껴지는가?
그래서 캐시가 중요하다.
CPU가 데이터를 찾는다.
L1 캐시를 본다.
있으면? 캐시 히트.
없으면? 캐시 미스.
L2로 간다.
있으면? 히트.
없으면? 미스.
L3로 간다.
있으면? 히트.
없으면? 미스.
결국 RAM까지 간다.
여기는 반드시 있다.
하지만 엄청 느리다.
캐시 히트율이 99%라고 해보자.
100번 중 99번은 L1에서 찾는다.
1번만 RAM까지 간다.
평균 시간은 얼마나 될까?
평균 시간 = (99 × 1사이클) + (1 × 200사이클)
= 99 + 200
= 299사이클
100번 접근에 약 300사이클.
한 번당 3사이클 정도.
이제 히트율이 98%로 떨어졌다고 해보자.
고작 1% 차이다.
평균 시간 = (98 × 1사이클) + (2 × 200사이클)
= 98 + 400
= 498사이클
한 번당 5사이클.
1% 차이로 속도가 1.66배 느려졌다.
히트율이 95%면?
평균 시간 = (95 × 1사이클) + (5 × 200사이클)
= 95 + 1000
= 1095사이클
한 번당 11사이클.
4% 차이로 속도가 3.7배 느려졌다.
이게 캐시 히트율의 위력이다.
캐시는 작다.
모든 데이터를 담을 수 없다.
그래서 선택해야 한다.
뭘 캐시에 남기고, 뭘 버릴까?
1. Compulsory Miss (최초 접근)
처음 접근하는 데이터는 당연히 캐시에 없다.
이건 어쩔 수 없다.
2. Capacity Miss (용량 부족)
캐시가 꽉 차서 데이터를 버렸다.
나중에 다시 필요해서 찾는다.
없다.
RAM에서 다시 가져온다.
3. Conflict Miss (충돌)
캐시 구조상 같은 자리를 놓고 데이터들이 싸운다.
한 데이터가 들어오면 다른 데이터가 밀려난다.
교대로 쫓겨나며 계속 미스가 난다.
이게 가장 안타깝다.
2차원 배열이 있다.
int arr[1000][1000];
방법 1: 가로로 읽기
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
sum += arr[i][j];
}
}
방법 2: 세로로 읽기
for (int j = 0; j < 1000; j++) {
for (int i = 0; i < 1000; i++) {
sum += arr[i][j];
}
}
둘의 속도 차이는 10배가 날 수 있다.
왜 그럴까?
메모리는 1차원이다.
2차원 배열도 결국 1차원으로 저장된다.
C 언어는 “행 우선 순서”로 저장한다.
arr[0][0], arr[0][1], arr[0][2], ...
arr[1][0], arr[1][1], arr[1][2], ...
한 행이 메모리에 연속으로 붙어 있다.
캐시는 메모리를 “블록” 단위로 가져온다.
보통 64바이트 정도.
arr[0][0]을 읽으면?
캐시는 arr[0][0]부터 arr[0][15]까지 한꺼번에 가져온다.
그러면 다음에 arr[0][1]을 읽을 때 이미 캐시에 있다.
히트!
arr[0][2]도 히트!
한 번 RAM 접근으로 16개를 읽는다.
효율적이다.
arr[0][0]을 읽는다.
캐시는 arr[0][0]부터 arr[0][15]까지 가져온다.
다음에 arr[1][0]을 읽는다.
이건 다른 행이다.
캐시에 없을 가능성이 크다.
미스!
RAM에서 arr[1][0]부터 arr[1][15]까지 가져온다.
arr[0][1]부터 arr[0][15]는?
안 쓰고 버린다.
다음에 arr[2][0]을 읽는다.
또 미스!
매번 RAM을 간다.
엄청나게 느리다.
1. 순차 접근하기
메모리를 순서대로 읽어라.
점프하지 마라.
연속된 메모리는 캐시가 알아서 가져온다.
2. 작은 데이터 구조 사용하기
크기가 작으면 캐시에 더 많이 들어간다.
// 나쁜 예
struct Data {
int value;
char padding[60]; // 낭비
};
// 좋은 예
struct Data {
int value;
};
3. 자주 쓰는 데이터 모으기
관련 데이터를 가까이 두어라.
// 나쁜 예
struct Player {
int x;
char name[100]; // 자주 안 씀
int y;
char description[500]; // 자주 안 씀
};
// 좋은 예
struct Player {
int x;
int y;
// 자주 쓰는 것만 여기
};
4. 루프 타일링
큰 배열을 작은 블록으로 나눠서 처리해라.
// 나쁜 예
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 10000; j++) {
// 캐시가 모든 행을 담기 어려움
}
}
// 좋은 예
for (int ii = 0; ii < 10000; ii += 64) {
for (int jj = 0; jj < 10000; jj += 64) {
for (int i = ii; i < ii + 64; i++) {
for (int j = jj; j < jj + 64; j++) {
// 64x64 블록은 캐시에 들어감
}
}
}
}
멀티스레드 환경에서 조심해야 할 게 있다.
struct Counter {
int count1; // 스레드 1이 씀
int count2; // 스레드 2가 씀
};
두 변수는 독립적이다.
하지만 같은 캐시 라인에 있다.
스레드 1이 count1을 수정한다.
캐시 일관성 때문에 다른 코어의 캐시가 무효화된다.
스레드 2의 캐시에 있던 count2도 날아간다.
스레드 2가 count2를 읽는다.
미스!
다시 가져온다.
스레드 2가 count2를 수정한다.
스레드 1의 count1이 무효화된다.
서로 방해한다.
이게 False Sharing이다.
해결법: 패딩 추가
struct Counter {
int count1;
char padding[60]; // 캐시 라인 분리
int count2;
};
이제 다른 캐시 라인에 들어간다.
서로 방해하지 않는다.
추측하지 말고 측정해라.
리눅스에서는 perf를 쓸 수 있다.
perf stat -e cache-misses,cache-references ./myprogram
캐시 미스율이 나온다.
5% 이하면 좋은 거다.
20% 넘으면 문제가 있다.
코드를 다시 봐야 한다.
간단한 행렬 곱셈 예제.
캐시 비친화적 코드
// 세로로 접근
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
C[i][j] += A[i][k] * B[k][j]; // B를 세로로 읽음
1000x1000 행렬: 8초
캐시 친화적 코드
// 루프 순서 변경
for (int i = 0; i < N; i++)
for (int k = 0; k < N; k++)
for (int j = 0; j < N; j++)
C[i][j] += A[i][k] * B[k][j]; // B를 가로로 읽음
1000x1000 행렬: 0.8초
10배 차이.
알고리즘은 똑같다.
단지 순서만 바꿨을 뿐이다.
데이터베이스도 똑같은 원리다.
자주 쓰는 데이터를 메모리에 캐싱한다.
그래서 인덱스가 중요하다.
인덱스는 캐시에 들어갈 만큼 작아야 한다.
자주 조회하는 컬럼에 인덱스를 건다.
캐시 히트율이 올라간다.
쿼리가 빨라진다.
브라우저 캐시, CDN 캐시, API 캐시.
모두 같은 원리다.
자주 쓰는 걸 가까이 둔다.
멀리서 가져오는 비용을 줄인다.
HTTP 헤더로 캐시를 제어한다.
Cache-Control, ETag.
캐시 히트율이 올라가면 서버 부하가 줄고 응답이 빨라진다.
캐시는 보이지 않는다.
하지만 성능에 엄청난 영향을 준다.
히트율 1% 차이가 몇 배 속도 차이를 만든다.
같은 알고리즘도 데이터 접근 패턴에 따라 10배 차이가 난다.
캐시를 이해하면 더 빠른 코드를 짤 수 있다.
순차 접근, 작은 자료구조, 지역성.
이 원칙만 지켜도 많이 빨라진다.
다음번에 코드 최적화할 때 기억하자.
“캐시가 좋아할까?”
이 질문 하나면 충분하다.