이상적으로는 모든 데이터를 레지스터처럼 빠른 곳에 두고 싶다. 하지만 빠른 메모리는 비싸고 칩 면적을 많이 먹어서 용량이 작을 수밖에 없다. 그래서 컴퓨터는 레지스터 → 캐시 → RAM → 디스크로 갈수록 느려지지만 커지는 계층을 쌓는다.

문제는 이거다 — 캐시가 전체 메모리의 1% 미만인 경우도 흔한데, 그 1%에 "지금 필요한 데이터"가 들어있을 확률이 왜 이렇게 높을까? 정답: 프로그램은 메모리를 균등하게 건드리지 않는다. 방금 쓴 변수를 또 쓰고, 배열은 순서대로 훑고, 함수는 정해진 코드 블록을 반복 실행한다. 이 편향에는 이름이 두 개 붙어 있다 — 시간 지역성과 공간 지역성. 캐시는 이 두 가지 편향에 통째로 베팅한 하드웨어다.

"최근에 접근한 데이터는 곧 다시 접근될 가능성이 높다." 반복문 안의 카운터, 합계를 누적하는 변수, 재귀 호출의 스택 프레임이 대표적이다. 아래 합계 계산 코드를 한 줄씩 재생해 보면, 변수 합계와 i가 매 반복마다 계속 재사용되는 게 보인다 — 이 두 변수는 한 번 레지스터/캐시에 올라가면 반복문이 끝날 때까지 계속 히트한다.

"한 번 접근한 데이터 근처의 데이터도 곧 접근될 가능성이 높다." 배열을 순서대로 훑는 게 대표적이다. 캐시는 이 편향을 이용해서 바이트 하나가 아니라 블록(캐시 라인) 단위로 메모리를 통째로 가져온다 — 아래 그리드에서 4칸씩 구분선이 캐시 라인 경계다.

16개 블록짜리 배열과 4줄짜리 작은 캐시를 두고, 순차 접근과 무작위 접근을 각각 20번 재생해서 히트율을 직접 비교해 보자. 캐시가 작아도(전체의 25%) 접근 패턴이 좋으면 히트율이 압도적으로 높다는 게 눈으로 보일 것이다.

2차원 배열은 메모리에 1차원으로 한 줄씩 이어 붙여 저장된다(행 우선 저장, row-major). 그래서 행 방향으로 순회하면 주소가 계속 이어지지만(공간 지역성 ↑), 열 방향으로 순회하면 매번 한 행 전체 너비만큼 점프한다(공간 지역성 ↓).

# 빠름: 행 우선 — 메모리 상 연속된 주소를 그대로 따라감
for i in range(N):
    for j in range(N):
        total += matrix[i][j]   # 캐시 라인 하나로 여러 번 히트

# 느림: 열 우선 — 매 접근이 한 행 너비(N칸)만큼 점프
for j in range(N):
    for i in range(N):
        total += matrix[i][j]   # 매번 새 캐시 라인 → 미스 폭증