Static Search Trees: nhanh hơn tìm kiếm nhị phân 40 lần
(curiouscoding.nl)- Triển khai một cây tìm kiếm tĩnh gọi là “S+ tree” để thực hiện tra cứu tốc độ cao trên dữ liệu đã sắp xếp
- Lấy mã được đề xuất trong bài viết trên Algorithmica làm điểm khởi đầu, sau đó tối ưu hóa và hiện thực hóa các ý tưởng bổ sung cũng như các cải tiến được đề xuất
- Sau khi phân tích mã assembly, tối ưu hóa mọi lệnh có thể để đẩy hiệu năng lên mức tối đa
- Giới thiệu batching để xử lý song song nhiều truy vấn nhằm cải thiện throughput
- Mục tiêu là dùng S+ tree để thực hiện truy vấn hiệu quả trên dữ liệu đã sắp xếp trong khi vẫn duy trì throughput cao
1. Giới thiệu và động lực
-
Định nghĩa bài toán:
- Đầu vào: danh sách số nguyên không dấu 32-bit đã sắp xếp
vals: Vec<u32> - Đầu ra: một cấu trúc dữ liệu có kích thước tối thiểu, trả về giá trị đầu tiên lớn hơn hoặc bằng truy vấn (q)
- Chỉ số đánh giá: số lượng truy vấn độc lập có thể xử lý mỗi giây
- Đầu vào: danh sách số nguyên không dấu 32-bit đã sắp xếp
-
Mục tiêu:
- Xây dựng cấu trúc dữ liệu hiệu quả trong tin sinh học, đặc biệt để tăng tốc tìm kiếm trên suffix array dùng cho lập chỉ mục chuỗi DNA
- Hướng tới tối đa hóa hiệu năng bằng cách tận dụng hiệu năng CPU và các lệnh SIMD
-
Tài liệu khuyến nghị:
- Nghiên cứu về tìm kiếm nhị phân và bố cục mảng (“Array Layouts for Comparison-Based Searching”)
- Tài liệu giới thiệu về S+ tree và static B-tree
2. S+ tree và tối ưu hóa
2.1 Tìm kiếm nhị phân và bố cục Eytzinger
- Tìm kiếm nhị phân trong thư viện chuẩn Rust có hiệu quả cache thấp, và hiệu năng suy giảm khi kích thước dữ liệu tăng
- Bố cục Eytzinger:
- Lưu cây tìm kiếm nhị phân dưới dạng mảng để tận dụng cache tối đa
- Hiệu năng: nhanh hơn tìm kiếm nhị phân tới 4 lần với dữ liệu vượt quá cache L3
2.2 Khái niệm S+ tree
- S-tree:
- Dạng cây 16 phân, mỗi nút chứa 15 giá trị đã sắp xếp
- Hiệu quả hơn B-tree và có thể nén tốt hơn bố cục Eytzinger
- S+ tree:
- Lưu toàn bộ dữ liệu ở các nút lá, đồng thời lưu bản sao ở các nút phía trên
- Cung cấp cấu trúc đơn giản và tìm kiếm hiệu quả
2.3 Tối ưu hóa hàm find
- Tìm kiếm tuyến tính cơ bản:
- Duyệt dữ liệu và trả về giá trị thỏa điều kiện (không hiệu quả)
- Tự động vector hóa:
- Chuyển thành mã không rẽ nhánh, tận dụng lệnh SIMD để tăng hiệu năng gấp 2 lần
- Hiện thực SIMD thủ công:
- Tối ưu thủ công bằng các lệnh SIMD, đạt hiệu năng tối đa chỉ với 5 lệnh
3. Batching và prefetching
3.1 Batching
- Xử lý song song nhiều truy vấn để bù trừ độ trễ chờ bộ nhớ
- Tăng kích thước batch giúp cải thiện throughput, và bão hòa ở kích thước batch tối đa là 16
3.2 Prefetching
- Nạp trước nút kế tiếp vào bộ nhớ để cải thiện hiệu năng với dữ liệu vượt quá cache L3
- Kết hợp với batching giúp giảm thời gian xử lý từ 45ns/query xuống 30ns/query
4. Tối ưu hóa bố cục và cấu trúc dữ liệu
4.1 Thay đổi kích thước nút
- Giảm số lượng giá trị mỗi nút xuống 15 để đơn giản hóa phép nhân và tăng hiệu quả cache
- Cải thiện hiệu năng nhẹ với dữ liệu nằm trong cache L3
4.2 Thay đổi bố cục bộ nhớ
- Thử nghiệm lưu bố cục theo thứ tự ngược hoặc cấu hình giảm tối thiểu phần đệm
- Cả bố cục ngược và bố cục giảm padding đều không ảnh hưởng đáng kể đến hiệu năng
5. Phân vùng dữ liệu
5.1 Phân vùng dựa trên tiền tố
- Tách các phần dữ liệu dựa trên các bit cao của dữ liệu
- Cải thiện hiệu năng với dữ liệu nhỏ, nhưng phát sinh overhead bộ nhớ
5.2 Cây con nén
- Đóng gói từng cây con để tăng hiệu quả không gian
- Cần theo dõi kích thước của từng phần, và tốc độ truy vấn giảm nhẹ
6. So sánh đa luồng
- Khi dùng 6 luồng, thời gian truy vấn giảm từ 27ns xuống 7ns
- Giới hạn băng thông RAM trở thành nút thắt cổ chai
7. Kết luận và nghiên cứu tiếp theo
- Cải thiện hiệu năng hơn 40 lần so với tìm kiếm nhị phân (1150ns/query → 27ns/query)
- Các hướng tiếp theo:
- Tối ưu cân bằng dữ liệu và giảm truy cập RAM
- Xử lý truy vấn phạm vi và truy vấn sắp xếp
- Tích hợp tìm kiếm trên suffix array
2 bình luận
Ồ... nếu được áp dụng vào các thư viện tích hợp sẵn của nhiều ngôn ngữ khác nhau thì có lẽ tác động lan tỏa sẽ rất đáng kể.
Ý kiến trên Hacker News
Quan sát thấy Rust ngày càng được օգտագործ nhiều hơn trong các nội dung cấp thấp liên quan đến thuật toán. Trước đây, nội dung chủ yếu được viết bằng C(++) hoặc mã giả mang tính học thuật. Xem đây là một tín hiệu tích cực
Cách chia truy vấn thành các lô chưa được khám phá. Chi phí chính là tra cứu trong bảng nằm ngoài cache
Số lượng giá trị int32 không quá nhiều, và toàn bộ bitset là 512MB. Với cấu trúc dữ liệu thông thường, đề xuất dùng Roaring Bitmaps
Cảm thấy ấn tượng về cách tăng hiệu quả cấp thấp trong Rust. Muốn so sánh với bản triển khai C++
Ưu điểm của cây Eytzinger là có công thức chuyển chỉ số nút sang vị trí duyệt trung tự
Ngạc nhiên khi việc tìm kiếm u32 trong 4GB bộ nhớ lại phát sinh overhead khoảng ~27ns
Có nhiều thảo luận về Rust và C++, nhưng lại đang nghĩ cách triển khai trong Common Lisp mà vẫn giữ được SIMD
Mỗi lần đọc các bài viết về tối ưu hóa cấp thấp, đều thấy biết ơn tác giả vì đã bỏ thời gian để tiết kiệm vài nano giây
Nghĩ rằng hình 3 ở mục 1.7 có lỗi. Đề xuất nhãn trục y của hình 1 ở mục 1.3 nên là "lượng truyền ngược"
Nếu thỉnh thoảng cần hỗ trợ ghi, có thể dùng một cây tìm kiếm tĩnh lớn và một cây nhỏ có thể ghi được