캐시 메모리: 리스트와 벡터의 속도차이

개요

리스트와 벡터, 어떤게 더 빠를까?

이 물음을 듣고나선 고등학생때 배웠던 리스트와 벡터의 차이를 생각해보았습니다.

 

벡터는 연속된 메모리 주소를 가진 Dynamic Array형태의 자료구조입니다.

리스트는 힙공간에 값을가진 노드가 생성되어있고, 노드가 다음 인덱스의 또 다른 노드를 가르키는 구조입니다.

 

단편적인 생각으로서는, 리스트와 벡터의 속도 차이에서 가장 큰 차이점은 중간 인덱스에 접근할때 구조적으로 속도 차이가 날수밖에 없다고 생각합니다.

 

그렇다면 만약에 리스트와 벡터 둘다 순차적으로 접근할때 어느 자료구조가 더 접근이 빠를까?

위와 같은 질문을 토대로 찾아 보았습니다.

 

답

커트 건서로스의 C++ 최적화: 최고 성능을 구현하는 10가지 검증된 기법에서 답을 찾을 수 있었습니다.

 

---

 

배열이나 벡터처럼 연속된 공간으로 구성된 자료구조는 캐시상에서 연속된 공간에 존재하며, 캐시 공간을 차지하는 개수가 적기 때문에 포인터로 연결된 자료구조보다 접근속도가 빠름.

 

포인터로 연결된 레코드로 구성된 자료구조(리스트나 트리)는 각 노드의 데이터를 메인 메모리에서 새로운 캐시라인으로 읽어야 하기때문에 접근속도가 느릴 가능성이 높음

 

---

 

이를 이해하기 위해서는 캐시메모리가 주기억장치에서 데이터를 가져오는 방식과, 쓰임새를 파악해야하기 때문에, 글을 써보았습니다.

 

캐시 메모리의 개요

CPU는 빠르고, 메모리는 느립니다.

한 프로세스를 실행할때, 필요한 데이터를 메모리에 올려놓으면서 CPU의 연산에 필요할때마다 메모리에서 데이터를 가져옵니다.

 

하지만, 태생적으로 메모리는 CPU보다 느리기때문에 더욱 빠른 CPU의 연산을 위해서는 새로운 구조가 필수불가결합니다.

 

이렇게하여 생성된것이 캐시메모리입니다.

 

위 사진은 메모리 계층구조를 나타낸 이미지입니다.

 

CPU가 연산을 할때 주로 쓰는 데이터들은 메모리에서 계속 꺼내오지 않고, 캐시 메모리에 저장이 됩니다.

 

그렇기 때문에 캐시메모리는 메모리와 CPU사이에 위치해 있습니다.

캐시메모리는 접근이 빠르지만 가격이 비싸기 때문에 용량이 작은 단점이 있습니다.

 

적중과 실패

캐시메모리가 있는 컴퓨터 시스템은 CPU가 메모리에 접근하기 전 먼저 캐시 메모리에서 원하는 데이터의 존재 여부를 확인합니다.

이때 필요한 데이터가 있는 경우를 적중(hit), 없는 경우를 실패(Miss)라고합니다.

 

이 때 캐시메모리의 성능은 적중률에 의해 결정되는데,

적중률은 캐시 메모리의 적중 횟수 / 전체 메모리의 참조횟수로, 생각보다 간단하게 구합니다.

 

CPU는 데이터를 가져오기 위해 캐시 메모리 > 메모리 > 보조기억장치 순으로 접근합니다.

 

• 캐시 적중일 때 : 캐시 메모리의 데이터를 CPU레지스터에 복사한다.

• 캐시 실패/메모리 적중일 때: 메모리의 데이터를 캐시 메모리에 복사하고, 캐시 메모리의 복제된 내용을 CPU 레지스터에 복사한다.

• 캐시, 메모리 실패일 때: 보조 기억장치에서 필요한 데이터를 메모리에 복사한다. 메모리에 복제된 내용을 캐시 메모리에 복제하고, 캐시 메모리의 복제된 데이터를 CPU 레지스터에 복제합니다.

 

캐시 메모리는 이런식으로 데이터를 받아오는데, 계속 데이터를 받아오다간 캐시 메모리의 용량이 부족할게 뻔하기 때문에 최대한 적중률이 높을만한 데이터를 가져옵니다.

 

캐시 메모리의 성공여부는 참조의 지역성 원리에 달려있습니다.

지역성은 짧은 시간동안 제한된 주소 공간의 일부만 참조되는 경향을 말합니다.

 

지역성의 종류는 이와 같습니다.

 

• 시간적 지역성: CPU가 한 번 참조한 데이터는 다시 참조할 가능성이 높다.

• 공간적 지역성: CPU가 참조한 데이터와 인접한 데이터 역시 참조될 가능성이 높다.

• 순차적 지역성: 분기가 발생하지 않는 한 명령어는 메모리에 저장된 순서대로 인출 / 실행된다.

 

이러한 지역성들은 어디까지나 경향에 대한 것이므로 항상 캐시의 높은 적중률을 보장해주지는 않습니다.

 

맨 처음 리스트와 벡터 속도 차이가 난다는 이유도 이런 지역성과 관련이 있습니다.

벡터는 연속된 메모리주소를 가지고 있기 때문에, 공간적 지역성을 바탕으로 수집한다면 벡터는 리스트보다 더 적중률을 높일 수 있습니다.