Arm Linux Kernel Hacks

공간 지역성과 시간 지역성을 활용해 캐시 알고리즘을 구성할 수 있다고 소개했습니다. 그런데 데이터 구조나 알고리즘을 사용할 때 메모리에 접근하는 패턴을 관찰하면 시간 지역성이나 공간 지역성을 확인하기 어려운 경우가 있습니다. 예를 들어, 링크드 리스트로 데이터를 관리할 때 메모리에 접근하는 패턴을 관찰하면 특정 위치에 있는 데이터에 다시 접근할 확률이 높지 않아 시간 지역성과 같은 특징을 지니지 않습니다. 

또한 링크드 리스트는 배열과 달리 인접한 메모리 주소 공간에 접근하지 않아 공간 지역성에도 맞지 않습니다. 그런데 코드를 유심히 분석하면 프로그램은 함수의 호출과 자료구조로 구성돼 있다는 사실을 알 수 있습니다. 자주 사용하는 자료 구조나 알고리즘은 어느 정도 정해져 있습니다. 예를 들어, 링크드 리스트나 스택과 같은 데이터 구조나 알고리즘을 사용해 데이터를 관리하는 패턴을 볼 수 있습니다. 

알고리즘의 특징을 활용해 프로그램이 메모리에 접근하는 패턴을 예측할 수 있는데, 이를 알고리즘 지역성이라고 합니다.
이번에는 간단한 예시 코드를 보면서 알고리즘 지역성에 대해 알아봅시다.

struct node {
02 struct node *next; // 다음 노드 주소를 저장
03 int data; // 데이터 저장 필드
04 };
05
06 struct node *curr = head->next; // 링크드 리스트 포인터에 첫 번째 노드의 주소를 저장
07 while (curr != NULL) // 노드의 포인터가 NULL이 아닐 때까지 실행
08 {
09 curr = curr->next; // 포인터에 다음 노드의 주소를 저장
10 process_data(curr); // process_data 함수를 호출해 노드를 처리
11 }

위 코드는 링크드 리스트를 구성하는 노드에 접근해 데이터를 처리하는 루틴입니다. 07 ~ 11번째 줄은 노드를 순회하면서 노드의 포인터가 NULL이 아닐 때까지 while 루프를 실행합니다. 그런데 링크드 리스트에 존재하는 자료 구조는 연속적인 메모리 공간에 위치하지 않습니다. 만약 링크드 리스트라는 자료 구조의 패턴을 미리 파악한다면 다음과 같이 처리할 수 있습니다.


06 struct node *curr = head->next; // 링크드 리스트 포인터에 첫 번째 노드의 주소를 저장
07 // 링크드 리스트를 순회하면서 노드 주소를 미리 로딩
08 while (curr != NULL) // 노드의 포인터가 NULL이 아닐 때까지 실행
09 {
10 curr = curr->next; // 포인터에 다음 노드의 주소를 저장
11 process_data(curr); // process_data 함수를 호출해 노드를 처리
12 }

이전 코드와 비교했을 때 달라진 점은 07번째 줄입니다. 07번째 줄은 미리 링크드 리스트를 순회해 노드포인터를 임시로 로딩하는 동작을 표현한 주석입니다. 07번째 줄과 같이 링크드 리스트를 미리 순회해 노드 포인터를 로딩하면 링크드 리스트를 구성하는 노드에 접근하는 08 ~ 12번째 줄의 실행 시간이 더 빨라질 것입니다.

링크드 리스트로 구성된 데이터를 어떤 패턴으로 접근할지는 예측이 가능한데, 이를 위해서는 링크드 리스트라는 자료구조와 알고리즘의 패턴을 이해해야 합니다. 알고리즘의 특징을 활용해 프로그램이 메모리에 접근하는 패턴을 예측하는 과정을 알고리즘 지역성이라고 합니다.