Chiko IT
AI & Machine Learning

바이너리 서치를 이기는 Eytzinger layout — 캐시 친화적 배열 검색 실측

Chiko
11min read

목차

같은 O(log n)인데 두 배 차이가 나는 지점

정렬된 64비트 정수 1억 개에서 lookup을 돌리면, std::lower_bound와 branch-free binary search 계열이 lookup당 수백 나노초 구간에 머무는 반면, Eytzinger layout + prefetch 구현은 같은 데이터에서 그 절반 수준으로 떨어진다는 측정이 보고된다 (Khuong & Morin, Array Layouts for Comparison-Based Searching, Journal of Experimental Algorithmics, vol. 22, 2017). 비교 횟수가 같고 점근 복잡도도 같은데 거의 두 배 가까운 처리량 차이가 난다. 차이의 원인은 알고리즘이 아니라 메모리 접근 패턴 한 가지로 좁혀진다.

이 주제는 HackerNews에서 주기적으로 다시 올라온다. 최근에도 Algorithmica의 Array Layouts 챕터(2026년 3월 기준 v0.4)를 인용한 토론이 재점화됐다. 이번 글은 그 토론을 따라가며, 어디서부터 Eytzinger가 실제로 이기는지, 어디서는 오히려 손해인지를 실측 가능한 범위에서 정리한다.

정렬된 배열이 느려지는 구조적 원인

게다가, 정렬된 배열에 대한 binary search는 코드만 보면 캐시 친화적으로 보인다. 매번 절반씩 좁혀가는 단순한 패턴이다. 다만 실제 메모리 접근을 추적하면 그림이 다르게 나온다.

게다가, 크기 N의 배열에서 첫 비교는 a[N/2], 두 번째는 a[N/4] 또는 a[3N/4], 세 번째는 8분할 지점이다. 처음 몇 번의 접근은 배열의 서로 멀리 떨어진 위치를 짚는다. 마지막 몇 번에서야 인접한 원소를 본다. N이 L1 캐시(보통 32KB)를 넘어가면 처음 절반의 비교는 거의 모두 캐시 미스가 된다. N이 L3(수 MB~수십 MB)을 넘어가면 미스 비용이 DRAM latency, 즉 70~100ns 수준까지 올라간다.

이처럼, 여기에 분기 예측이 한 겹의 비용을 더 얹는다. binary search 루프의 비교 결과는 입력 키와 데이터 분포에 따라 사실상 무작위에 가깝다. CPU의 branch predictor 입장에서는 50% 확률 분기가 가장 어려운 경우다. 최근 Intel·AMD 마이크로아키텍처에서도 이런 분기는 미스율이 30~50%에 달한다는 측정이 여러 곳에서 인용된다.

perf로 본 hot path

결국, bottleneck을 처음 확인한 경로는 Cursor에 perf record 결과를 붙여넣고 "이 hot loop에서 stall이 어디 생기는지 분석해달라"고 시킨 흐름이었다. Claude가 perf stat 출력에서 cycle_activity.stalls_l3_miss와 branch-misses 비율을 짚어주면서 cache miss와 branch mispredict가 거의 절반씩 cycle을 잡아먹고 있다고 답했다. perf 매뉴얼을 펴고 카운터 이름을 찾는 시간을 30분 정도 줄였다는 게 체감이다 (개인적으로 이런 분석 보조에서 LLM의 가성비가 가장 좋게 나온다).

그 결과 두 가지가 분명해졌다. hot path는 binary search 그 자체였고, stall은 branch와 cache miss에서 거의 다 왔다. 알고리즘을 바꾸지 않고 풀려면 이 둘을 동시에 줄여야 한다.

Eytzinger layout — heap을 검색에 쓴다

Eytzinger layout은 정렬된 데이터를 binary heap과 동일한 방식으로 1차원 배열에 펼친 배치다. 16세기 계보학자 Michael Eytzinger가 가계도를 표 형태로 그릴 때 사용한 인덱싱이 어원이다.

핵심은 단순하다. 1-based 인덱스 기준으로 노드 k의 왼쪽 자식이 2k, 오른쪽 자식이 2k+1이다. 부모는 k/2다. 정렬된 입력 [1, 2, 3, 4, 5, 6, 7]을 Eytzinger 배치로 옮기면 [_, 4, 2, 6, 1, 3, 5, 7]이 된다(0번 칸은 사용하지 않음). 즉 in-order 순회의 결과가 원래 정렬 순서가 된다.

