[TIL] 메모리 참조 지역성

메모리 참조 지역성이란

메모리 참조 지역성(Locality of Reference)은 프로그램이 짧은 시간 동안 비교적 좁은 메모리 영역에 접근하는 경향을 말합니다. 실행 중인 코드는 방금 사용한 변수나 명령어를 다시 사용하고, 배열처럼 인접한 데이터를 차례로 읽는 경우가 많습니다.

이 경향은 빠르지만 작은 메모리에 현재 필요한 데이터를 보관한다는 캐시 설계의 근거가 됩니다. 앞으로 사용할 데이터를 완벽하게 알 수는 없어도, 최근 데이터와 인접 데이터를 준비하면 실제로 다시 쓰일 가능성이 높기 때문입니다.

지역성은 프로그램의 정답을 바꾸는 규칙이 아니라 접근 패턴의 성질입니다. 같은 결과를 만드는 코드라도 데이터를 어떤 순서로 읽고 쓰는지에 따라 캐시 효율과 실행 시간이 달라질 수 있습니다.

시간 지역성

시간 지역성은 최근에 접근한 데이터나 명령어를 가까운 시간 안에 다시 접근할 가능성이 높다는 성질입니다. 반복문의 제어 변수, 누적값, 자주 호출되는 함수의 명령어, 현재 함수의 지역 변수에서 쉽게 볼 수 있습니다.

int sum = 0;

for (int i = 0; i < 100; ++i) {
  sum += i;
}

반복문이 실행되는 동안 sum과 i는 계속 읽고 갱신됩니다. 반복 조건 검사와 덧셈을 수행하는 명령어도 짧은 시간 안에 여러 번 실행됩니다. 캐시는 이런 데이터를 한 번 사용했다고 바로 버리지 않고 보관해, 다음 접근이 빠른 캐시에서 처리될 가능성을 높입니다.

• 루프 안에서 반복해서 읽고 쓰는 변수
• 여러 번 호출되는 함수의 명령어
• 스택에 놓인 현재 함수의 지역 변수
• 같은 배열 원소를 여러 계산에서 재사용하는 경우

공간 지역성과 순차 지역성

공간 지역성은 어떤 주소에 접근한 뒤 그 주변 주소에도 곧 접근할 가능성이 높다는 성질입니다. 배열 원소는 메모리에 연속해서 배치되므로 처음부터 끝까지 순회하는 코드가 대표적인 예입니다.

int values[100]{};

for (int i = 0; i < 100; ++i) {
  process(values[i]);
}

values[0] 다음에 values[1], values[2]를 읽으면 접근 주소가 차례로 이어집니다. 이처럼 주소 순서대로 데이터나 명령어를 접근하는 경향을 순차 지역성이라고 하며, 보통 공간 지역성의 한 형태로 설명합니다. 특별한 분기가 없다면 CPU가 명령어를 앞에서 뒤로 가져오는 흐름에서도 순차 지역성이 나타납니다.

반대로 연결 구조의 노드가 메모리 곳곳에 흩어져 있거나 큰 배열에서 일정 간격을 두고 원소를 읽으면 다음 접근 주소가 멀리 떨어질 수 있습니다. 알고리즘의 연산 횟수가 같아도 이런 접근 패턴은 캐시를 덜 효율적으로 사용할 수 있습니다.

캐시 라인과 캐시 적중

CPU 캐시는 필요한 데이터 한 바이트만 가져오기보다 일정한 크기의 캐시 라인 단위로 데이터를 옮깁니다. 캐시 라인의 정확한 크기는 시스템에 따라 다르지만, 현대의 많은 CPU에서는 64바이트가 흔합니다. 따라서 배열 원소 하나를 요청했을 때 그 주변 원소도 같은 캐시 라인에 함께 들어올 수 있습니다.

• 캐시 적중 · Cache Hit
• 필요한 데이터가 캐시에 있어 RAM까지 내려가지 않고 빠르게 접근합니다.
• 캐시 미스 · Cache Miss
• 데이터가 캐시에 없어 더 느린 하위 메모리에서 캐시 라인을 가져와야 합니다.

배열을 순서대로 읽으면 한 번 가져온 캐시 라인 안의 여러 원소를 연달아 사용할 수 있습니다. 반면 큰 간격으로 주소를 건너뛰면 가져온 라인의 일부만 사용하고 다음 라인을 다시 요청하게 되어 캐시 미스가 늘어날 수 있습니다.

2차원 배열 접근 순서

C++의 일반적인 2차원 배열은 행 우선(row-major) 방식으로 저장됩니다. matrix[0][0], matrix[0][1], matrix[0][2]처럼 같은 행의 원소가 연속된 주소에 놓입니다.

