- 정렬된 배열에서 값을 찾을 때 흔히 쓰는 이진 검색은 한 번에 하나의 값만 비교하지만, 최신 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