즉, 검색 알고리즘 자체도 heap을 따라 내려가는 것과 같다. k=1에서 시작해, 키가 a[k]보다 크거나 같으면 k = 2k+1, 작으면 k = 2k로 이동한다. k > n이 되면 종료, 마지막에 들어온 경로에서 "가장 가까운 왼쪽 분기" 시점이 lower_bound 위치다.

항목 정렬 배열 binary search Eytzinger layout 검색
비교 횟수 ⌈log₂(N+1)⌉ ⌈log₂(N+1)⌉
첫 접근 위치 a[N/2] a[1]
자식 인덱스 계산 산술 평균 비트 시프트 1회
prefetch 가능성 어렵다 자연스럽다
메모리 오버헤드 0 0 (재배치만)

이 표에서 가장 결정적인 줄은 prefetch 가능성이다. 정렬 배열 binary search는 다음에 볼 인덱스가 현재 비교 결과에 의존한다. 분기 결과를 알기 전에는 다음 주소를 미리 짐작하기 어렵다. Eytzinger는 다르다. k에서 다음 두 후보가 2k, 2k+1이고, 그 다음 네 후보는 4k부터 4k+3이다. 한 번의 비교 결과와 무관하게 이후 몇 단계의 접근 주소가 미리 계산된다. 이 차이가 prefetch 명령을 의미 있게 만든다.

분기를 없애고 prefetch를 끼우는 코드

또한, Khuong이 블로그 글 Binary Search eliminates Branch Mispredictions(2012년 작성, 이후 갱신)에서 정리한 코드를 따라가면 두 가지 최적화가 한 줄에 다 들어간다.

// Eytzinger layout 기반 lower_bound
// a[0]은 사용하지 않고, 유효 인덱스는 1..n
int eytzinger_search(const int *a, int n, int x) {
    int k = 1;
    while (k <= n) {
        // 4단계 아래(약 16 entry, 한 cache line)를 미리 끌어온다
        __builtin_prefetch(a + k * 16);
        // 조건부 이동을 분기 없이 처리
        k = 2 * k + (a[k] < x);
    }
    // 마지막에 "오른쪽으로만 내려간" 경로를 잘라내 rank를 복원
    k >>= __builtin_ffs(~k);
    return k;
}

예를 들어, 세 가지 트릭이 들어가 있다.

실제로, 첫째, k = 2 * k + (a[k] < x) 한 줄로 분기를 없앴다. 비교 결과를 0/1로 더해 인덱스를 갱신하므로 if/else 분기가 사라진다. CPU는 매 iteration마다 동일한 산술 명령만 실행한다. branch mispredict 페널티가 0이 된다.

특히, 둘째, __builtin_prefetch(a + k * 16)이 4단계 아래의 데이터를 미리 캐시로 끌어온다. cache line이 64바이트, int가 4바이트라고 하면 한 라인에 16개가 들어간다. 깊이 4 아래의 노드 인덱스는 16k부터 16k+15까지 분포하므로 한 cache line에 그대로 정렬된다. 다음 4번의 비교에 필요한 데이터가 한 번에 올라온다.

반면, 셋째, 종료 후의 비트 연산 k >>= __builtin_ffs(~k)는 마지막에 우측으로만 이동한 경로를 잘라내고, "마지막으로 좌측 자식을 골랐던" 시점의 인덱스를 복원한다. 이 인덱스가 곧 lower_bound 결과다.

옮겨 적을 때 자주 틀리는 지점

위 코드를 코드베이스에 옮기면서 두 가지 함정이 자주 보고된다. 하나는 1-based 인덱스 가정이다. C/C++ 표준 컨테이너는 0-based이므로, 빌드용 변환 함수에서 첫 칸을 비워두는 처리를 깜박하면 off-by-one이 난다. 다른 하나는 __builtin_ffs가 1-based 결과를 돌려주고 입력이 0일 때 정의되지 않는다는 점이다. n이 2^k - 1 형태가 아닌 일반 길이일 때 종료 조건과 맞물려 미묘한 버그가 난다. Khuong의 원본 글 댓글 스레드에도 동일한 지적이 여러 번 등장한다.

