이진 검색보다 빠르게 만들 수 있음

 (lemire.me)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 정렬된 배열에서 값을 찾을 때 흔히 쓰는 이진 검색은 한 번에 하나의 값만 비교하지만, 최신 CPU는 한 명령으로 여러 값을 동시에 비교할 수 있어 이 능력을 활용하면 검색 속도를 크게 높일 수 있음
  • SIMD Quad는 배열을 16개씩 블록으로 나눈 뒤, 블록 위치는 4진 보간 검색으로 빠르게 좁히고 블록 내부는 SIMD 명령어로 16개 원소를 한꺼번에 비교하는 계층형 검색 알고리듬
  • 벤치마크에서 Intel warm 캐시 기준 이진 검색 대비 2배 이상 빠른 성능을 보였고, Apple cold 캐시에서도 2배 이상 빨랐으며, 모든 측정 조건에서 std::binary_search보다 우수
  • 이진 검색을 반으로 나누는 대신 4분할하면 명령어 수는 약간 늘지만, Intel 대형 배열에서 메모리 수준 병렬성을 더 잘 활용해 cold 캐시 성능이 개선됨
  • 교과서 알고리듬이 오늘날 CPU의 데이터 병렬성과 메모리 병렬성을 전제하지 않고 설계되었기 때문에, 하드웨어 특성을 반영한 재설계로 실질적 성능 향상이 가능

핵심 아이디어

  • 이진 검색은 한 번에 값 하나만 비교하는 구조이지만, 최신 64비트 ARM과 x64 프로세서는 한 명령으로 16비트 정수 8개를 동시 비교할 수 있음
  • 이 하드웨어 능력을 활용하면 검색 단위를 개별 원소가 아닌 블록 단위로 바꿔 비교 횟수를 대폭 줄일 수 있음
  • 배열을 반으로 나누는 대신 4분할(4진 검색) 하면 명령어 수는 약간 늘어도 병목이 명령어 수가 아닐 가능성이 크며, 메모리 수준 병렬성도 더 잘 활용 가능

정렬 배열 멤버십 검사의 기본 방식

  • 정렬된 배열에서 값 존재 여부를 확인하는 가장 단순한 방법은 값을 하나씩 훑는 선형 검색이며, C++에서는 std::find로 같은 효과를 낼 수 있음
  • 큰 배열에서는 이진 검색이 더 빠르며, 검색 구간의 가운데 값을 기준으로 상·하반을 버리는 과정을 반복
  • C++의 std::binary_search는 값 존재 여부를 불리언으로 반환
  • Roaring Bitmap 형식은 크기 1~4096의 16비트 정수 배열을 사용하며, 값 존재 여부 확인에 이진 검색을 사용

SIMD Quad 알고리듬 구조

  • 16비트 부호 없는 정수의 정렬 배열을 16개 원소의 고정 크기 블록으로 분할
  • 각 블록의 마지막 원소를 보간 키로 사용해 대상 값이 있을 가능성이 높은 단일 블록으로 범위를 좁힌 뒤, 그 블록의 16개 원소를 SIMD로 동시 검사
  • 동작 단계:
    • 원소 수가 16개보다 적으면 전체를 단순 선형 검색
    • 배열을 16개 연속 원소 블록으로 나누고, 전체 블록 수는 num_blocks = cardinality / 16
    • 블록 마지막 원소를 키로 사용해 현재 검색 범위의 1/4 지점들을 대상 값과 비교하고 base를 조정
    • 유효한 블록이면 ARM에서는 NEON, x64에서는 SSE2로 16개 원소를 로드해 병렬 동등 비교 수행
    • 전체 블록에 포함되지 않는 나머지 원소는 선형 검색

벤치마크 방식

  • 배열 크기 2~4096 각각에 대해 16비트 부호 없는 정수의 정렬 배열 100,000개 생성
  • 각 크기마다 두 가지 모드로 멤버십 질의 1,000만 번 수행
    • cold 모드: 각 질의가 다른 배열을 검색해 캐시 미스를 시뮬레이션
    • warm 모드: 같은 배열을 100번 연속 검색해 캐시 히트를 시뮬레이션
  • 측정 대상은 평균 질의 시간이며, 비교 대상은 선형 검색(std::find), 이진 검색(std::binary_search), SIMD Quad
  • 측정 시스템은 Apple M4(Apple LLVM)와 Intel Emerald Rapids(GCC)

