퀵, 힙, 인트로 정렬의 캐시 친화성

들어가기 전에...

• 이 글은 이 글의 댓글로 언급된 퀵정렬, 힙정렬, 인트로(하이브리드) 정렬에 대해 다룹니다.
• 캐시 환경을 가정하고 퀵, 힙정렬의 캐시 미스 횟수를 셉니다. 실제 환경과는 차이가 있겠으나, 구조적 약점 파악에는 충분한 도움이 됩니다.

캐시 친화성이란

지난 글에서 캐시 히트와 캐시 미스에 대해 공부했는데, AI가 지나치게 하드웨어에 집중해서 작성했던 글이기 때문에 다소 어렵게 느껴졌다. 그래서 AI가 언급한 여러 하드웨어의 이름들은 차치하고서, 큰 흐름만 여기에 요약해본다.

CPU가 데이터를 찾는 큰 흐름

• CPU가 데이터에 접근해야할 때 먼저 캐시를 탐색한다
• L1 캐시, L2캐시, L3 캐시를 순서대로 탐색하고, 데이터가 발견되지 않았다면 메인 메모리로 접근한다. 뒤로 갈 수록 오래걸린다.
• 캐시 히트란 원하는 데이터가 캐시에 있어서 빠르게 데이터를 발견하는 것을 말하고
• 캐시 미스는 반대로, 캐시에서 데이터가 발견되지 않아 메인 메모리에서 데이터를 가져와야 하는 경우이다.

캐시의 지역성

• 시간적 지역성: 방금 접근한 데이터는 바로 또 쓸 가능성이 높다. (루프 변수, 이터레이터)
• 공간적 지역성: 캐시는 데이터를 캐시 라인(64Byte) 단위로 가져오므로, 인접 메모리가 통째로 캐시에 올라온다. 즉, 방금 접근한 데이터 주소의 근처 데이터도 캐싱 효율이 높다.

캐시 친화적

• 캐시 미스는 적고 캐시 히트는 많다. 또는 그런 구조.

정렬 알고리즘의 캐시 친화성

퀵정렬, 힙정렬의 상세한 알고리즘은 이 글에서 다루지 않습니다.

퀵정렬의 경우 Hoare 방식의 탐색을 사용한다고 가정합니다.

캐시 용량과 캐시 라인

캐시 용량이란 이름 그대로 캐시가 저장할 수 있는 용량이며, 캐시 라인은 캐시가 데이터를 로드하는 단위이다.

보통 캐시 라인은 64Byte크기이다.

여기서는 캐시가 단 하나의 캐시 라인만을 저장할 수 있다고 가정하여, 캐시 용량을 64Byte로 설정하겠다.

• 캐시 용량은 보통 kbyte단위이다

따라서 단 하나의 캐시 라인에 대해서 캐시 히트, 그 외의 데이터에 대해서는 캐시 미스가 발생한다.

위는 힙정렬과 퀵정렬의 캐시 친화성의 차이를 극단적으로 보여주기 위한 예시이고, 실제로는 배열의 길이가 매우 길 때 이와 비슷한 현상이 발생할 것이다.

32개의 int형 데이터 배열에 대한 퀵정렬과 힙정렬의 비교

길이가 32인 int배열의 크기는 32 * sizeof(int) = 128Byte로, 전체 데이터가 캐시에 보관될 수 없다

• 앞서 캐시 용량을 64Byte로 가정했기 때문이다.

힙정렬의 경우 index == 1을 root 노드로 사용하여 데이터 32개를 담으려면 배열의 크기가 33이 되어야 하는데, 이 경우 캐시 라인 3개를 사용하게 되어 글의 취지에 어긋나므로 데이터를 31개만 사용하였다.

• 즉, 퀵정렬은 32개, 힙정렬은 31개를 정렬한다.

이 점에 유의하여 두 정렬 방식이 몇 번의 캐시 미스를 유발하는지 비교한다.

퀵정렬의 경우(Hoare)

