[Arm프로세서] 캐시 알고리즘: 알고리즘 지역성(algorithm locality)
By Guillermo Austin Kim | 2022년 5월 17일 |
프로그램은 함수의 호출과 자료 구조로 구성돼 있습니다. 코드를 유심히 분석하면 자주 사용하는 자료 구조나 알고리즘이 어느 정도 정해져 있습니다. 예를 들어 링크드 리스트나 스택과 같은 데이터 구조나 알고리즘을 사용해 데이터를 관리하는 패턴을 볼 수 있습니다. 그런데 데이터 구조나 알고리즘을 사용할 때 메모리에 접근하는 패턴을 관찰하면 시간 지역성이나 공간 지역성을 확인하기 어렵습니다. 한 가지 예를 들까요? 링크드 리스트로 데이터 관리할 때 메모리에 접근하는 패턴을 살펴보면 특정 위치에 있는 데이터에 다시 접근하지 않을 확률이 높습니다. 시간 지역성과 같은 특징을 지니지 않습니다. 또한 링크드 리스트는 배열과 달리 인접한 메모리 주소 공간에 접근하지 않아 공간 지역성에도 맞지 않습니다. 그런데 링크드