측정 결과

  • 배열이 커지면 이진 검색이 선형 검색을 확실히 이기며, cold 캐시에서는 데이터 접근이 많아 선형 검색이 더 불리
  • Intel 플랫폼: warm 캐시에서 SIMD Quad가 이진 검색보다 2배 이상 빠름, cold 캐시에서는 이득이 더 작음
  • Apple 플랫폼: cold 캐시에서 SIMD Quad가 2배 이상 빠름, warm 캐시에서는 이득이 더 제한적
  • 모든 경우에서 SIMD Quad는 std::binary_search보다 빨랐음
  • SIMD 부분은 특수 명령어로 작업을 줄이며, 명령어와 분기가 더 적어 속도 향상의 원인이 명확

4진 검색의 효과

  • SIMD 최적화는 유지하되 4진 보간 검색을 이진 검색으로 바꾼 SIMD binary 버전도 비교
  • Apple 플랫폼에서는 4진 접근의 효과가 작았음
  • Intel 플랫폼에서는 큰 배열의 cold 캐시 상황에서 4진 접근이 의미 있는 최적화
  • Intel 서버에서는 4진 검색이 메모리 수준 병렬성을 더 잘 활용

구현 핵심

  • simd_quad 함수는 uint16_t 배열, 원소 수 cardinality, 찾을 값 pos를 받아 불리언 반환
  • gap은 16으로 고정, cardinality < gap이면 단순 반복문으로 검색
  • 블록 검색 루프는 n > 3 동안 1/4, 2/4, 3/4 지점의 블록 마지막 값을 읽어 비교하고, 세 비교 결과의 합으로 base를 이동
  • 선택된 블록은 ARM NEON의 vceqq_u16 또는 x64 SSE2의 _mm_cmpeq_epi16로 16개 원소를 두 묶음으로 병렬 비교
  • 나머지 원소 구간은 v >= pos가 되는 지점에서 v == pos 여부를 반환

결론

  • 교과서적 이진 검색은 괜찮은 알고리듬이지만, 실제 성능에 의미 있는 방식으로 더 빠르게 만들 수 있음
  • 표준 알고리듬은 오늘날 컴퓨터의 높은 병렬성을 전제로 설계되지 않은 경우가 많음
  • SIMD Quad는 메모리 수준 병렬성과 데이터 병렬성을 모두 활용하려는 접근
  • 더 나은 알고리듬도 가능할 수 있으며, 더 창의적인 접근이 필요
  • 소스 코드
  • Faster intersections between sorted arrays with shotgun