constexpr int size = 1000;
int matrix[size][size]{};

// 행 우선 저장 순서와 같은 방향
for (int row = 0; row < size; ++row) {
  for (int column = 0; column < size; ++column) {
    ++matrix[row][column];
  }
}

안쪽 반복문이 열 인덱스를 증가시키므로 메모리에 연속된 원소를 읽습니다. 한 캐시 라인에 들어온 주변 원소를 바로 이어서 사용해 공간 지역성을 활용하기 좋은 순서입니다.

// 열부터 순회해 큰 간격으로 주소를 이동
for (int column = 0; column < size; ++column) {
  for (int row = 0; row < size; ++row) {
    ++matrix[row][column];
  }
}

두 코드는 모든 원소를 한 번씩 증가시키므로 계산 결과와 시간복잡도는 같습니다. 하지만 두 번째 코드는 안쪽 반복마다 한 행 크기만큼 주소를 건너뛰기 때문에 큰 배열에서는 캐시 미스가 더 자주 발생하고 느려질 수 있습니다. 즉 빅오 표기법이 같아도 메모리 접근 패턴에 따라 실제 성능은 달라질 수 있습니다.

메모리 계층과 가상 메모리

컴퓨터의 저장 공간은 빠르고 작은 장치에서 느리고 큰 장치로 계층을 이룹니다. CPU에 가까울수록 접근은 빠르지만 용량과 비용의 제약이 크기 때문에, 현재 자주 쓰는 데이터만 위쪽 계층에 유지합니다.

1. CPU 레지스터
2. L1 캐시
3. L2 캐시
4. L3 캐시
5. RAM
6. SSD 같은 보조 저장 장치

지역성은 CPU 캐시에만 적용되지 않습니다. 가상 메모리는 데이터를 페이지 단위로 관리하고, 운영체제는 제한된 물리 메모리에 현재 필요한 페이지를 유지하려고 합니다. 프로그램의 작업 집합이 일정한 페이지에 모여 있으면 같은 페이지를 반복해서 사용할 수 있지만, 넓은 영역을 불규칙하게 오가면 페이지 교체와 페이지 폴트가 늘어날 수 있습니다.

지역성이 높을수록 빠른 계층에서 요청을 해결할 가능성이 커집니다. 그 결과 캐시 적중률이 올라가고, 평균 메모리 접근 시간과 페이지 폴트 비용은 줄어듭니다.

코드에서 활용하는 방법

지역성을 고려한다는 것은 모든 코드를 저수준 최적화로 바꾼다는 뜻이 아닙니다. 먼저 올바르고 읽기 쉬운 코드를 작성하고, 프로파일링으로 메모리 접근이 실제 병목인지 확인해야 합니다. 병목이 확인됐다면 다음과 같은 방향을 검토할 수 있습니다.

• 배열과 벡터처럼 연속 저장되는 데이터를 가능한 한 순서대로 순회합니다.
• 중첩 반복문은 실제 메모리 배치와 같은 방향으로 접근합니다.
• 루프 안에서 자주 쓰는 데이터를 가까운 시점에 모아 처리합니다.
• 한 번 읽은 데이터를 여러 계산에 재사용해 시간 지역성을 높입니다.
• 드물게 쓰는 데이터와 자주 쓰는 데이터를 분리해 핵심 작업 집합을 작게 유지합니다.

게임에서는 매 프레임 많은 객체를 갱신하거나 충돌 후보, 파티클, 애니메이션 데이터를 순회합니다. 이런 반복 경로에서 관련 데이터를 연속적으로 배치하고 순차 접근하면 같은 알고리즘이라도 프레임 시간의 안정성에 도움이 될 수 있습니다.

정리

• 메모리 참조 지역성은 프로그램이 최근 주소와 그 주변 주소를 반복해서 접근하는 경향이다.
• 시간 지역성은 최근 사용한 데이터나 명령어를 곧 다시 사용하는 성질이다.
• 공간 지역성은 접근한 주소 주변을 이어서 사용하는 성질이며, 순차 지역성은 그 대표적인 형태다.
• CPU 캐시는 캐시 라인 단위로 주변 데이터를 함께 가져와 공간 지역성을 활용한다.
• 행 우선 2차원 배열은 행 방향으로 순회할 때 연속된 메모리를 효율적으로 사용할 수 있다.
• 지역성이 높으면 캐시 적중률이 올라가고 평균 접근 시간과 페이지 폴트가 줄어들 수 있다.

지역성을 이해하면 같은 시간복잡도의 코드가 왜 서로 다른 실제 성능을 보이는지 설명할 수 있습니다. 데이터의 위치와 접근 순서까지 생각하는 습관은 CPU와 메모리 계층을 더 효율적으로 사용하는 출발점입니다.