LRU Cache
Cache
기술이 발전하면서 프로세서의 성능은 빠른 속도로 발전했지만
메모리의 성장은 이 속도를 따라가지 못했다.
이러한 격차를 극복하기 위해 cache라는 고성능의 메모리를 두어 cpu가 하염없이 메모리를 기다리는 일을 어느정도 방지하였다.
- cache는 연산에 필요한 data를 미리 가져다 놓는 임시 메모리이다.
cpu에서 메인메모리에 접근하는데에는 큰 비용이 발생하는데
캐시의 경우 cpu와 물리적으로 더 가까이 있어 비용이 더 적게 발생한다.
따라서 자주 사용되는 값들을 미리 캐시에 적재시켜 참조시간을 대폭 줄일 수 있다.
이 때, cpu가 필요로 하는 데이터가 캐시에 있는 상황을 히트라고 하며
캐시 히트율을 높여 cpu의 성능을 높일 수 있다.
모든 데이터를 캐시에 올려 히트율을 높이면 좋겠지만
캐시의 용량은 한정적이라 많은 데이터를 올릴 수 없고
그때 그때 필요한 데이터도 다르기 때문에 자주 캐시 메모리를 교체 시켜줘야 한다.
이 때, cpu가 필요로 하는 값을 예측하는데에 참조 지역성의 원리라는 것를 이용하는데
이는 시간 지역성과 공간 지역성으로 나눌 수 있다.
- 시간 지역성이란 최근에 접근했던 데이터에 다시 접근하려는 경향을 말한다.
반복문에서 반복 횟수로 사용하는 변수를 예로 들 수 있다.
공간 지역성이란 메모리 상의 공간을 의미하며 최근 접근한 데이터의 주변 공간에 다시 접근하려는 경향을 말한다. 배열을 순회할 때 바로 옆의 메모리 공간에 접근하는 것을 예로 들 수 있다.
이렇듯 캐시 메모리는 주기적으로 교체 되어야 하는데 이 때 사용할 수 있는 알고리즘 중 하나가 시간지역성의 원리를 따른 LRU Cache이다.
LRU Cache
LRU Cache의 이론은 오랫동안 사용되지 않은 항목은 앞으로도 사용되지 않을 가능성이 높다를 전제로 하기 때문에, cache에서 가장 오랫동안 참조되지 않은 값을 제거한다.
LRU 방법은 그 성능이 입증되어, 현재 가장 많이 사용되는 알고리즘이기도 하다.
구현 방식
-
배열을 사용하여 구현하기
LRU Cache의 구현에는 많은 방법이 있지만 가장 간단하게 배열을 활용하는 방법이 있다.
먼저 값이 들어오면 배열에 하나씩 추가한다. 이후 배열이 가득 차면 가장 마지막 값을 제거하고 정렬한 후 맨 앞에 새로운 데이터를 넣는다.
이러한 방법은 구현에 있어서는 간단하지만 배열의 데이터 탐색과 정렬에 있어 O(n)의 시간 복잡도를 가지기 때문에 좋은 방법은 아니다. -
Linked List와 Hash map을 사용하여 구현하기
Double Linked List와 hash map을 사용하여 효율적인 알고리즘을 구현할 수 있다.
먼저 리스트를 통해 데이터의 순서를 유지한다.
Head에 가까운 데이터일수록 최근에 사용된 데이터이고,
Tail에 가까울수록 오랫동안 사용되지 않은 데이터로 간주한다.
그리고 hash map을 통해 데이터와 데이터의 리스트에서의 위치를 저장해 리스트에 빠른 접근을 할 수 있게 해준다.
새로운 데이터를 삽입할 때, tail의 값을 삭제시키고 head에 새로운 데이터를 삽입한다.
이 때 히트가 발생할 경우, 해당 데이터를 head로 옮겨준다.
이렇게 hasp map을 통한 O(1)의 데이터 접근과, linked list를 통한 O(1)의 삽입, 삭제로 총 O(1) 시간복잡도를 만족하여 구현할 수 있다.
참고 : LRU Cache 이해하기
참고 : velog/kms9887
