cache memory
cpu와 주 기억장치(RAM) 사이의 속도 차이를 메우기 위한 고속의 임시 저장 공간
cpu는 엄청나게 빠른데, ram은 그 속도를 따라가지 못합니다.
cpu가 필요한 데이터를 ram에 요청하고 기다리는 시간은 cpu 입장에서 보면 굉장히 긴 시간이다.
이 병목 현상을 해결하기 위해 등장한 것이 바로 캐시 메모레이다.
- 왜 캐시 메모리가 필요한가?
컴퓨터의 핵심 부품인 cpu와 ram 사이에는 엄청난 속도 차이가 존재한다.
- cpu: 매우 빠름(나노초 단위로 동작)
- ram: cpu에 비해 훨씬 느림
cpu가 데이터를 처리하기 위해서 ram에서 데이터를 가져와야한다.
ram이 너무 느려서 cpu가 데이터가 도착할 때까지 아무 일도 못하고 기다려야 하는 상황(병목)이 발생한다.
이는 고성능 cpu의 잠재력을 낭비하는 것과 같다.
Cache Hit: cpu는 매우 빠르게 데이터를 가져와 작업을 즉시 수행한다.
Cache Miss: cpu는 어쩔 수 없이 ram에 데이터를 요청하고, 그 데이터를 캐시에 저장한 후 가져와서 작업을 수행한다.
자주 사용하는 데이터가 캐시에 있을 확률(cache hit rate)이 높을수록 컴퓨터의 전체적인 성능은 크게 향상된다.
- 캐시는 어떻게 동작하는가?
캐시가 효율적으로 동작하는 비결은지역성의 원리덕분이다. 프로세서는 일정 시간 동안 특정 메모리 영역에 집중적으로 접근하는 경향이 있다.
- 시간적 지역성 (Temporal Locality): 최근에 접근한 데이터는 가까운 미래에 다시 접근될 가능성이 높다.
- 공간적 지역성 (Spatial Locality): 하나의 데이터에 접근했을 때, 그 주변의 데이터에도 곧 접근할 가능성이 높다.
캐시 메모리는 이 지역성의 원리를 활용한다. Cache Miss가 발생하여 ram에서 데이터를 가져올 때, cpu가 요청한 데이터만 가져오는 것이 아니라 그 주변의 데이터까지 한 덩어리로 묶어서 캐시에 저장한다. 이렇게 하면 다음번에 필요한 데이터가 이미 캐시에 있을 확률이 극적으로 높아진다.
- 어떻게 코드를 작성해야 캐시 친화적인가?
- 공간적 지역성 극대화
데이터를 메모리상에 물리적으로 가깝게 모아두고, 접근할 때도 순차적으로 접근하는 것이 핵심이다.
배열 vs 링크드 리스트
배열의 경우에는 메모리에 데이터가 연속적으로 나열된다. arr[0]에 접근하면 Cache Miss가 발생하더라도, 캐시는 arr[0]부터 arr[15](캐시 라인 크기에 따라 다름)까지 한꺼번에 가져온다.
따라서 for문으로 배열을 순회하면, 첫 접근 이후 계속해서 Cache Hit가 발생할 확률이 매우 높다.
링크드 리스트의 겨우 각 노드는 동적으로 할당이되므로, 메모리 공간 여기저기에 흩어져 있다.
node1 다음의 노드인 node2는 메모리상에서 완전히 다른 곳에 있을 수 있다.
노드를 하나씩 순회할 때마다 다음 노드의 주소로 점프해야 하므로, 매번 Cache Miss가 발생할 가능성이 높다.
동일한 데이터를 다루더라도, 링크드 리스트보다 배열을 사용하는 것이 캐시 효율 면에서 압도적으로 유리하다.
결론
코드를 작성할 때 캐시의 원리를 이해하고 있다면 지역성을 고려할 수 있다.
하드웨어 잠재력을 최대한 이끌어내는 방식으로 코딩을 한다면 고성능의 프로그램을 만들 수 있는 것 같다.
끝!
