[자료구조] Cache

자료구조(Data Structure)란?

사전적인 의미로는 자료(Data)의 집합을 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.

자료구조를 사용하는 목적은 자료를 더 효율적으로 저장하고, 관리하기 위해 사용한다.

 

지난 학기 OS 수업 시간에 메모리 구성과 동작 과정에 대해 간단하게만 언급해주셨던 기억이 있다.
그 당시에는 LRU라던지 레지스터 등과 같은 개념을 사전적 정의로만 들어서 제대로 와닿지가 않았다.
지금은 메모리를 단계별로 구성하여 설명하겠다.

 

 

CPU가 메모리에 접근하는 방식

CPU가 메모리에 접근하는 방식은 그림과 같다.

1. Cache에 접근하고자 하는 데이터(주소)가 있는지 확인한다.
2. 캐시에 없다면, RAM에 접근하여 확인한다.
3. 램에도 없다면 Disk까지 접근하여 확인한다.

 

 

이 과정이 어떤 것을 의미할까?

아마 처음부터 데이터가 캐시에 저장되진 않을 것이다. 처음 올라오는 곳은 RAM일 것이다.
CPU는 캐시에 접근하고 없으면 RAM에 접근한다고 했는데, RAM에 접근하고 나서 Cache에 그 메모리 주변을 가져와 적재한다.
한번 사용하였으니 다음 번에 또 사용할 확률이 높다고 판단한 것이다.

만약 메인 메모리의 이곳 저곳에 산발적으로 접근한다면, 캐시메모리에 이쪽 부분을 다 담았다가 저쪽 부분을 다 담았다가 등등의 동작을 하며 캐시 메모리를 잘 쓸 수 없죠.  -> 이게 무슨 뜻일까?

 

캐시 친화적인 코드란?

캐시 친화적인 코드이 중요한 측면은 지역성 원칙에 관한 것이다.
그 목표는 관련 데이터를 메모리에 가깝게 배치하여 효율적인 캐싱을 허용하는 것이다. 
이 특성은 캐싱을 최적화하는데 매우 중요한 개념이다.
1. 시간적 지역성: 주어진 메모리 위치에 액세스 할 때 가까운 장래에 동일한 위치에 다시 액세스 할 가능성이 있다. 
간단하게 말하면, 가장 최근에 쓰인 메모리를 가장 가까운 곳에 두는 것이다...?
2. 공간적 지역성: 관련 데이터를 서로 가깝게 배치하는 것을 의미한다. 

"만약 메인 메모리의 이곳 저곳에 산발적으로 접근한다면, 캐시메모리에 이쪽 부분을 다 담았다가 저쪽 부분을 다 담았다가 등등의 동작을 하며 캐시 메모리를 잘 쓸 수 없죠."

캐시 친화적인 코드 개념을 잘 이해했다면, 이 말이 무슨 뜻인지 이해가 될 것이다.

 

 

+ 예시: ArrayList가 LinkedList보다 더 캐시 친화적이라고 할 수 있다.

ArrayList는 해당 배열의 시작 주소를 가지고, 나머지 인덱스 배열에 바로 접근할 수 있다는 장점이 있다.

그 이유는 해당 주소들이 DataType의 크기 만큼 나눠져서 바로 붙어있기 때문이다.

그렇기 때문에 ArrayList는 캐시에 저장될 때, 그 주변 메모리를 가져오기에 매우 적합하다고 할 수 있다.

이런 이유로 캐시 친화적이라고 말할 수 있다.

 

 

 

혼자 자문자답 하기

Q1. ArrayList가 왜 캐시 친화적인가요?
ArrayList는 내부적으로 배열로 구현되어 있다. 배열의 구성 요소는 해당 DataType의 크기 만큼 나줘져 있고, 그 주소는 바로 붙어 있기 때문에 공간 지역성 원칙을 충족한다.
때문에 ArrayList의 메모리 주변을 가져오면 그 구성요소에 접근하기 더 좋다. 


Q3. ArrayList가 add할 때의 시간 복잡도는 어떻게 되는 것인가요?
ArrayList의 크기는 지수적으로 증가한다. 예를 들어, 0~9까지는 O(1)이다가 크기를 늘리는 순간에는 O(n)이 된다.
이러한 특별한 경우에는 평균 시간 복잡도라는 개념을 적용하는데, 시간 복잡도를 평균 값으로 계산하여 O(1)로 생각한다.
하지만 여기서 궁금증이,,, 그럼 삽입만 하는 경우면, LinkedList가 더 효율적일 수도 있는건가??
add를 하다가 크기를 늘릴 때, 새로운 배열을 다시 생성하여 복사하는 것이니... 메모리 낭비가 심할 것 같다.
하지만 LinkedList는 CPU가 메모리에 접근하는 방식의 관점에서 봤을 때 or 공간적 지역성 관점에서 봤을 때, 매우 비효율적이다. 아마 LinkedList보다 더 비효율적일 수가 있을까 싶을 정도이다.

음,, 이 두가지 중 어떤게 더 효율적일까??

 

 

 

 

 

 

 

 

 

참고: https://andrew0409.tistory.com/148, https://isolution.pro/ko/q/so29697045/kaesi-chinhwajeog-kodeu-lan-mueos-ibnikka