Memory, Cache Locality, and why Arrays are Fast (Data Structures and Optimization)

 

https://www.youtube.com/watch?v=247cXLkYt2M&t=544s

Array 기본 개념, Memory Hierarchy에 대한 간략한 영상

 

 

메모리 구조 - Each block stores 1 byte of data - Address increments sequentially

 

Contiguous allocation : Chunk as a whole

 

Non-contiguous : Fragmented

 

Retrieving data with known index is super fast;

단순 연산으로 원하는 위치를 O(1)에 계산할 수 있기 때문

 

Contiguous array의 단점 :

앞/중간 부분에서의 삽입, 삭제가 어렵다 (뒤에 줄지어 있는 데이터들을 한 칸씩 당기거나 밀어줘야 하므로)

 

Fast CPU, but slow and fragmented memory

= overhead at retrieving data

 

Q. How to save time retrieving data from memory? (Optimization) -> Cache Hierarchy (L1/2/3 Caches)

 

CPU가 메모리에서 데이터 읽을 때 일어나는 일 :

메모리를 바로 참조하는게 아니라, L1 - L2 - L3 캐시 순으로 먼저 탐색한다.

 

Cache referencing 속도는 일반 메모리보다는 몇 백배 수준으로 빠르기 때문에,

이런 Hierarchy는 CPU가 데이터를 읽어오는 속도를 크게 개선함

 

캐시에 데이터가 없는 경우, 메모리에서 가져올 수 밖에

→ 이때, 그냥 필요한 데이터만 가져오는게 아니라, 주변 블록을 함께 들고 온다 (cache block)

 

데이터 처리가 가지는 특성 떄문 - Temporal/Spatial locality https://talkingaboutme.tistory.com/entry/Study-Memory-Hierarchy-1

+) Prefetcher : 지금 사용하지 않지만, 미래에 사용할 것 같은 데이터 chunk of block 채로 가져와서 캐싱하는 것

https://wh00300.tistory.com/90

 

 

많은 언어에서 기본적으로 지원하는 Dynamic Array의 구조 :

그냥 많은 블록 미리 선언해두고, size만 조절하는 식 (Memory inefficient 하지 않나? 진짜 이렇다고?)

 

Keywords : memory latency, memory hierarchy