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

• 정렬 배열의 멤버십 검사는 교과서적 이진 검색보다 더 빠르게 만들 수 있으며, SIMD Quad는 모든 측정 조건에서 std::binary_search보다 빨랐음
• SIMD Quad는 16비트 부호 없는 정수 정렬 배열을 16개 원소 블록으로 나누고, 블록 경계에서는 4진 보간 검색을, 블록 내부에서는 SIMD 병렬 비교를 수행함
• 최신 64비트 ARM과 x64(Intel/AMD)는 한 명령으로 16비트 정수 8개를 비교할 수 있어, 한 번에 값 하나만 검사하는 이진 검색 구조를 그대로 따를 필요가 줄어듦
• 벤치마크는 크기 2~4096의 정렬 배열 100,000개와 멤버십 질의 1,000만 번으로 수행됐으며, cold 모드는 캐시 미스, warm 모드는 캐시 히트를 시뮬레이션함
• Intel에서는 warm 캐시에서 SIMD Quad가 이진 검색보다 2배 이상 빨랐고, Apple에서는 cold 캐시에서 2배 이상 빨랐으며, Intel 큰 배열 cold 캐시에서는 4진 접근이 메모리 수준 병렬성을 더 잘 활용함

정렬 배열 멤버십 검사의 병목

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

SIMD Quad의 출발점

• 최신 프로세서는 대부분 데이터 병렬 명령어인 SIMD를 갖고 있으며, 64비트 ARM과 x64(Intel/AMD)는 한 명령으로 16비트 정수 8개를 대상 값과 비교할 수 있음
• 이 특성 때문에 이진 검색을 8개보다 작은 블록까지 계속 내려갈 필요가 없고, 16개 이상의 원소도 저렴하게 비교할 수 있음
• 이진 검색은 한 번에 값 하나를 검사하지만, 최근 프로세서는 한 번에 여러 값을 로드하고 검사할 수 있으며 메모리 수준 병렬성도 좋음
• 배열을 반으로 나누는 대신 4분할하는 4진 검색을 시도할 수 있으며, 명령어 수는 약간 늘어도 병목이 명령어 수가 아닐 가능성이 큼

SIMD Quad 알고리듬 구조

• SIMD Quad는 16비트 부호 없는 정수의 정렬 배열을 위한 검색 알고리듬으로, 4진 보간 검색과 SIMD를 결합함
• 배열을 16개 원소의 고정 크기 블록으로 나누고, 마지막 블록은 예외가 될 수 있음
• 각 블록의 마지막 원소를 보간 키로 사용해 대상 값이 있을 가능성이 높은 단일 블록으로 범위를 좁힌 뒤, 그 블록의 16개 원소를 SIMD로 동시에 검사함
• 핵심 흐름은 블록 경계에서 보간 검색으로 비교 횟수를 줄이고, 블록 내부에서 SIMD로 병렬 비교를 수행하는 계층형 검색임
• 동작 단계는 다음과 같음
  • 원소 수가 16개보다 적으면 전체를 단순 선형 검색함
  • cardinality 크기 배열을 16개 연속 원소 블록으로 나누고, 전체 블록 수는 num_blocks = cardinality / 16임
  • 위치 16-1, 32-1 등의 블록 마지막 원소를 키로 사용해 현재 검색 범위의 1/4 지점들을 대상 pos와 비교하고 base를 조정함
  • 보간 결과에 따라 적절한 블록 인덱스 lo를 선택함
  • 유효한 블록이면 ARM에서는 NEON, x64에서는 SSE2로 16개 원소를 로드해 대상 값과 병렬 동등 비교를 수행하고, 일치가 있으면 true를 반환함
  • 전체 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 캐시에서는 더 많은 데이터 접근으로 캐시 실패가 늘어나기 때문에 선형 검색이 상대적으로 더 불리함
• 이진 검색이 선형 검색보다 전반적으로 우세한 뒤, SIMD Quad와 비교됨
• Intel과 Apple 플랫폼의 결과는 뚜렷하게 달랐음
  • Intel 플랫폼에서는 warm 캐시에서 SIMD Quad가 이진 검색보다 2배 이상 빠름
  • Intel 플랫폼의 cold 캐시에서는 이득이 더 작음
  • Apple 플랫폼에서는 반대로 cold 캐시에서 SIMD Quad가 2배 이상 빠르고, warm 캐시에서는 이득이 더 제한적임
• 모든 경우에서 SIMD Quad는 이진 검색보다 빨랐음
• 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 지점의 블록 마지막 값을 읽어 pos보다 작은지 비교하고, 세 비교 결과의 합으로 base를 이동함
• 이후 n > 1 동안 절반 기준 비교를 수행해 남은 범위를 줄이고, 마지막으로 lo 블록을 선택함
• 선택된 블록은 ARM NEON의 vceqq_u16 또는 x64 SSE2의 _mm_cmpeq_epi16로 16개 원소를 두 묶음으로 비교함
• 나머지 원소 구간은 v >= pos가 되는 지점에서 v == pos 여부를 반환하고, 끝까지 없으면 false를 반환함

결론과 자료

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