CPU를 화나게 만드는 데이터 접근 패턴: 같은 합산 루프가 16배 느려지는 이유
실무에서 "이 함수 왜 이렇게 느려?"를 파다 보면 결국 메모리 접근 패턴 문제로 귀결되는 경우가 정말 많다. 알고리즘 복잡도는 똑같은데 실측 시간이 10배씩 차이 나는 일이 흔하다. 최근 GeekNews에 올라온 글이 이걸 아주 극단적으로 보여줬다. 똑같은 정수 합산 루프에서 데이터 자체는 그대로 두고 접근 순서(순열)만 바꿨더니, 선형 접근 1.33억 사이클 vs 무작위 접근 15.7억 사이클로 10배 이상 벌어졌고, 더 나아가 무작위보다 33% 더 느린 패턴까지 의도적으로 만들어냈다는 내용이다.
이게 단순 호기심 실험이 아니라 우리가 매일 만지는 코드와 직결된다. 연결 리스트 순회, 해시맵 조회, 2차원 배열 행/열 순회, DB 인덱스 스캔까지 전부 같은 원리 위에 있다. 이번 글에서는 원문 실험을 따라가며 왜 이런 차이가 나는지 하드웨어 동작으로 풀어보고, 실무에서 어떻게 적용할지 정리한다.
1. 도입: 왜 접근 순서가 성능을 지배하는가
먼저 숫자부터 보자. 원문 실험은 Intel Core Ultra 7 268V 머신에서 2^26개(약 6700만 개)의 uint32_t를 합산하면서, positions 배열의 순서만 바꿔 측정했다. rdtsc 사이클 카운트 기준이다.
linear : 132,752,394
fisher_yates_shuffle (무작위) : 1,572,108,618
separated_by_a_cacheline (캐시라인 간격) : 718,804,156
separated_by_a_page (페이지 간격) : 1,411,153,154
separated_by_a_page_and_cacheline : 1,408,519,172
stride=8 pages_and_cacheline : 2,058,425,640
stride bank_conflicts_and_cacheline : 2,082,308,014데이터 양도 같고, 더하는 연산 횟수도 같고, 누산 함수 코드도 한 글자 안 바뀌었다. 오직 "몇 번째 원소를 언제 읽느냐"만 달라졌는데 16배 차이가 난다. CPU 입장에서는 같은 일을 시켰는데 어떤 순서는 빠르게 처리하고 어떤 순서는 미친 듯이 답답해한다는 뜻이다. 이걸 이해하려면 캐시 계층을 알아야 한다.
2. 핵심: 캐시 구조와 접근 패턴이 만나는 지점
L1/L2/L3와 캐시 라인
CPU는 DRAM을 직접 읽으면 너무 느리니까 중간에 캐시를 둔다. 코어 가까운 순서로 L1, L2, L3가 있고, 멀어질수록 용량은 크지만 느리다. 원문 머신 기준:
- L1d(데이터): 코어당 48KB, 12-way, 64 set
- L2: 코어당 약 2.5MB
- L3: 12MB 공유
핵심은 캐시가 바이트 단위가 아니라 캐시 라인(보통 64바이트) 단위로 움직인다는 점이다. uint32_t 하나(4바이트)를 읽으려고 메모리에 접근하면, CPU는 그 4바이트만 가져오는 게 아니라 64바이트 라인 전체를 통째로 끌어온다. 즉 정수 16개가 한 번에 캐시로 올라온다.
그래서 선형 접근이 빠르다. data[0]을 읽는 순간 data[0]~data[15]가 캐시에 들어와 있고, 다음 15번의 접근은 메모리까지 안 가도 된다. 비유하자면 도서관에서 책 한 권 빌리러 가면서 같은 책장의 책 16권을 한꺼번에 들고 오는 것과 같다. 어차피 차례대로 읽을 거면 엄청 효율적이다.
프리페처: CPU의 패턴 예측기
여기에 더해 하드웨어 프리페처가 있다. CPU가 "얘가 0, 64, 128, 192바이트를 순서대로 읽네? 다음은 256이겠군" 하고 미리 캐시에 당겨놓는다. 선형 접근이 압도적으로 빠른 진짜 이유가 이거다. 메모리 지연이 연산 뒤에 숨어버린다.
무작위 접근은 이 두 가지가 다 무너진다. 매번 다른 캐시 라인을 건드리니 라인 안의 나머지 15개는 버려지고, 다음 위치를 예측할 수 없으니 프리페처도 무력하다. 매 접근이 캐시 미스가 되고 DRAM 지연(수백 사이클)을 그대로 맞는다. 원문에서 10배 차이가 여기서 나온다.
무작위보다 더 나쁜 패턴 만들기
원문이 흥미로운 건 "무작위보다 나쁜 순열"을 의도적으로 만든 부분이다. 핵심 아이디어 세 가지만 정리하면:
- 집합 연관 캐시 악용: L1d가 64 set × 12 way 구조라, 주소 A와 A+4096은 같은 set에 매핑된다(4096 = 64 set × 64B). 페이지 단위(4096B) stride로 접근하면 같은 set만 계속 두드리게 되고, set당 12 way밖에 없으니 13번째부터는 기존 라인을 쫓아낸다. 48KB 캐시인데 실제로 쓰는 용량은 12 × 64B = 768B뿐이 되는 셈이다.
- PTE 캐시 라인까지 파괴: 가상 주소를 물리 주소로 바꾸는 PTE는 8바이트라 캐시 라인 하나에 8개가 들어간다. 페이지 stride를 8로 두면 PTE 지역성까지 깨져서 데이터뿐 아니라 주소 변환 캐시 라인도 매번 새로 가져온다. 그래서 stride=8에서 20.6억 사이클이라는 피크가 나왔다.
- DRAM bank/row 충돌: 같은 bank의 다른 row를 번갈아 치면 precharge + activation이 매번 발생해 DRAM 응답이 느려진다. 다만 물리 주소 → DRAM 매핑이 플랫폼 의존적이라 완전 통제는 어렵고, 원문도 근사치(20.8억 사이클)만 얻었다.
실무자가 외울 필요는 없다. 핵심 교훈은 하나다. 접근 거리가 멀어질수록(재사용 거리가 커질수록) 캐시는 무용지물이 된다.
3. 실무 관점: 어디서 만나고 어떻게 피하는가
직접 재현해보기 (벤치마크 코드)
원리를 체감하려면 직접 돌려보는 게 최고다. 행/열 우선 순회 차이를 보여주는 간단한 C 예제를 준비했다. 같은 2차원 배열을 행 우선과 열 우선으로 합산한다.
// access.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 8192
static int *m;
double now() {
struct timespec t;
clock_gettime(CLOCK_MONOTONIC, &t);
return t.tv_sec + t.tv_nsec / 1e9;
}
int main() {
m = malloc((size_t)N * N * sizeof(int));
for (size_t i = 0; i < (size_t)N * N; i++) m[i] = 1;
// 행 우선: 메모리 연속 접근 (캐시 친화적)
double t0 = now();
long long sum1 = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum1 += m[(size_t)i * N + j];
double t1 = now();
// 열 우선: N칸씩 건너뜀 (캐시 미스 폭발)
long long sum2 = 0;
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum2 += m[(size_t)i * N + j];
double t2 = now();
printf("row-major : %.3f s (sum=%lld)\n", t1 - t0, sum1);
printf("col-major : %.3f s (sum=%lld)\n", t2 - t1, sum2);
free(m);
return 0;
}빌드하고 실행한다. 출력은 머신마다 다르지만 내 노트북(x86_64) 기준 이런 식으로 나온다.
$ gcc -O2 access.c -o access
$ ./access
row-major : 0.071 s (sum=67108864)
col-major : 0.512 s (sum=67108864)결과 합은 똑같은데(67108864 = 8192×8192) 시간은 7배 넘게 차이 난다. 열 우선 순회는 매 접근마다 N × 4 = 32KB씩 건너뛰니 캐시 라인을 거의 재사용하지 못한다. 원문의 "page stride 접근"과 본질적으로 같은 함정이다. 행렬 연산, 이미지 처리, 텐서 다루는 코드에서 인덱스 순서 한 번 잘못 짜면 이게 그대로 터진다.
perf로 캐시 미스 눈으로 확인하기
"느린 건 알겠는데 진짜 캐시 미스 때문이야?"를 증명하려면 측정해야 한다. Linux에서는 perf가 표준이다.
$ perf stat -e cache-references,cache-misses,L1-dcache-load-misses ./access
row-major : 0.070 s (sum=67108864)
col-major : 0.509 s (sum=67108864)
Performance counter stats for './access':
145,332,118 cache-references
18,442,901 cache-misses # 12.69 % of all cache refs
210,558,334 L1-dcache-load-misses
0.612 seconds time elapsed열 우선 구간에서 L1 d-cache load miss가 폭증하는 게 보인다. 두 루프를 분리해서 따로 측정하면 차이가 더 명확하다.
흔한 함정 1: perf 권한 에러
perf 처음 돌리면 십중팔구 이 에러부터 만난다.
$ perf stat ./access
Error:
Access to performance monitoring and observability operations is limited.
Consider adjusting /proc/sys/kernel/perf_event_paranoid setting to open
access to performance monitoring and observability operations for processes
without CAP_PERFMON, CAP_SYS_PTRACE or CAP_SYS_ADMIN Linux capability.해결은 커널 파라미터 조정이다. 개발 머신이면 임시로 낮춰서 쓴다(운영 서버는 보안 정책 확인 필수).
$ sudo sysctl -w kernel.perf_event_paranoid=1
kernel.perf_event_paranoid = 1컨테이너 안에서 돌릴 때는 추가로 cache-misses 같은 하드웨어 이벤트가 막혀 있을 수 있다. 그 경우 이런 메시지가 뜬다.
<not supported> cache-misses이건 가상화 환경(특히 클라우드 VM이나 컨테이너)에서 PMU 카운터가 노출 안 될 때 나온다. 베어메탈이나 PMU를 패스스루한 환경에서 측정해야 한다. 클라우드에서 캐시 단위 프로파일링이 안 되는 건 꽤 자주 겪는 한계다.
흔한 함정 2: AoS와 SoA 선택
실무에서 가장 자주 만나는 게 구조체 배열 설계다. 객체 지향적으로 짜면 자연스럽게 AoS(Array of Structures)가 된다.
// AoS - 객체 하나가 메모리에 뭉쳐 있음
struct Particle { float x, y, z; float vx, vy, vz; int id; ... };
struct Particle particles[N];
// x좌표만 전부 합산하려는데...
for (int i = 0; i < N; i++) sum += particles[i].x;x만 필요한데 캐시 라인에는 y, z, vx... id까지 딸려 온다. 필요한 4바이트 쓰자고 라인 64바이트 중 대부분을 낭비한다. 특정 필드만 대량 순회하는 패턴이면 SoA(Structure of Arrays)가 유리하다.
// SoA - 같은 필드끼리 모음
struct Particles {
float x[N], y[N], z[N];
float vx[N], vy[N], vz[N];
int id[N];
};
// x[]가 연속이라 캐시 라인 낭비 없음 + 벡터화도 잘 먹음
for (int i = 0; i < N; i++) sum += p.x[i];트레이드오프가 분명하다. SoA는 "필드별 대량 처리"에 강하지만, "객체 하나의 모든 필드 접근"이 잦으면 오히려 AoS가 낫다. 게임 엔진, 시뮬레이션, 컬럼 지향 DB가 SoA를 택하는 이유고, 일반 비즈니스 로직은 보통 AoS가 무난하다. 무조건 SoA가 답이 아니다. 접근 패턴을 보고 정해야 한다.
실무에서 만나는 다른 나쁜 패턴들
- 연결 리스트 순회: 노드가 힙 여기저기 흩어져 있어 next 따라가는 게 사실상 무작위 접근이다. 원소 수가 많으면 배열/벡터로 바꾸는 것만으로 몇 배 빨라진다. "삽입/삭제가 O(1)이라 리스트가 빠르다"는 교과서 논리가 실측에서 자주 깨지는 이유다.
- 해시맵 대량 순회: 해시맵은 키 조회 한 방엔 강하지만, 전체를 순회하면 버킷이 흩어져 있어 캐시 효율이 나쁘다. 순회가 핫패스면 정렬된 배열이나 별도 인덱스를 두는 게 낫다.
- DB 인덱스 스캔 vs 시퀀셜 스캔: 옵티마이저가 인덱스를 안 타고 풀스캔을 택하는 게 비합리적으로 보일 때가 있는데, 넓은 범위를 읽을 땐 디스크/페이지의 순차 접근이 랜덤 인덱스 점프보다 빠르기 때문이다. 이것도 결국 같은 지역성 원리다.
대안: 루프 타일링(블로킹)
행렬 곱처럼 큰 데이터를 반복 접근하는 경우, 캐시에 들어갈 만한 작은 블록 단위로 쪼개서 처리하면 재사용 거리가 줄어 캐시 히트가 올라간다. 다만 블록 크기 튜닝이 머신 의존적이고 코드가 복잡해지니, 직접 짜기보다 BLAS 같은 검증된 라이브러리나 컴파일러 최적화를 먼저 쓰는 걸 권한다.
4. 정리
한 줄 요약: 알고리즘이 같아도 메모리 접근 순서가 성능을 지배한다. 가능하면 데이터를 연속으로, 순차적으로 읽어라. CPU와 프리페처가 알아서 빠르게 만들어준다.
누가 언제 신경 써야 하나:
- 대량 데이터를 반복 순회하는 핫패스를 가진 사람(배치 처리, 데이터 파이프라인, 게임/시뮬레이션, 수치 연산) → 무조건 본다.
- "복잡도는 같은데 왜 느리지?"를 디버깅 중인 사람 →
perf stat으로 cache-miss부터 찍어봐라. - 일반 CRUD 웹 백엔드 → 대부분 네트워크/DB가 병목이라 우선순위가 낮다. 단, 직렬화 포맷이나 in-memory 캐시 자료구조를 설계할 땐 알아두면 좋다.
마지막으로 강조하고 싶은 건 측정 없는 최적화는 하지 말라는 거다. 원문도 결국 rdtsc로 실측했고, 우리도 perf로 확인했다. SoA 같은 패턴은 가독성을 희생하니, 진짜 병목으로 확인된 곳에만 적용하는 게 맞다.