캐시 라인,( C++ STL std::list 보다 std:vector를 써야하는이유)

한 Cache 라인에 있으면 1 Clock 만 필요, -> 어마어마하게 빠른 Data Manipulation이 가능해진다.

Vector 는 늘 Cache Line에 데이터를 가지고 있음, List는 NONO

 

CPU의 캐시라인이란?

 CPU가 메모리로부터 데이터를 가져올 때는 바이트 단위로 가져오지 않고 캐시라인을 가득 채울 만큼의 데이터를 

 가져오는 것을 말합니다. (메모리의 페이징 기법과 비슷합니다.)

 캐시라인의 크기는 32, 64, 128바이트(CPU에 따라 다름) 구성되며 해당 사이즈 경계로 정렬되어 있습니다.

CPU-Z로 확인한 CPU 정보

 필자의 컴퓨터의 경우 64바이트의 캐시라인을 사용하고 있습니다. 

 캐시 라인을 사용하는 이유는 일반적인 애플리케이션의 경우 인접한 바이트들을 사용하는 경우가 많기 때문에

 CPU의 메모리 접근 횟수를 줄여 성능을 향상 시키기 위함입니다.

 

멀티 프로세서 환경에서 캐시라인

 캐시라인은 성능의 향상을 위해서 도입되었지만 멀티 프로세서 환경에서는 문제가 될 수 있는 여지가 있습니다.

 다수의 CPU가 동일한 캐시라인을 보유하고 있다고 가정하고 그중 하나의 CPU가 해당 캐시라인을 수정한다면

 다른 CPU들은 해당 캐시라인의 갱신을 어떻게 확인 할 수 있을까요?

 이런 문제를 해결하기 위해서 CPU 설계자는 캐시라인이 수정되면 다른 CPU가 들고 있는 캐시라인을 무효화

 시켜 데이터를 동기화 합니다. 이후 다른 CPU는 해당 캐시라인을 사용하려면 메모리에서 다시 읽어야 합니다.  

 이러한 이유 때문에 캐시라인이 오히려 멀티 프로세서 환경에서는 성능을 저해하는 요인이 될 수 있습니다.

성능을 개선하는 방법

 멀티 프로세서에서 개발을 하는 애플리케이션 개발자는 이러한 속성을 이해해서 애플리케이션에서 사용하는 

 데이터를 캐시라인의 크기와 같은 경계라인으로 묶어서 다루는 것이 좋습니다. 

 해당 머신의 CPU의 캐시라인은 어떻게 얻어 올 수 있을까요? WINDOWS API인 GetLogicalProcessorInfomation함수를

 통해서 얻어 올 수 있습니다. MSDN을 참조해서 해당 캐시라인을 가져오는 함수를 만들어 보았습니다.

 

 

-------이와 관련해서 좋은 글

자료구조의 성능을 비교할 때는 원소의 크기, 지역성에 대한 케시미스 입니다.
vector는 연속적으로 데이터를 저장하기 때문에 지역성이 높아 캐시 효율이 좋습니다. .
원시 타입이나 간단한 구조체에 대해서는 vector가 list에 비해 성능이 좋습니다.
반면에 list는 많은 상황에서 캐시 미스가 발생해 크기가 작은 원소에 대해서는 vector에 비해 느립니다.
그러나 원소의 크기가 커지게 되면 vector의 캐시 효율이 떨어지게 되므로 
list가 상대적으로 성능이 좋아지게 됩니다.
그리고 어떤 상황에서도 안정적인 성능을 보이는 것은 deque 입니다.
deque는 vector의 단점인 복사와 단편화를 줄인 버전 또는 vector와 list의 중간 정도로 생각할 수 있는데,
원소가 추가될 때 공간이 부족하면 새로운 배열로 원소들을 복사하는 것이 아니라 
새로운 메모리 블록을 할당합니다.
이때문에 vector보다는 지역성이 떨어지지만 vector보다 일관된 성능을 가지게 됩니다.

 

---

아래는 기본적으로 프로그래머들이 가지고 있는 DS에 대한 상식이다 . 그러나 위의 캐쉬라인 즉, 메모리에 대해 제대로 Manage 하면서 프로그래밍을 하는것이 매우중요하다.

vector, deque, list 간단 비교 정리

1. vector

일반적인 배열처럼 vector는 개체들을 연속적인 메모리 공간에 저장한다.
즉, iterator 뿐 아니라 position index(operator [])로도 접근이 가능하다는 것이다.

vector는 동적으로 확장/축소가 가능한 dynamic array로 구현되어 있다.

강점