레벨 1. 파티션 1개

do { left++; } while(arr[left] < pivot); 을 수행한다. 즉, left가 arr[0]에서 시작하여 최대 arr[31]까지를 참조하는 과정에서 두 번의 미스가 발생할 것이다.

• arr[0]에서 미스: arr[0..15]가 캐시에 저장됨.
  • 캐시는 sizeof(int) * 16개 = 64Byte의 캐시 라인 단위로 읽기 때문
• arr[16]에서 미스: arr[16..31]이 캐시에 저장됨

do { right--; } while(arr[right] > pivot); 을 수행한다. right가 arr[31]에서 시작하여 최대 arr[0]를 참조한다. 이 과정에서 right가 left를 추월하면 파티션 단계가 종료된다.

• arr[16..31]은 캐시 히트. 아까 로드 했으므로.
• 만약 arr[15]을 탐색하면 미스. 또는 그 전에 right가 left를 추월했다면 미스 발생 안 함.

left와 right의 교차 지점이 어떤 캐시라인이냐와는 무관하게 최소 2회 미스가 발생한다.

• 최초 로드 시
• left 또는 right가 경계(arr[15] ~ arr[16])를 넘을 때

두 포인터가 교차 이전에 멈추면 둘을 swap하는데, 둘이 다른 CL(Cache line)에 있으면 최대 4회의 미스가 추가로 발생한다.

이는 데이터의 구조에 따라 천차만별의 횟수가 된다. 구조적 약점만 보기 위해 0회로 간주한다.

파티션 2개

이제 각 파티션 [0..k]와 [k+1..31]을 탐색한다.

• left 파티션에서 미스 1회가 발생한다(데이터 로드)
  • k <= 15라면, right 파티션에서 미스 1회가 발생한다(경계 arr[16] 접근)
  • k > 15라면, left 파티션에서 미스 1회가 발생한다(경계 arr[16] 접근)

따라서 최대 2회 캐시 미스가 발생한다.

파티션 4개, 8개, 16개

다음은 파티션이 총 4개인 경우이다. 전체 데이터가 캐시 라인 2개로 구성되므로, 각 레벨 당 2회의 미스가 발생할 것이다.

• arr[0..15] 로드시 미스
• arr[16..31] 로드시 미스
• 스왑 과정에서는 미스가 발생하지 않는다. arr[left]와 arr[right]가 같은 파티션에 위치, 즉 같은 캐시라인에 있기 때문이다.

따라서 2회 * 3레벨 = 6회 캐시 미스가 발생한다.

(파티션 32개인 경우는 없다. 배열의 크기가 32이므로 배열 크기가 1인데, left와 right의 교차 조건이 즉시 달성되므로 데이터 접근이 없기 때문이다)

결과

위 과정에서 발생한 캐시 미스를 전부 합치면...

• 1레벨 2회
• 2레벨 2회
• 3레벨 이상 6회
• 10회다.

힙정렬의 경우

앞서 언급했듯이, 힙정렬은 데이터를 31개만 사용한다. 트리 구조는 아래와 같을 것이다.

• 깊이 0, root 노드 1개: arr[1]
• 깊이 1, 노드 2개: arr[2..3]
• 깊이 2, 노드 4개: arr[4..7]
• 깊이 3, 노드 8개: arr[8..15]
• 깊이 4, 노드 16개: arr[16..31]

이 경우 캐시 라인의 경계는 깊이 3과 깊이 4의 사이가 된다. 앞의 퀵 정렬과 동일하게 arr[15..16]가 경계이기 때문이다.

편의를 위해 arr[0..15]를 CL0, arr[16..31]을 CL1라고 부르자. CL은 Cache Line의 약자이다.

Build Heap

먼저, sift-down 방식으로 힙을 build한다. 주어진 배열을 힙 구조에 맞게 바꾸는 과정이다. Max, Min Heap 모두 동일하다.

