Cây tìm kiếm tĩnh: Nhanh hơn 40 lần so với tìm kiếm nhị phân

Tìm kiếm nhị phân trên mảng đã sắp xếp là một phương pháp kinh điển, nhưng nó không tối ưu trên phần cứng hiện đại. Một bài viết mới từ Curious Coding hướng dẫn xây dựng cây tìm kiếm tĩnh (cây S+) đạt thông lượng cao hơn tới 40 lần so với tìm kiếm nhị phân tiêu chuẩn. Công trình này dựa trên khái niệm cây S từ Algorithmica và đẩy nó đến giới hạn với các tối ưu vi mô mạnh mẽ.

Vấn đề và đường cơ sở

Đầu vào là một danh sách đã sắp xếp các số nguyên không dấu 32-bit. Mục tiêu là trả lời nhiều truy vấn độc lập, trả về phần tử nhỏ nhất lớn hơn hoặc bằng truy vấn. Thước đo là thông lượng — số truy vấn mỗi giây — và đường cơ sở là tìm kiếm nhị phân từ thư viện chuẩn của Rust.

Các tối ưu chính

Bài viết cải thiện cây S+ một cách có hệ thống qua nhiều lớp:

Bố trí Eytzinger: Sắp xếp lại cây tìm kiếm nhị phân trong bộ nhớ sao cho các nút được truy cập trong các bước liên tiếp nằm gần nhau, cải thiện hành vi bộ nhớ đệm. Prefetching sau đó có thể che giấu độ trễ bộ nhớ.
Xử lý theo lô: Thay vì xử lý từng truy vấn một, việc triển khai xử lý nhiều truy vấn song song, giảm chi phí chung và cho phép sử dụng SIMD tốt hơn.
Vector hóa SIMD: Sử dụng lệnh AVX2 để so sánh nhiều khóa cùng lúc, giảm số lượng nhánh và truy cập bộ nhớ mỗi truy vấn.
Điều chỉnh kích thước nút: Thử nghiệm với các kích thước nút (B=15, B=16, v.v.) để căn chỉnh với dòng bộ nhớ đệm và độ rộng thanh ghi SIMD.
Chiến lược prefetching: Prefetch các dòng bộ nhớ đệm trước vài bước, che giấu độ trệ DRAM.
Số học con trỏ: Loại bỏ gián tiếp không cần thiết bằng cách sử dụng con trỏ dựa trên byte và splatting giá trị truy vấn ngay từ đầu.

Kết quả

Triển khai cuối cùng đạt thông lượng cao hơn khoảng 40 lần so với tìm kiếm nhị phân tiêu chuẩn trên dữ liệu ngẫu nhiên. Tác giả cũng khám phá phân vùng tiền tố cho các phân phối truy vấn không đồng đều và mở rộng đa luồng.

Tại sao điều này quan trọng

Đây không chỉ là một benchmark thử nghiệm. Động lực đến từ tin sinh học — cụ thể là tìm kiếm mảng hậu tố để lập chỉ mục DNA. Bộ gen người có 3 tỷ cặp base, và việc tìm kiếm hiệu quả là rất quan trọng. Các kỹ thuật ở đây áp dụng trực tiếp cho bất kỳ tìm kiếm thông lượng cao nào trên dữ liệu tĩnh đã sắp xếp, từ chỉ mục cơ sở dữ liệu đến pipeline phân tích bộ gen.

Bài viết rất cụ thể: mọi tối ưu đều được hỗ trợ bởi phân tích assembly và số liệu benchmark. Đây là một lớp học mẫu mực về cách suy nghĩ về phân cấp bộ nhớ, SIMD và dự đoán nhánh.