GeekNews Weekly에 포함된 글입니다. 에디터 코멘트 보기

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Daniel Lemire가 말한 저수준 하드웨어 최적화와는 별개로, 이진 탐색이나 그 구현 변형이 최선인 경우는 데이터가 정렬/단조라는 사실 외에 아무것도 모를 때뿐임
    데이터 분포에 대한 사전 정보가 있으면 그 정보를 써서 훨씬 더 빠른 알고리즘을 만들 수 있음. 종이 사전에서 사람이 순수한 이진 탐색보다 더 빨리 적당한 페이지 묶음으로 이동하는 것이 예시임
    수학적으로 정렬 리스트 검색은 닫힌 루프 제어 알고리즘으로 단조 함수의 역함수를 찾는 일에 가깝고, 비용 함수를 만들어 경사 하강법이나 가속 변형을 쓸 수도 있음. 더 일반적으로는 지나치게 추상화된 표현의 해법을 가져오기보다, 풀려는 특정 문제에 대한 정보를 더 쓰는 편이 항상 더 효율적이며, 하드웨어를 더 잘 써서 얻는 상수배 개선보다 훨씬 큰 확장 가능한 속도 향상을 줄 수 있음

    • 이진 탐색에 꽤 머리를 써봤지만, 이 구현보다 나은 걸 못 찾았음: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
      1. 조밀한 리스트인지 O(1)로 확인
      2. 상한 확인
      3. 반복 횟수가 고정된 이진 탐색
        고정 반복 횟수는 분기 예측기에 좋고, 핵심 루프도 대상 하드웨어에 맞게 곱셈을 피하며 꽤 빡빡하게 최적화돼 있음. 더 영리하게 만들려는 시도는 루프를 악화시켰고 이득을 못 냈음. 구조체 배열 형식에 크기가 12이고, 대체로 N이 작아서 어렵기도 함
    • 트립(treap)에 관한 글을 읽은 기억이 있는데, 트리 균형을 맞추는 대신 가중치를 써서 허프만 인코딩처럼 탐색 깊이를 조정하고, 접근 빈도가 다른 경우 평균 접근 시간을 줄이는 방식이었음
      북마크를 안 해둬서 1년에 두 번쯤 다시 찾고 있음. 전설에 따르면 아직도 찾는 중임
    • 맞지만, 핵심은 데이터를 더 알 수 없는 경우가 많다는 것임
      그래서 데이터베이스에서는 B-트리가 표준임. 데이터는 무엇이든 될 수 있고, 새 행을 대량으로 가져오면 특성이 언제든 크게 바뀔 수 있음
      경사 하강법 같은 방식으로 조회를 가속하는 알고리즘을 만들 수는 있지만, B-트리는 이미 매우 빠르고 최악 성능과 I/O 요구량 예측 가능성, 범위 스캔, 정렬 순회, 접두 조건 지원 같은 장점도 많음
      특정 데이터 분포에 더 효율적인 조회 알고리즘은 만들 수 있지만, 중요한 속성을 잃는 경우가 많음. 다른 알고리즘이 더 가까운 초기 추정을 내더라도 마지막 항목을 찾는 데 느릴 수 있고, 평균은 빨라도 최악 성능이 너무 나빠서 못 쓸 수도 있음
      종이 사전에서도 첫 추정 이후에는 거의 이진 탐색을 썼고, 그 초기 추정으로 줄어드는 단계는 몇 번뿐임. 적당한 페이지 묶음에 도달한 뒤에는 필요한 것보다 선형적으로 훑는 편인데, 엄격한 이진 탐색을 하면 더 빠를 수도 있지만 페이지 넘기는 시간과도 균형을 맞춰야 함
    • “풀려는 특정 문제에 대한 정보를 더 쓰는 것이 더 효율적”이라는 말은 뻔하면서도 깊음. 이미 가진 정보가 많을수록, 이미 가진 정보가 많은 셈임
    • Fritz Henglein이 빠른 정렬/그룹화에 대해 흥미로운 작업을 했음. 핵심 논문은 Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]로 보임
      Ed Kmett은 그 아이디어를 Haskell용 discrimination[2] 라이브러리로 다듬었고, 관련 기술 발표[3]도 매우 흥미로움
      [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
      [2]: https://hackage.haskell.org/package/discrimination
      [3]: https://www.youtube.com/watch?v=cB8DapKQz-I

  • “4분 탐색”은 결국 이진 탐색 루프를 한 단계 펼친 것 아닌가? 항목이 있는 구간을 찾으려면 비교 횟수는 대략 비슷하고, 한 번에 2개가 아니라 4개씩 처리하는 것처럼 보임. 루프 펼치기로도 같은 효과가 날 것 같음

    • 그보다 더 까다로움. 현대 프로세서는 추측 실행을 해서 비교 결과를 예측하고, 틀렸다는 걸 알거나 내부 한계에 닿을 때까지 한쪽 분기를 계속 진행함. 틀리면 추측 작업을 버리고 몇 사이클 페널티를 낸 뒤 다른 시작점에서 다시 함
      사실상 프로세서 관점에서는 모든 루프가 이미 어느 정도 펼쳐져 있고, 루프 자체의 작은 오버헤드만 남음. 이진 탐색에서 주된 비용은 메모리나 캐시에서 데이터를 가져오는 것이므로, 실제 싸움은 나중에 필요할 데이터를 최대한 일찍 요청하게 만들어 도착을 덜 기다리는 것임
      4분 탐색 같은 알고리즘의 차이는 각 분기의 한쪽만 깊게 미리 가져오는 대신, 가능한 모든 경우를 얕게 프리페치한다는 데 있음. 결국 필요할 프리페치는 반드시 발행되고, 실제 실행 경로에서 쓰지 않을 데이터에 대역폭을 조금 덜 쓰게 됨
      검색 알고리즘의 실제 성능을 예측하려면 “비교 횟수”는 거의 쓸모없는 지표임. 병목은 비교를 얼마나 많이 할 수 있느냐가 아니라 메모리와 캐시 대역폭을 최대한 활용하느냐에 달려 있음. 현대 프로세서의 분기 동작을 내부까지 고려한다면 루프 펼치기로 볼 수도 있음
    • 이건 루프를 조금 펼친 것으로 볼 수 있음. 성능이 좋아지는 이유는 명령 수나 메모리 읽기를 크게 줄여서가 아니라, 연산 간 의존성을 완화해 순수 직렬 실행을 피하기 때문임. 분기의 양쪽을 추측 실행하는 것과 비슷하게 볼 수도 있음
    • 4분 탐색은 사실상 현재 반복의 비교와 동시에 다음 반복에서 가능할 두 비교를 함께 수행함. 단순한 루프 펼치기보다는 조금 더 복잡함
      어쨌든 두 탐색 모두 상수가 다른 O(log N)임. 알고리즘 수업에서는 상수가 별로 중요하지 않지만 현실에서는 꽤 크게 작용할 수 있음
    • 어느 정도 맞지만, 펼쳐진 단계 사이의 데이터 의존성도 제거하고 있음
    • 프로세서는 우리가 순진하게 생각하는 방식으로 동작하지 않기 때문임

  • 최근에 지수 탐색[2]에 대해서도 글[1]을 썼음. 찾는 원소들 자체가 정렬된 상태로 배열에서 반복적으로 이진 탐색해야 할 때 쓸 수 있는 알고리즘이고, 우리 작업 부하에서는 8배 속도 향상이 나왔음
    [1] https://lalitm.com/post/exponential-search/
    [2] https://en.wikipedia.org/wiki/Exponential_search

    • 지수 탐색은 순차 ID로 리소스를 주소 지정하는 REST API에서 마지막 ID가 필요하지만 전용 엔드포인트가 없을 때 유용함
      HEAD /users/1 -> 200 OK
      HEAD /users/2 -> 200 OK
      HEAD /users/4 -> 200 OK
      ...
      HEAD /users/2048 -> 200 OK
      HEAD /users/4096 -> 404 Not Found
      그런 다음 2048과 4096 사이를 이진 탐색하면 가장 최근 사용자와 부수적으로 사용자 수를 찾을 수 있음. 경쟁 SaaS 회사를 조사할 때 알면 좋은 정보임

  • CPU는 항상 캐시 라인 전체, 보통 64바이트를 한 번에 접근하니 캐시 라인 전체를 검색하는 편이 낫겠음. 데이터가 CPU 안에 올라온 뒤에는 사실상 공짜에 가까움
    그래서 “이진” 탐색에서 가운데 캐시 라인의 모든 값을 검사하고, 일치하는 값이 없으면 왼쪽/오른쪽으로 가는 방식을 시도해보고 싶음. 캐시 라인 검색은 512비트 SIMD 명령 하나로 가능함. 캐시 라인 64바이트는 16비트 정수 32개이므로, 단순 이진 탐색보다 거의 32배 빠를 수도 있고, 적어도 메모리 접근은 32배 줄어들어 현실적인 프로그램 대부분에서 지배적일 것임

    • 이진 탐색 트리, 즉 정렬 벡터의 위쪽 캐시 라인에서 목표값을 찾을 가능성은 낮음. 대신 라인 안의 추가 데이터를 이용해 탐색 범위를 줄이는 편이 좋고, 그러면 B-트리나 B+트리로 이어짐
      4바이트 키와 4바이트 자식 포인터, 또는 배열 인덱스를 쓰면 내부 노드는 키 7개, 자식 포인터 8개, 다음 포인터 1개로 64바이트 캐시 라인을 꽉 채울 수 있음. 100만 항목에서 트리 깊이는 약 20에서 약 7로 줄고, 위쪽 몇 단계는 캐시에 남아 있을 가능성이 큼
      조금 고민하면 SIMD로 B-트리 노드 내부 검색을 빠르게 할 수 있지만, 데이터 의존성이 매우 큼

  • 더 작은 배열이라면 끝에 센티널 값을 둔 선형 탐색은 이미 이기기 어려움. 다만 이 주장이 애매한 이유는 “작다”가 너무 흐릿한 조건이라 체감하기 어렵다는 데 있음

    • 그건 사실이 아님. 이 글의 훌륭한 벤치마크를 보면 선형 탐색은 대략 200~400개 원소 부근에서 뒤처짐
      전반적으로 이 글은 마음에 듦. 평소 궁금했던 점을 유용한 제거 실험까지 곁들여 완벽하게 탐구했음
    • 이 글이 다루는 내용은 그게 아님

  • 작은 배열, 16~32개 항목에서 검색 실험을 조금 해봤는데 이진 탐색은 분기가 많아서 최악의 방법 중 하나였음. 작은 배열에서 가장 빠른 방법은 분기 없는 선형 탐색이었음
    루프를 중간에 끊지 않고 모든 원소를 훑는 방식임. 예를 들어 배열에 어떤 수가 있는지 알고 싶다면 모든 항목의 검사 결과를 논리 OR로 합침. SIMD는 쓰지 않았지만, 작은 배열에서는 분기가 매우 비싸서 분기 없이 모든 원소를 그냥 검사하는 편이 더 빠름

    • 프리페처가 좋아하는 접근 패턴이라 더 빠른 건지 궁금함

  • 알고리즘 설명이 조금 헷갈렸음
    SIMD 부분은 마지막 단계, 즉 마지막 16개 원소를 검색할 때만 쓰임
    4분 탐색 부분은 3개 지점을 검사해서 4개 경로를 만드는 것이지만, 단순히 올바른 키가 아니라 올바른 블록을 찾고 있음
    세부가 흥미로운데, 작성자는 각 블록의 마지막 원소를 4분 탐색에 사용함. 첫 원소를 쓰거나 임의의 원소를 쓰면 알고리즘이 어떻게 바뀔지 궁금함

  • 여기의 핵심 직관인 SIMD 다중 비교는 마지막 단계보다 더 큰 규모에도 쓸 수 있어 보임
    개요는 이렇다: a) gather로 균등 간격 16곳에서 여러 원소를 가져옴 b) SIMD 명령으로 병렬 비교 c) 올바른 블록에 집중 d) 블록이 작으면 선형 탐색으로 전환하고, 아니면 gather/비교 주기를 반복함
    gather 명령은 비연속 메모리에서 읽고, 이진 탐색이라면 필요하지 않을 만큼 더 많이 읽긴 함. 그래도 다방향 비교가 가능해지고 이진 탐색 4단계를 접을 수 있다면 큰 테이블에서는 이길 수 있을 듯함
    모든 자료형에서 완전한 16방향 비교가 가능한 것도 아님. float64 검색은 AVX-512에서도 8방향 비교로 제한되지만, int32와 float32는 16방향 비교가 가능함

    • gather는 극도로 느림. 효율을 노리는 사람이라면 gather를 피할 것임
      gather 기반 방식보다 이진 탐색이 실제로 더 빠를 가능성이 높다고 봄

  • 고전적인 컴퓨터 과학 알고리즘은 사실상 병렬성이 없는 CPU를 대상으로 “설계”된 셈임. 여러 코어, Hyper-threading, SIMD 명령 같은 병렬성이 없고, 모든 메모리 접근 시간이 같아서 L1/L2/L3 캐시 지연 같은 개념도 없으며, 일반적/무작위 데이터를 다룬다는 가정임
    이 가정 중 하나라도 벗어나면 성능을 높일 수 있는 조정이 많이 생김
    고전 알고리즘은 특정 데이터 형태나 특정 CPU의 특성/기능을 더 알게 된 뒤 더 최적화된 해법을 개발하기 위한 매우 좋은 출발점을 제공함
    최적화의 뾰족한 끝까지 가면 보통 데이터가 메모리에 어떻게 저장되고 접근되는지, 그리고 이를 개선하는 변경이 이후 단계에 해를 끼치지 않는지를 보게 됨. 오래전 직장에서 누군가 코드의 특정 부분을 너무 오래 최적화했는데, 그 최적화 때문에 나중에 필요한 많은 정보가 캐시에서 밀려나 전체 애플리케이션은 더 느려진 일이 있었음
    이는 아마 Rob Pike의 프로그래밍 5번째 규칙, 다시 말해 _The Mythical Man Month_에서 Fred Brooks가 한 말을 재진술한 것에 가까움. 참고: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...

  • 십대 때 주말 내내, 이진 탐색이 매 단계 탐색 공간을 절반으로 줄여서 좋다면 삼진 탐색은 3분의 1씩 줄이니 더 낫지 않을까 생각했음
    가운데 값 하나만 비교하는 대신 1/3 지점 값을 비교하고, 너무 낮으면 2/3 지점 값을 비교하는 방식임
    하지만 각 단계에서 이진 탐색의 1/2 대신 1/3로 줄이는 반면, 비교는 평균 3/2배 한다고 생각해서 결국 같다고 봤음
    수정: zamadatix 답변을 보니 실제로는 2/3의 경우 비교를 2번 해야 하므로 평균 5/3배임

    • 이 삼진 접근은 실제로 단계당 평균 비교 횟수가 3/2가 아님
      첫 1/3: 비교 1번
      둘째 1/3: 비교 2번
      셋째 1/3: 비교 2번
      (1+2+2)/3 = 평균 5/3번 비교임. “비교를 1번 하거나 2번 한다”는 느낌 때문에 50%로 착각하기 쉽지만, 실제로는 첫 비교에서 걸릴 확률이 1/3이고, 2번 비교할 확률이 2/3임
      그래서 총 평균 비교 횟수에서 삼진 탐색이 아주 조금 더 나쁨을 보일 수 있음: 5/3*Log_3[n] = 1.052... * Log_2[n]
      즉 단계 수는 줄지만 끝까지 가기 위해 평균적으로 더 많은 비교를 하게 됨. 이건 이런 유형의 모든 탐색, 즉 분할 수가 2보다 큰 경우에 대체로 성립함. 물론 찾는 값이 균등 분포하고 연산 비용이 이상화돼 있다는 몇 가지 가정이 있고, 바로 이 지점에서 본문 글의 논의가 들어옴
    • 알고 보니 십대 시절의 그 생각에도 뭔가가 있었음
      이진 탐색 알고리즘의 삼진 버전으로서는 아님. 그건 실제 삼진 탐색이 아니라 치우친 이진 탐색에 가깝기 때문임. 비교는 본질적으로 이진이므로, 비교를 포함하는 탐색 알고리즘은 모두 일종의 이진 탐색이고, 가운데 원소가 아닌 선택은 알고리즘 복잡도 측면에서 덜 효율적임. 다만 실제 하드웨어에서는 어떤 조건에서 더 나을 수도 있음. 진짜 삼진 탐색을 하려면 기본 연산으로 3방향 비교가 필요함
      흥미로워지는 지점은 “기수 효율”[1]을 고려할 때임. 최선의 선택은 e에 가장 가까운 자연수인 3임. 트리 탐색과도 관련이 있어서, 삼진 트리가 이진 트리보다 나을 수 있음
      [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
    • 빠른 탐색이 불가능한 디스크 같은 곳에서는 예를 들어 128방향 B-트리를 쓸 수 있음. 키 128개를 가져오는 비용은 1개를 가져오는 것보다 크게 비싸지 않지만, 추가로 7번의 가져오기를 줄여줌
    • 그 다음에는 삼진 비교기를 포함한 CPU를 상상했나?
    • 십대 시절 이후 CPU는 실행 폭과 벡터 기능 양쪽에서 극적으로 넓어졌음. 처리량이 늘면서, 의존성 사슬을 줄이기 위해 연산을 더 태우는 쪽으로 균형이 이동함
      그래서 그 아이디어가 당시 CPU에서는 실현성이 없었지만 지금 CPU에서는 더 가능성이 높아졌을 수 있음
답변달기