• arr[15]에 접근한다. 캐시 미스 발생, CL0이 로드된다. 이제 자식과의 비교를 위해...
  • 자식 arr[30]에 접근한다. 캐시 미스 발생, CL1이 로드되고 CL0은 퇴출된다.
  • 자식 arr[31]에 접근한다. 캐시 히트이다. CL1이 앞서 로드되었기 때문이다.
  • 자... 여기서 캐시 미스가 2번 발생했다.
• arr[14]에 접근한다. 캐시 미스 발생, CL0이 로드되고 CL1이 퇴출된다.
  • 자식 arr[28]에 접근한다. 캐시 미스 발생, CL1이 로드되고 CL0은 퇴출된다.
  • 자식 arr[29]에 접근한다. 캐시 히트 발생.
  • 자... 여기서도 캐시 미스가 2번 발생했다.
• arr[13], arr[12], ..., arr[9]까지의 index에 대해 마찬가지의 과정이 반복된다.
  • 5개의 과정에 대해 캐시 미스가 각 2번, 총 10번 발생했다...
• arr[8]에 접근한다. 캐시 미스 발생. CL0이 로드된다.
  • arr[16]에 접근한다. 캐시 미스 발생. CL1이 로드되고 CL0은 퇴출된다.
  • arr[17]에 접근한다. 캐시 히트 발생.
  • 여기서도 캐시 미스가 2번 발생했다.
• arr[7]에 접근한다. 캐시 미스 발생. CL0이 로드된다.
  • arr[14]와 arr[15]에 접근한다. 캐시 히트 발생.
    • 만약 arr[7]과 arr[14]가 바뀌었다면, arr[28]과 arr[29]도 참조한다.
    • 또는 만약 arr[7]과 arr[15]가 바뀌었다면, arr[30]과 arr[31]을 참조한다.
    • 두 경우 모두 캐시 미스가 1회 추가로 발생한다.
  • 캐시 미스가 1회 발생하고, 추가로 1회 더 발생할 수 있다.
  • 최악의 경우를 상정하면 2회의 미스가 발생한다.
• arr[6]에 접근한다.
  • 캐시 히트. 그러나 이전 단계의 노드(arr[7])가 자식과 swap되었다면 캐시 미스이다.
    • 이전 단계에 CL1을 로드했는데, arr[6]은 CL0이기 때문이다.
  • arr[12]와 arr[13]에 접근한다. 캐시 히트.
    • arr[6]이 자식과 swap되면 이전 단계와 마찬가지로 캐시 미스가 1회 더 발생할 수 있다.
  • 따라서 최악의 경우 2회의 미스가 발생한다.
• arr[5]에 접근한다.
  • arr[6]의 경우와 같다. 최악의 경우 2회의 미스가 발생한다.
• arr[4]에 접근한다.
  • arr[6]의 경우와 같다. 최악의 경우 2회의 미스가 발생한다.
• arr[3]에 접근한다.
  • 이전 단계에서 CL1에 접근했다면 캐시 미스, 아니면 캐시 히트다.
  • arr[6], arr[7]에 접근한다. 캐시 히트
    • 스왑시 arr[12..15]에 접근한다. 캐시 히트
      • 스왑시 arr[24..31]에 접근한다. 캐시 미스(CL1에 접근)
  • 최악의 경우 2회의 미스가 발생한다.
• arr[2]에 접근한다.
  • arr[3]의 경우와 같다. 최악의 경우 2회의 미스가 발생한다.
• arr[1]에 접근한다.
  • 이전 단계에서 CL1에 접근했다면 캐시 미스, 아니면 캐시 히트다.
  • arr[2], arr[3]에 접근한다. 캐시 히트
    • 스왑시 arr[4..7]에 접근한다. 캐시 히트
      • 스왑시 arr[8..15]에 접근한다. 캐시 히트
        • 스왑시 arr[16..31]에 접근한다. 캐시 미스(CL1에 접근)

그래서 총 몇 번의 캐시 미스가 발생하느냐...