• 개별 원소들을 position index로 접근이 가능하다 (상수 복잡도)
• 원소를 컨테이너의 끝에 삽입/제거 하는 것이 빠르다 (상수-아모타이즈드 복잡도)
• 어떠한 순서로도 원소들을 순회할 수 있다. 즉, Random access iterating이 가능함. (로그 복잡도)

일반적으로 vector는 다른 두 개의 시퀀스 컨테이너인 deque, list에 비해 개별 원소에 대한 접근 속도와 컨테이너의 끝에서 삽입/제거하는 속도가 가장 빠르다. 
굳이 "일반적으로" 빠르다는 표현을 쓴 것은 특정 상황별로 달라지기 때문이다.
이는 아래 내용들을 모두 읽어보고 종합적으로 분석해 보면 알 수 있다.

약점

• 컨테이너의 끝 위치가 아닌 곳에서 삽입/제거 수행시 그 성능은 deque/list에 비해 현저히 떨어진다.

주의

• 동적으로 컨테이너의 크기가 확장/축소되는 것이 편하기는 하나, 확장시의 reallocation은 비용이 꽤 크다.
• capacity를 확장 시켜줄 수 있는 적절한 크기의 reserve로 인한 메모리 확보가 중요.

 

2. deque (double ended queue)

deque는 어느 정도 vector와 유사성이 있는 듯하면서도 상당히 많이 다르다고도 할 수 있는 시퀀스 컨테이너다.

우선, Random access iterator를 통한 개별 원소에 대한 접근이 가능하다. operator []도 지원된다.
그리고, 컨테이너의 크기 역시 동적으로 조절되지만, 그 방법은 vector의 그것과 많이 다르다.

강점

• 개별 원소들을 position index로 접근이 가능하다.
• 원소를 컨테이너의 끝 뿐 아니라, 앞에서도 삽입/제거 하는 것이 빠르다.
• 어떠한 순서로도 원소들을 순회할 수 있다.

약점

• 컨테이너의 시작 / 끝 위치가 아닌 곳에서 삽입/제거 수행시 그 성능은 list에 비해 현저히 떨어진다.

vector와 비슷해 보이지만, 두번째 강점이 vector와의 첫번째 차이점이다. 
vector는 컨테이너 끝에 삽입/제거하는 것만이 빨랐지만, deque는 컨테이너 끝 뿐 아니라 처음부분에서의 삽입/제거도 효율이 높다. double ended 라는 naming...

이러한 특징으로 STL의 스택과 큐 클래스는 deque와 list로 구현이 가능하지만, 기본 클래스는 deque이다.

그리고 vector와의 두번째 차이점이 컨테이너의 동적 확장/축소 방식이다.
이는 어떻게 보면 deque의 불편한 점이 되기도 하고, vector보다 더 나은 점이 되기도 한다.

vector의 경우 컨테이너 내부 capacity가 고갈되면 이를 확장하기 위해 전체 메모리 크기만큼 reallocating이 발생한다.
하지만, deque의 경우 일정 크기를 가지는 chunk 단위로 확장되는 방식을 가지고 있다.
이렇기에 vector에 비해 다음과 같은 장단이 존재한다.

장점

• 저장 원소가 많고 메모리 할당량이 큰 경우 vector에 비해 확장 비용이 절감된다.
  : 전체가 재할당되기 보다, 늘어나야 될 크기만큼만의 chunk가 하나 더 할당되면 그만이므로...

단점

• 컨테이너 처음부터 끝까지 연속 메모리 공간이 아니므로, vector에서 가능했던 원소들간 포인터 연산이 불가능하다.

 

3. list

list는 doubly linked list로 구현되어 있다.

강점

• 컨테이너의 어느 위치에서도 삽입/제거가 빠르다 (상수 복잡도)
• 원소들의 컨테이너 내 순서 이동이 빠르다. (상수 복잡도)

vector와 deque와 다르게 list의 가장 큰 강점은 컨테이너 내 어느 위치에서도 원소의 삽입/제거가 빠르다는 것이다.

약점

• 원소의 position index로 직접 접근이 불가능하다.
  : 특정 원소에 접근하려면 처음이나 끝에서부터 선형 탐색을 하여야만 한다.
• 컨테이너 내 원소 순회는 forward / reverse 순회만 가능하며, 느리다. (선형 복잡도)
• 원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용된다.
  : 원소 수가 적을수록 그 상대 비율은 올라가겠지 쩝;

얼핏 보면 약점이 되게 많아 보이지만, 컨테이너 내 어느 위치에서도 원소의 삽입/제거가 빠르다는 장점이 list의 활용성을 대변해 주는 키워드이다.