어디서부터 이기는가 — 측정 가능한 임계점

예를 들어, 여기서부터는 "어디서 누구를 이기는가"의 영역이다. Khuong & Morin 논문 Table 5와 Figure 6에 정리된 측정에 따르면 임계점은 대체로 L2 캐시 크기(보통 256KB~1MB) 근처다. 이보다 작은 배열에서는 표준 binary search나 branch-free 변형이 더 빠르거나 비슷하게 나온다. 캐시 안에 데이터가 다 들어가면 cache miss 자체가 안 나기 때문에 prefetch가 손해가 된다. 불필요한 메모리 트래픽만 추가된다.

배열이 L2를 넘기 시작하면 격차가 벌어진다. L3 영역에서는 격차가 분명해지고, DRAM 영역에서는 두 배 근처까지 벌어진다는 측정이 반복적으로 인용된다. Algorithmica의 Array Layouts 챕터(2026년 3월 v0.4 기준)에는 동일한 경향이 더 큰 N에서도 유지된다는 후속 측정이 정리되어 있다.

N (4바이트 정수 기준) 데이터 크기 일반적으로 빠른 쪽
≤ 1만 40KB 이하 std::lower_bound (branch-free)
10만 ~ 100만 400KB ~ 4MB 비슷함, 입력 분포에 민감
100만 이상 4MB 이상 Eytzinger + prefetch

이 표는 일반 데스크톱·서버 CPU(L1 32KB, L2 256KB~1MB, L3 8MB~32MB)를 가정한 값이다. 임베디드나 ARM Cortex 계열처럼 캐시 계층이 다른 환경에서는 임계점이 다르게 잡힌다. 실제 도입 전에는 자기 환경에서 N을 바꿔가며 곡선을 직접 그려보는 게 안전하다.

한계 — 작은 배열, 동적 변경, 메모리 정렬

Eytzinger layout의 약점은 분명하다. 첫째, 데이터를 한 번 재배치해야 한다. 정렬된 배열을 Eytzinger 순서로 재배치하는 비용은 O(N)이지만, in-place로 하기 까다로워 보통 별도 버퍼에 in-order 순회로 채워넣는다. 데이터가 자주 갱신되는 워크로드(insert/delete가 많은 경우)에서는 매번 재배치 비용이 커지므로 현실적으로 쓰기 어렵다. 정적 lookup 테이블, 빌드 타임에 한 번 만들어두는 사전류, read-mostly 인덱스에 적합하다.

둘째, 작은 배열(L2에 다 들어가는 수준)에서는 오히려 손해다. cache miss가 안 나는 구간에서 prefetch 명령이 cycle을 추가로 잡아먹는다. branch-free binary search가 이 구간에서는 가장 단순하고 빠른 선택이 된다.

게다가, 셋째, 메모리 오버헤드는 0이지만 정렬 요건이 까다롭다. cache line 경계에 맞춘 padding이 필요하고, NUMA 환경에서는 첫 페이지 할당 위치까지 신경을 써야 한다. 이 부분은 직접 다 해보지 못했고, Khuong의 글과 Algorithmica 챕터의 권고를 그대로 따르는 정도에 머물러 있다.

즉, 이런 제약을 통과하는 영역, 예컨대 게임 엔진의 정적 스프라이트 룩업, 검색 엔진의 사전 인덱스, in-memory OLAP의 sorted column lookup처럼 한 번 빌드해두고 수억 번 조회하는 케이스에서는 도입 가치가 있다. 당장 실험해볼 항목은 세 가지로 좁혀진다. (1) 현재 코드의 lookup 경로를 perf로 측정해 cache miss 비율이 30% 이상 나오는지 확인한다, (2) Khuong의 코드를 그대로 가져와 N이 100만 이상인 인덱스에 한정해 A/B 벤치를 돌린다, (3) prefetch distance를 k*8, k*16, k*32로 바꿔가며 자기 CPU의 sweet spot을 찾는다. 현재로서는 Khuong & Morin 측정 범위를 벗어난 입력 분포에서의 안정성은 더 지켜봐야 한다.

관련 글

More posts