CS학습2026년 8월 31일

Locality: CPU 캐시가 예측하는 메모리 접근 패턴

지역성(Locality)은 프로그램이 메모리를 접근하는 패턴에 나타나는 규칙성으로, 시간 지역성(Temporal Locality)과 공간 지역성(Spatial Locality)으로 나뉜다. CPU 캐시와 가상 메모리 시스템은 이 규칙성을 전제로 설계되어 있으며, 지역성을 무시한 코드는 같은 알고리즘이라도 몇 배 이상 느려질 수 있다. 이 글에서는 캐시 계층

송민성6분 읽기

1. 개념

지역성(Locality)은 프로그램이 짧은 시간 동안 메모리 주소 공간의 좁은 영역에 집중해서 접근하는 경향을 말한다. 크게 두 가지로 나눈다.

시간 지역성(Temporal Locality): 한 번 접근한 데이터는 가까운 미래에 다시 접근될 가능성이 높다. 예를 들어 반복문 안의 카운터 변수는 매 반복마다 다시 읽힌다.
공간 지역성(Spatial Locality): 어떤 주소가 접근되면 그 주변 주소도 곧 접근될 가능성이 높다. 예를 들어 배열을 순차적으로 순회하는 경우다.

이 두 성질은 상호 배타적이지 않고 대부분의 실제 프로그램에서 함께 나타난다.

2. 왜 사용하는가

CPU 레지스터 접근은 1사이클 미만이지만, 메인 메모리(DRAM) 접근은 수백 사이클이 걸린다. 이 속도 차이를 메우기 위해 CPU와 메모리 사이에 L1/L2/L3 캐시라는 작고 빠른 저장 공간을 계층적으로 둔다.

캐시는 용량이 작기 때문에(L1 보통 32~64KB, L3 보통 수 MB) 모든 데이터를 담을 수 없다. 캐시가 효과를 내려면 "최근에 쓴 데이터, 혹은 그 근처 데이터를 다시 쓸 확률이 높다"는 지역성 가정이 성립해야 한다. 이 가정이 깨지면 캐시 적중률(hit rate)이 떨어지고 매번 메인 메모리까지 가야 하는 캐시 미스(cache miss)가 늘어난다.

3. 동작 원리

CPU가 메모리 주소를 요청하면 다음 순서로 처리된다.

L1 캐시를 먼저 확인한다. 있으면 캐시 히트(hit), 없으면 다음 단계로 간다.
L2, L3 캐시를 순서대로 확인한다.
모든 캐시에 없으면 메인 메모리에서 데이터를 가져온다.

이때 메모리에서 캐시로 데이터를 가져올 때는 필요한 1바이트만 가져오지 않고, 캐시 라인(cache line) 단위(대부분의 x86-64 시스템에서 64바이트)로 통째로 가져온다. 이것이 공간 지역성을 하드웨어 차원에서 이용하는 방식이다. 배열의 한 원소를 읽으면 그 주변 원소들도 같은 캐시 라인에 함께 올라오므로, 이어서 그 원소들을 읽을 때는 캐시 히트가 된다.

시간 지역성은 LRU(Least Recently Used)에 가까운 교체 정책으로 활용된다. 캐시가 가득 차면 가장 오래 사용되지 않은 라인을 밀어내고 새 데이터를 채운다. 최근에 쓴 데이터를 캐시에 남겨두는 것이 목표다.

가상 메모리 시스템의 페이지 캐싱과 TLB(Translation Lookaside Buffer)도 동일한 원리로 동작한다. 자주 쓰는 페이지 테이블 엔트리를 TLB에 캐싱해서 주소 변환 비용을 줄인다.

4. 코드 예제

행렬을 순회하는 순서에 따라 공간 지역성이 어떻게 달라지는지 비교한다.

python

import time
import numpy as np

N = 4000
matrix = np.random.rand(N, N)

# 1) 행 우선 순회 (row-major): 메모리 배치와 일치, 공간 지역성 높음
start = time.perf_counter()
total = 0.0
for i in range(N):
    for j in range(N):
        total += matrix[i][j]
row_major_time = time.perf_counter() - start

# 2) 열 우선 순회 (column-major): 메모리 배치와 불일치, 공간 지역성 낮음
start = time.perf_counter()
total = 0.0
for j in range(N):
    for i in range(N):
        total += matrix[i][j]
col_major_time = time.perf_counter() - start

print(f"row-major: {row_major_time:.4f}s")
print(f"col-major: {col_major_time:.4f}s")

