참조 지역성(Locality of reference)이란?
참조 지역성 원리는 데이터에 대한 참조가 지속적으로 일어날 때, 이전에 참조한 데이터와 시간적으로 공간적으로 인접한 데이터가 연속적으로 참조될 확률이 높다는 것이다. 즉, 최근에 접근한 데이터의 주변에 반복해서 접근할 가능성이 높다.
이를 근거로 CPU는 특정 데이터에 접근할 때, 그 데이터가 위치한 주소의 인접 메모리들까지 캐싱한다. 즉, 공간 지역성을 근거로 캐싱한다.
예를 들면, 연속된 메모리를 할당받는 배열의 특정값을 가져올 때, 그 값을 읽음과 동시에, 인접한 다른 원소들도 같이 캐싱한다.
이렇게 하면 참조 지역성에 따라, 통계적으로 메모리에 직접 접근해야하는 횟수가 크게 감소한다. 이미 CPU가 이렇게 설계되어있으므로, 우리가 어플리케이션을 개발할 때도, 최적화를 위해서는 고려해야할 필요가 있다.
자바의 배열
자바의 배열은 동적할당으로 Heap의 연속적인 메모리를 할당받는다.
단일 배열을 할당할 때는 C와 그렇게 다르지 않지만, 2차원 이상의 다차원 배열을 할당할 때는 차이를 보인다.
2차원 배열로 예를 들어보자.
int staticArr[3][3]; //c 정적할당
int dynamicArr** = (int**)malloc(sizeof(int*) * 3); //c 동적할당
int i;
for(i = 0; i < 3; i++)
{
arr[i] = (int*)malloc(sizeof(int) * 3);
}int[][] arr = new int[3][3]; //java이들은 거의 비슷하게 동작하지만, 할당받은 메모리 구조가 조금 다르다.
c에서는 정적할당한 경우 다차원 배열이더라도, 일렬로 연속된 하나의 메모리를 할당받는다.
반면에 java에서는 배열이 내부적으로 동적할당으로 구현되어 있기 때문에, c의 이중포인터에 대한 동적할당처럼 동작한다.
즉, 각 row(1차원 배열 ex: arr[0], arr[1] ...)가 서로 연관되지 않고 별도로 메모리를 할당 받기 때문에, 메모리가 이웃하지 않는다.
즉, arr[0][2]를 참조했어도, arr[0][1]과 그 주변의 메모리들이 캐싱되지, arr[1][0]이 캐싱되지는 않는다. 따라서, 순회가 자주 발생하는 경우, 하나의 행안에 같이 쓸 데이터들을 몰아서 저장하는 것이 좋다.
그렇지 않으면, 캐시 히트율이 떨어지고, CPU가 반복적으로 메모리에 직접 접근하게 되어, 오버헤드가 크게 증가한다.
C에서 정적할당된 배열 역시 하나의 행의 크기가 커지면, 다른 인접한 열이라도, 같이 캐싱되지 않기 때문에, 웬만하면, 언어 상관 없이, 항상 행우선 순회가 권장된다.
