📝 서론
블로그 글을 작성하다 보니, Locality를 설명할 필요성이 느껴졌다.
설명이 조금 길어질 것 같아 따로 Locality에 대한 설명 글을 적는다.
📖 Locality에 대하여
컴퓨터와 Cache 메모리
CPU가 프로그램을 실행하기 위해서는 어딘가에 존재하는 데이터를 가지고 와야 한다. 그런데, CPU가 데이터를 가져오기 위해서 메모리에 접근하는 것은 비교적 큰 시간 비용이 든다. 때문에 컴퓨터는 비교적 자주 사용하는 데이터들을 접근이 빠른 Cache memory에 데이터들을 저장한다.
운영체제를 강의하셨던 교수님의 비유를 빌리자면, 책이 필요할 때 마다 항상 도서관에 가는 것은 시간이 오래 걸리기 때문에, 자주 참고해야 할 책은 대여해서 내 방 책상 위에 올려두는 것이다.
캐시에 저장하게 될 자주 사용하는 데이터 라는 것은 무엇일까?
자주 사용하는 데이터
프로그램을 작성하다 보면, 특정 시간대에 유독 자주 접근하는 데이터가 생길 수 있다. 예를 들어, A라는 프로그램이 동작하는 시간이 10초라고 가정하자. 이 때, 1~3초 사이에는 int temp 라는 변수를 자주 사용했고, 6~8초 사이에는 int i 라는 변수를 자주 사용했다고 가정하자. 그렇다면 1~3초 사이의 동작에서는 int temp 변수가, 6~8초 사이에는 int i 변수가 cache에 저장되어 있다면, 해당 변수를 디스크나 메모리에서 가지고 오는 것 보다 훨씬 시간을 단축시킬 수 있다는 것이다.
그렇다면, 컴퓨터는 어떻게 자주 사용하게 될 데이터를 예측하고, Cache memory에 저장하는 것일까? 이 때 Locality 라는 개념이 사용된다.
Locality란?
미리 말해두건데, 이 Locality 라는 것은 어떠한 규칙이나 약속같은 것이 아니다. "프로그램을 사용하다 보니 어떠어떠한~~ 메모리를 자주 사용하더라" 라는 어떠한 특성같은 것이다.
즉, 지금까지의 경험을 살펴보며 자주 사용할 가능성이 높은 데이터에 대한 경험적 빅데이터에 가깝다고 할 수 있다.
Locality에는 Temporal locality와 Spatical locality가 있다.
1. Temporal locality
Temporal locality : 최근 참조했던 데이터를 다시 참조할 가능성이 높다는 성질
즉, 한번 사용한 데이터는 다시 사용할 가능성이 높다는 것이다. 예를 들어보자.
int main(){
...
for(int i = 0; i<100; i++){
sum += i;
}
...
}위의 코드를 살펴보자. for문 안에 존재하는 코드가 반복적으로 실행되는 동안, CPU는 i라는 변수를 반복적으로 사용하고 있다. 또, sum이라는 변수 역시 반복적으로 참조하고 있다. 그렇다면 두 변수 i와 sum이 cache 메모리에 존재한다면, 훨씬 시간을 절약하여 프로그램을 실행시킬 수 있을 것이다.
그렇다면, 위 코드에서 반복적으로 사용하는 데이터는 두 변수 i와 sum이 전부인가? 그렇지 않다!
프로그램은 실행되는 시점에 코드를 모두 메모리의 코드 영역에 저장한 후, 명령어를 하나씩 가져오며 프로그램을 실행한다. 즉, 사용하는 코드 역시 데이터의 일종이다. 그렇다면 for문 안에 존재하는 sum += i 라는 명령어 역시 반복적으로 사용하는 데이터가 될 수 있다.
이처럼 한번 사용했던 변수는 빠른 시간 내에 다시 사용할 가능성이 높다는 특성이 Temporal locality 이다.
2. Spatical locality
Spatical locality : 최근 참조했던 데이터의 근처에 저장되어 있는 데이터는 근래에 사용될 가능성이 높다는 성질
즉, 근처에 저장되어 있는 데이터들은 함께 사용될 가능성이 높다고 이해해도 좋을 듯 하다.
이번에도 코드를 통해 예시를 확인해 보자.
int main(){
int array[5] = {1, 2, 3, 4, 5};
int sum = 0;
for(int i = 0; i<5; i++)
sum += array[i];
...
}위의 코드에서는 array[0]부터 array[4]까지의 다섯개의 데이터가 순차적으로 참조되고 있다. 그리고, 다들 알고 있겠지만, C언어에서 배열은 인접한 위치에 연속적으로 저장된다.
즉, array[0] ~ array[4]의 다섯개 변수는 인접한 위치에 저장되어 있는 데이터이다.
그렇기에, array[0]을 사용하는 시점에서 Spatical locality를 고려할 수 있다면, array[0] ~ array[4] 까지의 다섯개의 데이터를 Cache memory에 저장하여 프로그램 실행 시간을 더욱 단축시킬 수 있다.
이번 코드 역시 locality의 예시는 변수가 끝이 아니다. C언어에서 일반적으로 모든 코드는 순차적으로 실행됨을 알고 있을 것이다. 그렇기에 이전에 실행되었던 코드와 연속된 위치에 저장되어 있는 코드는 다른 코드에 비해 빠른 시간 내에 실행될 가능성이 훨씬 높다. 따라서 프로그램을 구성하고 있는 명령어 역시 Spatical locality의 예시가 될 수 있다.
Locality의 활용
프로그래머는 이 Locality를 고려하여 프로그램의 성능을 개선할 수 있다.
다음의 두 코드를 비교해 보자.
// 1번 코드
int main(){
...
for(int i = 0; i<10; i++){
for(int j = 0; j<10; j++){
sum += array[i][j];
}
}
...
}// 2번 코드
int main(){
...
for(int i = 0; i<10; i++){
for(int j = 0; j<10; j++){
sum += array[j][i];
}
}
}생략된 부분의 코드는 모두 동일하다고 가정했을 때, 두 프로그램의 다른 점은 배열의 각 원소를 참조하는 순서를 array[i][j]로 사용하는지, array[j][i]로 사용하는지의 차이일 뿐이다.
그러나, 두 코드의 실행 시간에서 유의미한 차이를 확인할 수 있을 것이다.
1번 코드가 2번 코드보다 훨씬 빠른 속도로 실행될 것이다. 왜 그럴까? 그 이유는 2차원 배열의 저장 방법에 있다.
2차원 배열 int array[10][10]이 저장될 때는 array[0][0] 바로 다음 주소에 array[0][1]이 저장되고, array[1][0]은 array[0][9] 바로 다음 위치에 저장된다.
즉, array[0][0] 다음에 array[0][1]을 사용한다면 array[0][0] 근방의 데이터들을 cache에 저장하여 Spatical locality를 활용할 수 있다. 하지만, array[0][0] 다음에 array[1][0]을 사용한다면, 인접한 위치의 데이터들을 순차적으로 사용하지 않기에 Spatical locality를 제대로 활용하지 못해 메모리의 접근에 훨씬 많은 시간이 소요된다.
✏️ 정리
요약하자면, Locality는 자주 사용할 것으로 예측되는 데이터를 예측하기 위해 사용되는 현상이다.