• 깊이 4의 노드 16개는 접근하지 않으므로 0개다. sift-down의 과정에서 자식이 없어서 탐색할 필요가 없기 때문이다.
• 깊이 3의 노드 8개에서 2회 발생하므로 총 16회
• 깊이 2의 노드 4개에서 최악 2회 발생하므로 총 8회
• 깊이 1의 노드 2개에서 최악 2회 발생하므로 총 4회
• 깊이 0의 루트 노드에서 최악 2회 발생하여 총 2회
• 그럼 합계 30회

Extract

지금까지 한 것은 힙을 구성하는 과정이다. 이제 힙을 만들었으니 하나씩 데이터를 빼보자.

데이터를 뺄 때마다, arr[1]과 arr[힙 크기]의 swap이 발생한다.

처음 16회의 추출은 아래와 같다.

• arr[1] 추출. 캐시 미스(CL0 최초 로드)
• arr[1]과 arr[힙 크기] 스왑.
  • 힙크기 >= 16이므로 캐시 미스 발생
• sift-down
  • arr[1] 접근. 캐시 미스
  • sift-down
    • arr[2..15]는 캐시 히트.
    • arr[16..31]에 접근하면 캐시 미스.
• 위 과정에서 최악의 경우 캐시 미스 3회 + 스왑 발생

서로 다른 캐시 라인의 요소 간 swap 한 번에 4회의 미스가 발생한다

• A읽기
• B읽기
• A쓰기
• B쓰기

구조적 약점만을 보기 위해 swap을 제외하면 3회의 미스가 발생한다.

• 3회는 각각 아래와 같다.
  • arr[1] 추출
  • sift-down에서 arr[1] 접근
  • sift-down에서 CL1 접근

이제 다음 16회의 추출을 보자.

• arr[1]을 추출. 캐시 미스(최초 CL0 로드시에만)
• arr[1]과 arr[힙크기] swap. 캐시 히트.
• sift-down. 캐시 히트.
• 애초에 힙크기 < 16이라서 전 과정에서 캐시 히트다.
• 따라서 캐시 미스는 1회다.

그럼 총 16회 * 3번 + 1번 = 49회의 캐시 미스가 발생할 수 있다. 스왑을 제외한 경우이고, 퀵정렬에 비해 스왑이 더 빈번하게 발생하는 구조적 특징으로 인해 실제 캐시 미스는 훨씬 많을 것이다.

결과

• Build 과정에서 30회
• Extract 과정에서 49회
• 총 79회

두 정렬의 비교

퀵정렬은 10회, 힙정렬은 79회가 발생했다. 이는 swap시 발생할 수 있는 캐시 미스 횟수를 제외한 수치이므로 실제와는 큰 차이가 있다.

그러나 구조적으로 swap을 유발하는 빈도는 힙정렬 쪽이 더 잦다.

퀵정렬

• left right가 다른 CL에 있으면서 교차하지 못한 채 멈췄을 때, 두 포인터를 swap
• left right가 교차 했을 때, 피벗과 교차지점 swap

힙정렬

• 추출 직후 마지막 노드를 가져올 때. 마지막 노드가 있던 자리에 데이터를 입력할 필요는 없으므로 최대 캐시 미스 1회 적게 발생. 통상 swap은 최대 4회.
• sift down에서 자식과 swap할 때.

좌우지간 퀵정렬보다 힙정렬이 더 많은 캐시 미스를 유발함은 변함이 없을 것이다.

인트로정렬(하이브리드)

다음은 위키백과에서 가져온 인트로정렬 의사코드이다.