NumPy 배열은 기본적으로 C 스타일(row-major)로 메모리에 연속 저장된다. 즉 matrix[i][j]와 matrix[i][j+1]은 메모리상 인접해 있지만, matrix[i][j]와 matrix[i+1][j]는 한 행(N개 원소) 만큼 떨어져 있다. 행 우선 순회는 캐시 라인에 올라온 데이터를 연속으로 재사용하지만, 열 우선 순회는 매번 캐시 라인을 새로 가져와야 해서 캐시 미스가 많이 발생한다.

python

# 캐시 지역성을 이용해 큰 배열 합을 빠르게 구하는 예
def sum_flat(data: list[float]) -> float:
    # 1차원 연속 배열 순회: 공간 지역성 최대 활용
    total = 0.0
    for x in data:
        total += x
    return total

5. 시간 복잡도 또는 성능 특성

지역성은 점근 시간복잡도(Big-O)를 바꾸지 않는다. 위 예제의 두 순회 방식 모두 O(N²)이다. 하지만 상수 인자(constant factor)에 미치는 영향이 매우 커서, 실제 측정 시간은 몇 배까지 차이가 날 수 있다. 구체적인 배수는 CPU 아키텍처, 캐시 크기, 데이터 크기에 따라 달라지므로 일반화된 수치를 제시하지 않고, 본인 환경에서 직접 벤치마크하는 것이 정확하다.

캐시 참조 지연 시간의 대략적인 자릿수 감각은 다음과 같다(수치는 대표적인 예시이며 하드웨어마다 다르다).

L1 캐시 접근: 1~수 나노초 수준
L2 캐시 접근: L1보다 수배 느림
L3 캐시 접근: L2보다 수배 느림
메인 메모리(DRAM) 접근: L1 대비 수십~수백 배 느림

6. 실무 사용 사례

데이터베이스 인덱스: B-Tree 인덱스는 디스크 I/O(가장 느린 계층)를 최소화하기 위해 노드 하나에 여러 키를 담아 공간 지역성을 높인다.
구조체 배열 vs 배열 구조체(AoS vs SoA): 게임 엔진이나 데이터 처리 파이프라인에서 필드 단위로 순회할 때는 SoA(Structure of Arrays)가 캐시 효율이 좋다.
이미지/행렬 처리 라이브러리: OpenCV, NumPy 내부 구현은 캐시 라인에 맞춰 블록 단위(tiling)로 연산을 나눠 처리한다.
CDN, HTTP 캐시, 브라우저 캐시: 하드웨어 캐시와 동일한 원리를 응용 계층에서 재사용한다. 최근 요청한 리소스를 다시 요청할 가능성이 높다는 시간 지역성 가정에 기반한다.
LRU 캐시 알고리즘: Redis, 데이터베이스 버퍼 풀, OS 페이지 캐시 모두 시간 지역성을 전제로 LRU 혹은 그 근사 알고리즘을 사용한다.

7. 주의할 점

지역성 최적화는 Big-O를 바꾸지 않는다. 알고리즘 자체의 복잡도가 나쁘면 지역성만으로 해결되지 않는다.
과도한 최적화는 코드 가독성을 해친다. 실제 병목이 캐시 미스에서 발생하는지 프로파일링(perf, valgrind --tool=cachegrind 등)으로 확인한 뒤 최적화하는 것이 바람직하다.
언어와 런타임에 따라 메모리 레이아웃이 다르다. Python의 리스트는 객체 포인터의 배열이라 원소 자체는 메모리상 흩어져 있을 수 있고, NumPy 배열처럼 연속된 원시 타입 배열과는 지역성 특성이 다르다.
멀티스레드 환경에서는 여러 코어가 같은 캐시 라인을 두고 경쟁하는 거짓 공유(False Sharing) 문제가 발생할 수 있다. 이는 공간 지역성을 잘못 활용했을 때 생기는 부작용이다.

8. 핵심 정리

지역성은 시간 지역성(같은 데이터 재사용)과 공간 지역성(인접 데이터 재사용)으로 나뉘며, CPU 캐시 계층과 가상 메모리는 이 규칙성을 전제로 설계되어 있다. 캐시 라인 단위로 데이터를 가져오고 LRU 방식으로 교체하는 것이 그 구현이다. 지역성은 알고리즘의 점근 복잡도를 바꾸지 않지만 실제 실행 속도의 상수 인자를 크게 좌우하므로, 데이터 접근 순서와 메모리 레이아웃을 설계할 때 의식적으로 고려할 가치가 있다.