메모리 지역성: 캐시와 가상 메모리 성능을 좌우하는 접근 패턴

메모리 참조가 한곳에 모이는 이유

프로그램은 실행 중 모든 메모리를 균등하게 사용하지 않는다. 일정 시간에는 일부 코드와 데이터에 참조가 집중되고, 그 주변 주소가 이어서 사용되는 경향도 나타난다. 이 접근 규칙성을 지역성(Locality)이라 한다.

지역성은 캐시 메모리와 가상 메모리, 페이징 시스템이 성능을 확보하는 근거다. 시스템은 다음에 필요할 가능성이 높은 데이터가 이미 접근한 위치 또는 그 인접 영역에 있을 것이라는 전제 아래 데이터를 보관하거나 미리 적재한다.

실행 시간의 90%를 코드의 10%에서 소비한다는 90-10 법칙도 이러한 편중을 설명하는 관찰이다. 반복문, 순차적인 명령어 인출, 함수 호출 중의 지역 변수 사용, 배열과 구조체 같은 데이터 구조의 연속 접근이 지역성을 만든다.

최근 사용한 주소를 다시 찾는 시간적 지역성

시간적 지역성(Temporal Locality)은 최근 참조한 메모리 위치가 가까운 미래에 다시 참조될 가능성이 높다는 성질이다. 같은 주소를 반복해서 사용하는 재사용 패턴이 핵심이다.

루프 카운터, 합계를 갱신하는 누산기, 배열 순회에 쓰이는 인덱스는 반복적으로 읽히거나 갱신된다. 함수가 실행되는 동안에는 스택 프레임 안의 지역 변수도 집중적으로 사용된다.

캐시는 최근 사용한 데이터를 고속 메모리에 남겨 시간적 지역성을 활용한다. 빈번히 쓰는 변수를 레지스터에 할당하거나 자주 접근하는 데이터를 버퍼에 유지하는 방식도 같은 성질을 이용한다.

// 시간적 지역성 예제
for (int i = 0; i < 1000; i++) {  // i는 반복적으로 참조됨
    sum += array[i];               // sum은 계속 갱신됨
}

인접한 주소를 함께 쓰는 공간적 지역성

공간적 지역성(Spatial Locality)은 한 메모리 위치를 참조한 뒤 인접한 주소도 곧 접근될 가능성이 높다는 뜻이다. 연속된 메모리 영역을 따라가는 접근이 여기에 해당한다.

배열 요소를 차례로 순회하거나, 연속된 명령어를 인출하거나, 구조체의 인접 필드를 사용하는 경우가 대표적이다. 문자열을 앞에서부터 처리할 때도 연속된 문자 데이터에 접근하게 된다.

캐시 라인은 인접 데이터를 블록 단위로 캐시에 적재해 이 성질을 활용한다. 다음 접근이 예상되는 데이터를 먼저 올리는 프리페칭(Prefetching), 연속된 페이지를 함께 메모리에 적재하는 페이징 시스템도 공간적 지역성을 바탕으로 한다.

// 공간적 지역성 예제
int array[1000];
for (int i = 0; i < 1000; i++) {  // array[0], array[1], ... 순차 접근
    array[i] = i * 2;
}

순서까지 예측 가능한 순차적 지역성

순차적 지역성(Sequential Locality)은 공간적 지역성의 특수한 형태다. 인접한 위치를 접근한다는 데서 더 나아가, 증가하는 순서로 메모리를 연속 접근한다.

명령어 인출 과정에서 PC(Program Counter)가 증가하는 흐름, for 루프로 배열을 순방향 순회하는 경우, 데이터 스트림을 순서대로 읽는 처리가 여기에 속한다.

공간적 지역성은 인접 위치에 접근한다는 사실에 초점을 두므로 접근 순서는 관계없다. 반면 순차적 지역성에서는 주소가 증가하는 방향으로 이어지는 순서 자체가 중요하다.

캐시·가상 메모리·코드 배치에 반영되는 원리

캐시 메모리는 시간적 지역성을 위해 LRU(Least Recently Used) 교체 정책을 사용하고, 공간적 지역성을 위해 캐시 라인(Cache Line) 단위로 데이터를 적재한다. L1, L2, L3로 이어지는 다단계 캐시도 지역성이 높은 프로그램에서 적중률을 높이는 구조다.

가상 메모리에서는 Working Set 모델을 바탕으로 페이지 교체를 관리한다. 요구 페이징(Demand Paging)은 필요한 페이지만 메모리에 적재하고, 선행 페이징(Prepaging)은 공간적 지역성을 이용해 데이터를 미리 적재한다. 지역성에 맞춘 페이지 관리는 스래싱(Thrashing)을 피하는 데도 연결된다.

프로그램 수준에서는 데이터 접근 순서와 배치를 조정할 수 있다. 루프 융합(Loop Fusion)은 시간적 지역성을 개선하고, 루프 교환(Loop Interchange)은 공간적 지역성을 높인다. 캐시 크기에 맞춰 데이터를 나누는 블록킹(Blocking), 캐시 라인을 고려한 구조체 배치도 같은 목적의 기법이다.

접근 패턴을 관찰하고 개선하는 방법

지역성은 캐시나 페이지의 적중률(Hit Ratio), 메모리 접근 순서를 기록한 참조 문자열(Reference String), 동일 주소 재접근 간격인 재사용 거리(Reuse Distance), 특정 시간 동안 참조된 페이지 수인 Working Set 크기로 분석할 수 있다.

프로파일러(Profiler)는 함수와 라인별 실행 빈도를 확인하는 데 쓰인다. 캐시 시뮬레이터는 캐시 적중률을 예측하고, 트레이스 분석기는 메모리 접근 패턴을 시각화한다. 하드웨어 이벤트는 성능 카운터로 측정할 수 있다.

개선 대상은 빈번하게 실행되는 핫스팟(Hot Spot)부터 찾는다. 접근 패턴에 맞춰 데이터를 재배치하고, 실행 순서에 맞게 함수를 배치하며, 지역성이 높은 알고리즘을 선택하는 접근이 가능하다. 지역성은 코드와 데이터가 메모리 계층을 어떻게 통과하는지 판단하는 기준이 된다.