참조 지역성의 원리란?

 

매일메일 백엔드 질문을 참고해 개인적으로 학습한 내용을 정리하였습니다.
오류가 있다면 언제든 피드백 주시면 바로 반영하겠습니다..!

 

 

 

참조 지역성의 원리란?

 

참조 지역성의 원리(Locality of reference)는 CPU가 메모리에 접근할 때 특정 메모리 영역을 반복적으로 접근하는 경향이 있다는 원리를 의미하며, 주로 캐시 메모리의 적중률을 높여 CPU의 메모리 접근 횟수를 줄이는 데 이용됨

 

=> 크게 시간 지역성과 공간 지역성이 존재함

 

시간 지역성 (Temporal locality)

 

시간 지역성(Temporal locality) 이란 CPU는 최근에 접근한 데이터를 가까운 시점에 다시 접근할 가능성이 높다는 성질임

 

int sum = 0;
for (int i = 0; i < 100; i++) {
    sum += array[10]; // 같은 인덱스 반복 접근
}

 

여기서 array[10]은 루프마다 계속 사용되기 때문에 CPU는 이를 캐시에 보관하고 빠르게 재사용할 수 있음

=> 이렇게 같은 데이터를 반복해서 사용하는 구조는 시간 지역성의 예시로 볼 수 있음

 

공간 지역성 (Spatial locality)

 

공간 지역성(Spatial locality) 이란 CPU는 한 번 접근한 데이터 근처의 데이터도 곧 접근될 가능성이 높다는 성질임

 

for (int i = 0; i < 100; i++) {
    sum += array[i]; // 연속된 메모리 접근
}

 

위 코드는 array[0], array[1], array[2] 처럼 물리 메모리상 인접한 위치를 순차적으로 접근하기 때문에, CPU가 미리 인접 데이터를 캐시에 로딩해 놓고 빠르게 처리할 수 있음

 

예시 코드 개선

 

public class LocalityTest {

     @Test
     void test() {
        int size = 10240;
        int[][] array = new int[size][size];

        long beforeTime = System.currentTimeMillis();

        for (int j = 0; j < size; j++) {
            for (int i = 0; i < size; i++) {
                array[i][j]++;
            }
        }

        long afterTime = System.currentTimeMillis();
        long diffTime = afterTime - beforeTime;
       
        System.out.println("수행시간(m) : " + diffTime); // 577ms
    }
}

 

위 코드는 2차원 배열을 순회하면서(열 먼저) 값을 증가하는 코드인데 JAVA에서 2차원 배열은 내부적으로 1차원 배열에 대한 참조 배열임

=> array[i]는 각각 독립된 int[] 객체이며, 이들은 메모리상에 반드시 연속적으로 배치되는 것이 보장되지 않음

 

CPU 캐시는 공간 지역성의 원리에 근거를 두어 물리적인 메모리 공간상에 인접한 데이터를 미리 캐싱할텐데 열을 먼저 순회하고 행에 접근하게 된다면 물리적인 메모리상에서 멀리 떨어져 있는 데이터를 읽게 되어 캐시 히트율이 떨어짐

=> 위 코드를 개선하기 가장 쉬운 방법은 행에 먼저 접근하여 캐시 히트율을 높이는 것임

 

public class LocalityTest {

     @Test
     void test() {
        int size = 10240;
        int[][] array = new int[size][size];

        long beforeTime = System.currentTimeMillis();

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                array[i][j]++;
            }
        }

        long afterTime = System.currentTimeMillis();
        long diffTime = afterTime - beforeTime;
       
        System.out.println("수행시간(m) : " + diffTime); // 28ms
    }
}

 

일반적인 경우와 같이 배열의 행을 먼저 순회하고 열을 나중에 순회하는 코드인데 이는 array[i]라는 하나의 배열을 연속적으로 접근하게 되며, CPU 캐시의 공간 지역성을 극대화할 수 있음

(열을 먼저 순회하는 코드와 약 20배 이상의 성능 차이가 나는 것 을 확인할 수 있음)

 

요약

 

참조 지역성은 고성능 어플리케이션을 설계할 때 꼭 알아야 할 메모리 접근의 핵심 원리임
(단순한 루프 순서 변경만으로도 수십 배의 성능 향상을 이끌어낼 수 있음)

 

캐시를 잘 활용하려면

 

• 시간 지역성 : 최근에 접근한 데이터는 또 접근할 가능성이 높다
  
  
• 공간 지역성 : 접근한 위치 근처도 곧 접근될 가능성이 높다
  
  

을 신경써야함!!

 

L1 캐시는 시간 지역성에 특히 민감하고,  L2나 L3 캐시는 공간 지역성도 고려해 동작함