캐시 친화적인 프로그램 작성
컴퓨터 구조
컴퓨터 구조를 공부하면서 알게된 내용을 요약해서 작성해보자.
캐시
- CPU와 메모리 사이의 속도 차이를 보완하려고 CPU가 메모리에 직접 접근하는 대신 CPU와 메모리 사이에 캐시를 추가했다.
- 일반적으로 L1, L2, L3 캐시 세 계층으로 나뉜다.
- L1 캐시에서 L3 캐시로 갈수록 캐시 용량은 점점 커지지만 접근 속도는 점점 느려진다.
- 이 세 계층의 캐시는 메모리의 데이터를 저장하는데, CPU는 메모리에 접근해야 할 때 캐시를 먼저 확인한다.
- 캐시에 데이터가 있다면 메모리에 접근할 필요가 없다.
- 캐시 적중률을 높이기 위한 프로그램 지역성의 원칙이 있다.
프로그램 지역성의 원칙
- 프로그램 지역성의 본질은 프로그램이 매우 규칙적으로 메모리에 접근한다는 것이다.
- 프로그램이 메모리 조각에 접근하고 나서 이 조각을 여러 번 참조하는 경우를 일컬어 시간적 지역성이라고 한다. 이는 오늘 교실에서 공부를 했던 학생이 내일도 또 교실에 가는 것에 비유할 수 있다.
- 프로그램이 메모리 조각을 참조할 때 인접한 메모리도 참조할 수 있는데, 이것을 공간적 지역성이라고 한다.
메모리 풀 사용
- 메모리 풀은 일반적으로 고성능 요구 사항이 있을 때만 사용된다.
- 메모리 풀 기술은 커다란 메모리 조각을 미리 할당받는다.
- 메모리 풀을 초기화할 때 일반적으로 연속적인 메모리 공간을 할당받는다.
핫 데이터와 콜드 데이터의 분리
- 노드가 많을 때는 연결리스트에 접근할 때 캐시해야 하는 노드도 많아진다.
- 배열 하나를 다른 구조체에 넣고 List 구조체 안에 이 구조체를 가리키는 포인터를 추가할 수 있다.
- 이렇게 하면 List 구조체 크기는 줄어들고 캐시는 더 많은 노드를 저장할 수 있다.
- 구조체의 배열은 콜드 데이터, 더 빈번하게 접근하는 것이 핫 데이터다.
- 콜드 데이터와 핫 데이터를 서로 분리하면 더 나은 지역성을 얻을 수 있다.
캐시 친화적인 데이터 구조
- 지역성 원칙 관점에서는 배열이 연결 리스트보다 낫다.
- 배열은 하나의 연속된 메모리 공간에 할당되지만, 연결리스트는 일반적으로 이곳저곳에 흩어져 있을 수 있기 때문이다.
- 연속된 메모리는 확실히 더 나은 공간적 지역성을 보여주며 캐시 친화적이기도 하다.
- 데이터 구조의 장단점 논의는 캐시 친화적인가 그렇지 않은가에 국한된다는 것을 반드시 염두에 두어야 한다.