6.5 캐시 친화적인 코드 작성하기 (Writing Cache-Friendly Code)
6.2절에서 우리는 지역성(locality)의 개념을 소개하고, 무엇이 좋은 지역성을 구성하는지에 대해 정성적으로 이야기했습니다. 이제 캐시 메모리가 어떻게 동작하는지 이해했으므로, 더 정확하게 설명할 수 있습니다.
더 좋은 지역성을 가진 프로그램은 더 낮은 미스율(miss rate)을 보이는 경향이 있고, 더 낮은 미스율을 가진 프로그램은 더 높은 미스율을 가진 프로그램보다 더 빠르게 실행되는 경향이 있습니다. 따라서, 좋은 프로그래머는 항상 좋은 지역성을 갖는다는 의미에서 캐시 친화적인(cache-friendly) 코드를 작성하도록 노력해야 합니다.
캐시 친화적인 코드 작성을 위한 기본 접근법
- 일반적인 경우를 빠르게 만들어라 (Make the common case go fast).
프로그램은 종종 시간의 대부분을 몇 개의 핵심 함수(core functions)에서 보냅니다. 그리고 이 함수들은 시간의 대부분을 몇 개의 루프(loop) 안에서 보냅니다. 따라서, 핵심 함수의 내부 루프(inner loop)에 집중하고 나머지는 무시하십시오. - 핵심 내부 루프의 캐시 미스를 최소화하라 (Minimize the number of cache misses in each inner loop).
총 로드(load)와 스토어(store) 횟수 같은 다른 모든 조건이 동일하다면, 더 나은 미스율을 가진 루프가 더 빠르게 실행될 것입니다.
예제 1: 1차원 배열 합산 (sumvec)
이 접근법이 실제로 어떻게 작동하는지 보기 위해, 6.2절의 sumvec 함수를 다시 살펴봅시다.
int sumvec(int v[N])
{
int i, sum = 0;
for (i = 0; i < N; i++)
sum += v[i];
return sum;
}이 함수는 캐시 친화적일까요?
- 지역 변수
i와sum: 먼저, 루프 본문에서 지역 변수i와sum에 대해 좋은 시간적 지역성이 있음을 주목하십시오. 이 변수들은 지역 변수이기 때문에, 어지간히 괜찮은 최적화 컴파일러는 이 변수들을 메모리 계층의 최상위인 CPU 레지스터 파일에 캐싱할 것입니다. - 벡터
v에 대한 참조: 이제 벡터v에 대한 스트라이드-1(stride-1) 참조를 고려해 봅시다. 일반적으로 캐시의 블록 크기가B바이트일 때, 스트라이드-k 참조 패턴은 루프 반복당 평균적으로min(1, (워드 크기 × k) / B)만큼의 미스를 발생시킵니다. 이 값은k=1일 때 최소화되므로,v에 대한 스트라이드-1 참조는 정말로 캐시 친화적입니다.
예를 들어, v가 블록 경계에 정렬되어 있고, 워드는 4바이트, 캐시 블록은 4 워드(16 바이트)를 담을 수 있으며, 캐시가 초기에 비어있다고(cold cache) 가정해 봅시다. 그러면 캐시 구조와 상관없이, v에 대한 참조는 다음과 같은 히트/미스 패턴을 보일 것입니다.
| v[i] | i=0 | i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 |
|---|---|---|---|---|---|---|---|---|
| 접근 순서, [h]it or [m]iss | 1 [m] | 2 [h] | 3 [h] | 4 [h] | 5 [m] | 6 [h] | 7 [h] | 8 [h] |
이 예시에서, v[0]에 대한 참조는 미스를 발생시키고, v[0]~v[3]을 포함하는 해당 블록이 메모리에서 캐시로 로드됩니다. 따라서 다음 3번의 참조(v[1], v[2], v[3])는 모두 히트합니다. v[4]에 대한 참조는 새로운 블록이 캐시로 로드되면서 또 다른 미스를 유발하고, 다음 3번의 참조는 히트하는 식이 반복됩니다. 일반적으로, 4번의 참조 중 3번이 히트하게 되며, 이는 콜드 캐시 상태에서 우리가 할 수 있는 최선입니다.
sumvec 예제가 보여주는 두 가지 중요한 점은 다음과 같습니다.
- 지역 변수에 대한 반복적인 참조는 좋습니다. 컴파일러가 이들을 레지스터 파일에 캐싱할 수 있기 때문입니다 (시간적 지역성).
- 스트라이드-1 참조 패턴은 좋습니다. 메모리 계층의 모든 레벨에 있는 캐시는 데이터를 연속적인 블록으로 저장하기 때문입니다 (공간적 지역성).
예제 2 & 3: 2차원 배열 합산
공간적 지역성은 다차원 배열을 다루는 프로그램에서 특히 중요합니다. 행 우선 순서(row-major order)로 2차원 배열의 원소를 합산하는 sumarrayrows 함수를 생각해 봅시다.
// 좋은 예: 행 우선 순회 (Cache Friendly)
int sumarrayrows(int a[M][N])
{
int i, j, sum = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++) // 안쪽 루프가 행을 따라 순회
sum += a[i][j];
return sum;
}C언어는 배열을 행 우선 순서로 메모리에 저장하므로, 이 함수의 내부 루프는 sumvec과 동일하게 바람직한 스트라이드-1 접근 패턴을 가집니다. 위와 동일한 캐시 가정을 한다면, 배열 a에 대한 참조는 sumvec과 유사한 미스-히트-히트-히트 패턴을 보일 것입니다.
하지만, 겉보기에 무해해 보이는 루프 순서 변경을 적용하면 어떻게 될까요?
// 나쁜 예: 열 우선 순회 (Not Cache Friendly)
int sumarraycols(int a[M][N])
{
int i, j, sum = 0;
for (j = 0; j < N; j++) // 바깥 루프가 열을 따라 순회
for (i = 0; i < M; i++)
sum += a[i][j];
return sum;
}이 경우, 우리는 배열을 행 단위가 아닌 열(column) 단위로 스캔하게 됩니다. 만약 운이 좋아서 배열 전체가 캐시에 들어갈 수 있다면 1/4의 동일한 미스율을 누릴 것입니다. 하지만, 배열이 캐시보다 큰 경우(더 일반적인 경우), a[i][j]에 대한 모든 접근이 미스가 될 것입니다!
| a[i][j] | j=0 | j=1 | j=2 | j=3 | ... |
|---|---|---|---|---|---|
| i=0 | 1 [m] | 5 [m] | 9 [m] | 13 [m] | ... |
| i=1 | 2 [m] | 6 [m] | 10 [m] | 14 [m] | ... |
| i=2 | 3 [m] | 7 [m] | 11 [m] | 15 [m] | ... |
| i=3 | 4 [m] | 8 [m] | 12 [m] | 16 [m] | ... |
a[0][0]에 접근하면 해당 블록을 캐시에 가져오지만, 다음 접근인 a[1][0]은 메모리 상에서 N개의 원소만큼 멀리 떨어져 있어 완전히 다른 블록에 있습니다. 이 블록을 가져오면서 이전 블록을 쫓아낼 수 있습니다. a[2][0]도 마찬가지입니다. 결국 배열의 한 열을 다 훑고 다음 열의 첫 원소(a[0][1])로 돌아왔을 때는, 필요한 블록이 캐시에 남아있을 확률이 거의 없습니다.
높은 미스율은 실행 시간에 상당한 영향을 미칠 수 있습니다. 예를 들어, 필자의 데스크탑 머신에서 큰 배열 크기에 대해 sumarrayrows는 sumarraycols보다 25배 더 빠르게 실행됩니다.
요약하자면, 프로그래머는 자신의 프로그램에 있는 지역성을 인지해야 하며, 그것을 잘 활용하는 프로그램을 작성하도록 노력해야 합니다.