procedure sort(A : array):
    let maxdepth = ⌊log2(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n < 16:
        insertionsort(A)
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[1:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

잘 보면 insertionsort, heapsort, partition의 세 정렬 방법을 섞어 쓰는 것을 볼 수 있다. partition은 퀵정렬을 통해 도출한 피벗을 반환한다고 볼 수 있겠다.

삽입 정렬이 포함되는 이유

삽입 정렬(insertionsort)이 섞여있는데, 삽입 정렬의 알고리즘 아이디어는 간단하다.

• arr[0]을 정렬된 1칸 짜리 배열로 간주하고, 이를 output 배열로 한다.
• arr[1..n]까지의 요소들을 앞의 output 배열의 어느 위치에 넣을지 판단한다.
  • 단순히 output 배열의 0부터 순회하면서 비교하면 된다.

이 알고리즘의 단점은 데이터의 개수인데, 시간 복잡도가 최악 O(n^2) 로 크지만 n이 작으면 아래의 장점이 부각된다.

• 바로 초 간단해서 오버헤드가 적다는 것.
  • n이 충분히 작으면 다른 정렬이 파티션을 나눈다거나 힙을 만든다거나 하는 것보다 단순히 삽입 정렬을 해버리는 것이 오버헤드가 더 적다고 한다.
• 또, 캐시 친화성이 매우 좋다는 장점도 있다.
  • 4Byte 데이터를 기준으로 정렬할 때에는 캐시 라인에 16개가 들어온다. 그래서 인트로 소트 기준이 16이다.
    • 이 임계값 16은 상황에 따라 바꿀 수 있다. 환경에 따라 너무 다양해서 필요하다면 실측을 통해 값을 찾아야 한다.
    • 예시) SIMD 사용이 가능한 경우: Unity의 Burst Compiler는 SIMD 최적화를 지원하는데, 한 번에 여러 연산이 가능해지므로 삽입 정렬에 유리해진다. 이를 테면 index == 0에 삽입 하여 뒤의 요소를 다 한 칸 씩 밀어야 할 때, 하나 씩 미는 게 아니라 여러 개를 동시에 밀어버리니 O(n)이 걸리던 것을 O(n/8)로 줄이는 느낌이다.
  • 데이터의 크기가 16 미만일 때 삽입 정렬을 수행하므로 최초 데이터 로드시의 미스를 제외하면 정렬 과정에서 전부 캐시히트된다. 캐시 친화성이 높은 삽입 정렬에게 특히 유리한 것이다.

log2(len) * 2으로 퀵정렬과 힙정렬을 나누는 이유

인트로 정렬의 depth가 log2(len) * 2 이상이 되면 퀵정렬에서 힙정렬로 전환하는데, 이는 퀵정렬의 피벗 선택이 연속해서 잘못되는 상황을 피하기 위함이다.

아까 예시로 든 32개의 int 정렬에서 퀵정렬의 재귀 깊이가 5였는데, 이는 이상적인 경우 퀵정렬이 log2(n)만큼의 재귀를 하기 때문이다. 그러나 피벗 선택의 운이 나빠서 16:16 분할이 아니라 1:31 등의 극단적인 분할을 계속하게 되면, 재귀 깊이가 계속해서 증가하므로 최악의 경우 O(n^2)만큼의 시간이 걸린다.

재귀 깊이 log2(len) * 2의 기준은 그 불리한 상황을 피하기 위해 설정된 값으로, 다소 운이 나쁜 것은 감안하도록 *2가 붙었다. 참고로 median-of-3 로 피벗을 선택하므로 어느 정도 안전장치가 있긴 하다.

median-of-3: arr[0], arr[n - 1], arr[n/2] 중 중앙값을 피벗으로 선택

인트로정렬의 강점

이 정렬 방식은 삽입 정렬, 퀵정렬, 힙정렬의 장점만을 취하도록 설계된 복합적인 정렬 - 하이브리드 정렬이다. 결론적으로 이 정렬 알고리즘은 최악의 경우에도 O(nlogn)의 성능을 유지할 수 있다.

퀵, 힙정렬은 O(nlogn) 으로 알려져있다.

삽입 정렬은 O(n^2)로 알려져 있으나, n < 16에서 상수 계수가 퀵, 힙에 비해 작아서 O(nlogn)보다 좋은 성능이 나온다. 캐싱 효율은 덤

끗.

캐시 미스 횟수를 일일이 세는 일은 다시는 하지 않으련다