C++ 벡터 검색 엔진, 데이터 레이아웃 변경으로 16배 성능 향상!
C++ 기반 벡터 검색 엔진의 성능 개선을 위해 데이터 레이아웃(Data Layout)을 변경하여 획기적인 성능 향상을 달성
기존 객체 기반 구조에서 플랫 배열(Flat Array)로 변경하여 캐시 미스(Cache Miss)를 줄이고 SIMD(Single Instruction, Multiple Data) 연산을 활용
제곱 거리(Squared Distance) 사용 및 정렬 시 거리 재계산 방지를 통해 불필요한 연산 제거
알고리즘 변경 없이 쿼리 지연 시간(Query Latency)을 최대 16.5배 단축, 빌드 시간(Build Time) 단축 및 리콜(Recall) 유지
데이터 레이아웃 변경을 통한 성능 개선
저자는 기존의 객체 기반 데이터 레이아웃(Object-heavy Data Layout)에서 플랫 배열(Flat Array) 기반으로 변경하여 성능을 개선했다. 기존에는 각 레코드가 벡터 객체에 대한 포인터를 가지고 있어, 쿼리 처리 시 포인터 추적(Pointer Chasing) 및 가상 함수 호출(Virtual Method Call)로 인해 성능 저하가 발생했다. 특히, 캐시 미스(Cache Miss)가 빈번하게 발생하여 CPU의 효율성을 떨어뜨렸다. 변경 후, 연속된 메모리 공간에 벡터 데이터를 저장하여 SIMD(Single Instruction, Multiple Data) 연산을 가능하게 했다.
제곱 거리(Squared Distance) 사용 및 불필요한 연산 제거
성능 개선을 위해 제곱 거리(Squared Distance)를 사용하고, 정렬 과정에서 거리 재계산을 방지했다. 기존에는 유클리드 거리(Euclidean Distance) 계산을 위해 제곱근 연산(Square Root)을 수행했으나, 검색 결과의 순서만 중요하다면 제곱근 연산은 불필요하다. 또한, 정렬 시 거리 계산을 캐싱하여 중복 계산을 피했다. 이러한 최적화는 CPU 부하(CPU Load)를 줄여 쿼리 처리 속도를 향상시키는 데 기여했다.
어셈블리 코드(Assembly Code) 분석을 통한 성능 비교
저자는 성능 개선 전후의 어셈블리 코드를 비교 분석하여 최적화 효과를 입증했다. 기존 코드에서는 가상 함수 호출(Virtual Function Call) 및 제곱근 연산(Square Root)으로 인해 복잡한 경로가 생성되었으나, 최적화된 코드에서는 SIMD(Single Instruction, Multiple Data) 연산을 활용하여 간단하고 효율적인 코드를 생성했다. 특히, `movups`, `subps`, `mulps`와 같은 명령어를 통해 여러 개의 부동 소수점 연산을 동시에 처리하여 성능을 향상시켰다.
Vamana 알고리즘의 성능 향상 및 결과
본 연구는 그래프 기반 인덱스인 Vamana 알고리즘을 사용하여 벡터 검색 엔진의 성능을 개선했다. 알고리즘 자체의 변경 없이 데이터 레이아웃 및 연산 최적화를 통해 쿼리 지연 시간(Query Latency)을 최대 16.5배 단축하고, 빌드 시간(Build Time)을 단축했다. 또한, 리콜(Recall)을 1.0으로 유지하여 검색 품질 저하 없이 성능을 향상시켰다. 이는 데이터 레이아웃이 알고리즘의 성능에 미치는 영향이 크다는 것을 보여준다.
