- 최신 컴퓨터 시스템에서 프로그램이 메모리에 접근할 때 캐시의 적중률이 매우 중요함.
- 캐시 친화적인 프로그램을 작성하여 캐시 적중률을 향상 시켜야 함.
- 프로그램 지역성의 원칙
- 지역성이란 프로그램이 ‘매우 규칙적으로’ 메모리에 접근한다는 의미임.
- 프로그램이 메모리 조각에 접근하고 나서 이 조각을 여러 번 참조하는 경우 → 시간적 지역성(temporal locality) 라고 함.
- 시간적 지역성은 캐시 친화성이 매우 높음.
- 데이터가 캐시에 있는 한 메모리에 접근하지 않아도 반복적으로 캐시의 적중이 가능함.
- 프로그램이 메모리 조각을 참조할 때, 인접한 메모리도 참조할 수 있음. → 공간적 지역성(spatial locality) 라고 함.
- 캐시가 적중하지 않으면 메모리의 데이터를 캐시에 적재해야 함.
- 일반적으로 요청한 메모리의 인접 데이터도 함께 캐시에 저장되므로 프로그램이 인접 데이터에 접근할 때 캐시가 적중하게 됨.
- 메모리 풀 사용
- 메모리 풀 기술은 일반적으로 고성능 요구 사항이 있을 때만 사용됨.
- 프로그램이 메모리에서 조각을 N개 할당받아야 할 경우, malloc 을 사용해서 할당 받으면 메모리 조각 N개가 힙 영역 이곳저곳에 흩어져 있을 가능성이 높음.
- 메모리 풀 기술은 커다란 메모리 조각을 미리 할당받음.
- 이후에 메모리 요청하거나 해제할 때 더이상 malloc 을 거치지 않음.
- malloc 은 복잡한 과정에 속하므로, 부담이 없어짐.
- 메모리 풀 초기화할 때 연속적인 메모리 공간을 할당받기에 매우 캐시 친화적임.
#define SIZE 100000
struct List
{
List* next;
int arr[SIZE];
int value;
};
- 연결리스트 구현을 위한 구조체임
- 여기서 arr[SIZE] 배열 변수는 전혀 사용되지 않음.
- 이때, next 포인터와 value 값이 배열 arr 에 의해 멀리 떨어져 있기에 공간적 지역성이 나빠질 수 있음.
#define SIZE 100000
struct List
{
List* next;
int value;
int arr[SIZE];
};
- 따라서 next 포인터와 value 값을 함께 배치하면 캐시는 next 포인터가 있다면 매우 높은 확률로 value 값도 포함되어 있을 수 있음.
#define SIZE 100000
struct List
{
List* next;
int value;
struct Arr* arr;
};
struct Arr
{
int arr[SIZE};
}
- List 구조체의 배열을 Arr 구조체로 빼서 포인터를 가리키게 함.
- 이렇게 되면 연결리스트 노드 자체 저장 공간이 줄어듦.
- 각 노드별 저장 공간 크기가 줄기에 캐시에 저장할 수 있는 노드가 늘어나고 캐시 적중률이 높아짐.
- 여기서 arr 는 콜드 데이터이며 next 포인터와 value 값은 빈번한 접근이 일어나는 핫 데이터임.
- 콜드 데이터와 핫 데이터를 서로 분리하면 더 나은 지역성을 얻을 수 있음.
- 캐시 친화적인 데이터 구조
- 지역성 원칙에서 배열이 연결 리스트 보다 나음.
- 배열은 하나의 연속된 메모리 공간에 할당되지만, 연결 리스트는 일반적으로 이곳저곳에 흩어져 있을 수 있기 때문.
- 하지만, 연결리스트의 자료구조 특성이 배열과 다르고, 캐시 친화적인것과 별개로 배열에서 얻을 수 없는 자료구조적 특성의 이점을 얻을 수 있음.
- 만약 연결리스트의 장점 (노드 추가, 삭제의 시간 효율)과 캐시 친화적이게 만들려면 연결 리스트 생성 시, 메모리 풀에서 메모리 요청하면 됨.
- 이러한 최적화를 할 때는 아래를 판단해야 함.
- 캐시의 적중률이 시스템 성능의 병목이 되는지 판단 해야 함
- 병목이 되지 않으면 굳이 최적화를 할 필요가 없음.
- 다차원 배열 순회
- 다차원 배열의 경우 행 우선 방식으로 배열을 저장함.
- 다차원 배열 순회 시, 행 우선 방식으로 접근한다면, 첫번째 데이터 조회 시, 캐시 적중에 실패하지만, 두번째 데이터 조회 시, 캐시가 적중됨.
- 그러나 열 우선 방식으로 접근한다면, 캐시는 행 우선으로 캐시데이터를 가져오는데 순회를 열 우선으로 해버리니, 캐시를 아무리 갱신해도 절때 캐시 히트가 발생하지 않음.