- Kiểm tra phần tử có thuộc một mảng đã sắp xếp có thể được thực hiện nhanh hơn tìm kiếm nhị phân kiểu giáo khoa, và SIMD Quad nhanh hơn
std::binary_search trong mọi điều kiện đo
- SIMD Quad chia mảng đã sắp xếp gồm các số nguyên không dấu 16 bit thành các khối 16 phần tử, thực hiện tìm kiếm nội suy tứ phân ở ranh giới khối và so sánh song song bằng SIMD bên trong khối
- ARM 64 bit hiện đại và x64 (Intel/AMD) có thể so sánh 8 số nguyên 16 bit chỉ với một lệnh, nên không còn quá cần thiết phải giữ nguyên cấu trúc tìm kiếm nhị phân vốn chỉ kiểm tra từng giá trị một
- Benchmark được chạy với 100.000 mảng đã sắp xếp có kích thước từ 2 đến 4096 và 10 triệu truy vấn kiểm tra phần tử; chế độ cold mô phỏng cache miss, còn chế độ warm mô phỏng cache hit
- Trên Intel, ở cache warm SIMD Quad nhanh hơn tìm kiếm nhị phân hơn 2 lần; trên Apple, ở cache cold nó cũng nhanh hơn hơn 2 lần; còn với mảng lớn trên Intel trong cache cold, cách tiếp cận tứ phân tận dụng song song mức bộ nhớ tốt hơn
Điểm nghẽn của kiểm tra phần tử trong mảng đã sắp xếp
- Cách đơn giản nhất để kiểm tra một giá trị có tồn tại trong mảng đã sắp xếp hay không là tìm kiếm tuyến tính, tức duyệt từng giá trị một; trong C++ có thể đạt hiệu ứng tương tự bằng
std::find
- Với mảng lớn, tìm kiếm nhị phân nhanh hơn; nó lặp lại việc loại bỏ nửa trên hoặc nửa dưới dựa trên giá trị ở giữa khoảng tìm kiếm cho đến khi tìm thấy giá trị hoặc khoảng rỗng
std::binary_search trong C++ trả về giá trị boolean cho biết phần tử có tồn tại hay không- Định dạng Roaring Bitmap sử dụng các mảng số nguyên 16 bit có kích thước từ 1 đến 4096 và dùng tìm kiếm nhị phân để kiểm tra sự tồn tại của giá trị
Điểm khởi đầu của SIMD Quad
- Hầu hết bộ xử lý hiện đại đều có các lệnh song song dữ liệu SIMD, và ARM 64 bit cùng x64 (Intel/AMD) có thể so sánh 8 số nguyên 16 bit với giá trị đích chỉ trong một lệnh
- Vì đặc tính này, không cần tiếp tục hạ tìm kiếm nhị phân xuống các khối nhỏ hơn 8 phần tử, và việc so sánh từ 16 phần tử trở lên cũng có chi phí thấp
- Tìm kiếm nhị phân kiểm tra từng giá trị một lần, nhưng bộ xử lý hiện đại có thể nạp và kiểm tra nhiều giá trị cùng lúc, đồng thời có song song mức bộ nhớ tốt
- Thay vì chia mảng làm hai, có thể thử tìm kiếm tứ phân chia làm bốn; dù số lệnh có tăng nhẹ thì điểm nghẽn có thể cũng không nằm ở số lượng lệnh
Cấu trúc thuật toán SIMD Quad
- SIMD Quad là thuật toán tìm kiếm cho mảng đã sắp xếp gồm các số nguyên không dấu 16 bit, kết hợp tìm kiếm nội suy tứ phân và SIMD
- Mảng được chia thành các khối cố định gồm 16 phần tử, ngoại trừ khối cuối có thể là ngoại lệ
- Dùng phần tử cuối của mỗi khối làm khóa nội suy để thu hẹp phạm vi xuống một khối duy nhất có khả năng cao chứa giá trị đích, rồi kiểm tra đồng thời 16 phần tử của khối đó bằng SIMD
- Luồng xử lý cốt lõi là một tìm kiếm phân tầng: giảm số lần so sánh bằng tìm kiếm nội suy ở ranh giới khối, rồi thực hiện so sánh song song bằng SIMD bên trong khối
- Các bước hoạt động như sau
- Nếu số phần tử ít hơn 16 thì tìm kiếm tuyến tính toàn bộ
- Chia mảng kích thước
cardinality thành các khối gồm 16 phần tử liên tiếp, với tổng số khối là num_blocks = cardinality / 16
- Dùng các phần tử cuối khối ở vị trí
16-1, 32-1... làm khóa để so sánh các điểm 1/4 của phạm vi tìm kiếm hiện tại với giá trị đích pos, rồi điều chỉnh base
- Chọn chỉ số khối phù hợp
lo theo kết quả nội suy
- Nếu là khối hợp lệ thì trên ARM dùng NEON, còn trên x64 dùng SSE2 để nạp 16 phần tử và thực hiện so sánh bằng nhau song song với giá trị đích; nếu có khớp thì trả về
true
- Các phần tử còn lại không nằm trọn trong các khối 16 phần tử sẽ được tìm tuyến tính
Cách benchmark
- Benchmark tạo ra 100.000 mảng đã sắp xếp gồm các số nguyên không dấu 16 bit cho mỗi kích thước mảng từ 2 đến 4096
- Với mỗi kích thước, thực hiện 10 triệu truy vấn kiểm tra phần tử ở hai chế độ
- Chế độ cold: mỗi truy vấn tìm trên một mảng khác nhau để mô phỏng cache miss
- Chế độ warm: nhóm truy vấn theo mảng và tìm liên tiếp 100 lần trên cùng một mảng để mô phỏng cache hit
- Đại lượng đo là thời gian truy vấn trung bình; các thuật toán được so sánh là tìm kiếm tuyến tính (
std::find), tìm kiếm nhị phân (std::binary_search) và SIMD Quad
- Hệ thống đo gồm Apple M4 với Apple LLVM, và bộ xử lý Intel Emerald Rapids với GCC
Kết quả đo
- Khi so sánh tìm kiếm tuyến tính với tìm kiếm nhị phân, khi mảng lớn lên thì tìm kiếm nhị phân vượt qua tìm kiếm tuyến tính
- Trong cache cold, do có nhiều lần truy cập dữ liệu hơn nên số lần trượt cache tăng lên, khiến tìm kiếm tuyến tính tương đối bất lợi hơn
- Sau khi tìm kiếm nhị phân nhìn chung chiếm ưu thế so với tìm kiếm tuyến tính, bài viết tiếp tục so sánh nó với SIMD Quad
- Kết quả trên nền tảng Intel và Apple khác nhau khá rõ
- Trên nền tảng Intel, ở cache warm SIMD Quad nhanh hơn tìm kiếm nhị phân hơn 2 lần
- Trên nền tảng Intel, trong cache cold mức lợi ích nhỏ hơn
- Trên nền tảng Apple thì ngược lại: trong cache cold SIMD Quad nhanh hơn hơn 2 lần, còn trong cache warm lợi ích hạn chế hơn
- Trong mọi trường hợp, SIMD Quad đều nhanh hơn tìm kiếm nhị phân
- Phần SIMD giảm khối lượng công việc bằng các lệnh chuyên dụng, đồng thời ít lệnh và ít nhánh hơn nên mức tăng tốc khá dễ lý giải
Hiệu quả của tìm kiếm tứ phân
- Bài viết cũng so sánh một phiên bản SIMD binary giữ nguyên tối ưu SIMD nhưng thay tìm kiếm nội suy tứ phân bằng tìm kiếm nhị phân tiêu chuẩn
- Trên nền tảng Apple, hiệu quả của cách tiếp cận tứ phân là nhỏ
- Trên nền tảng Intel, trong tình huống cache cold với mảng lớn, cách tiếp cận tứ phân là một tối ưu có ý nghĩa
- Trên máy chủ Intel, tìm kiếm tứ phân tận dụng song song mức bộ nhớ tốt hơn
Các điểm chính trong triển khai
- Hàm
simd_quad nhận một mảng uint16_t, số phần tử cardinality, và giá trị cần tìm pos, rồi trả về boolean
gap được cố định ở 16; nếu cardinality < gap thì tìm giá trị bằng vòng lặp đơn giản- Vòng lặp tìm khối, khi
n > 3, sẽ đọc các giá trị cuối khối tại các điểm 1/4, 2/4, 3/4 và so sánh xem chúng có nhỏ hơn pos hay không, rồi dịch chuyển base theo tổng của ba kết quả so sánh
- Sau đó, khi
n > 1, nó thực hiện các phép so sánh theo mốc giữa để thu hẹp phạm vi còn lại, rồi cuối cùng chọn khối lo
- Khối được chọn sẽ được so sánh 16 phần tử theo hai nhóm bằng
vceqq_u16 trên ARM NEON hoặc _mm_cmpeq_epi16 trên x64 SSE2
- Với đoạn phần tử còn lại, thuật toán trả về kết quả của
v == pos tại điểm v >= pos; nếu duyệt đến cuối vẫn không có thì trả về false
Kết luận và tài liệu
- Tìm kiếm nhị phân kiểu giáo khoa là một thuật toán ổn, nhưng vẫn có thể được tăng tốc theo những cách mang ý nghĩa thực tế đối với hiệu năng
- Nhiều thuật toán tiêu chuẩn vốn không được thiết kế với giả định về mức độ song song cao của máy tính ngày nay
- SIMD Quad là một cách tiếp cận nhằm tận dụng cả song song mức bộ nhớ lẫn song song dữ liệu
- Vẫn có thể tồn tại các thuật toán tốt hơn, và điều đó đòi hỏi những cách tiếp cận sáng tạo hơn
- Mã nguồn
- Faster intersections between sorted arrays with shotgun
1 bình luận
Ý kiến trên Hacker News
Nếu có kiến thức trước về phân bố dữ liệu, ta có thể dùng thông tin đó để thiết kế thuật toán nhanh hơn rất nhiều. Ví dụ, với từ điển giấy, con người có thể nhảy tới một cụm trang phù hợp nhanh hơn so với binary search lý tưởng thuần túy
Về mặt toán học, tìm kiếm trong danh sách đã sắp xếp gần giống việc biến đổi ngược một hàm đơn điệu bằng thuật toán điều khiển vòng kín, và ta thậm chí có thể xây dựng một hàm chi phí phù hợp để dùng gradient descent hoặc các biến thể tăng tốc của nó
Nói rộng hơn, để giải bài toán hiệu quả hơn, cách tốt nhất là dùng nhiều thông tin hơn về chính bài toán cụ thể cần giải thay vì mang vào một lời giải bị trừu tượng hóa quá mức. Điều này có thể đem lại mức tăng tốc theo bậc độ lớn, có khả năng mở rộng tốt hơn hẳn so với cải thiện hằng số nhờ tận dụng phần cứng tốt hơn
Số vòng lặp cố định có lợi cho branch predictor, và vòng lặp lõi cũng được tối ưu hóa khá gắt theo phần cứng đích, đồng thời tránh phép nhân. Mọi nỗ lực làm nó “thông minh” hơn đều khiến vòng lặp tệ đi và không thu hồi được chi phí. Đây là dạng array-of-structs kích thước 12 và N thường cũng nhỏ nên càng khó hơn
Tôi đã không bookmark lại nên mỗi năm lại phải đi tìm lại khoảng hai lần
Vì thế B-tree là tiêu chuẩn trong cơ sở dữ liệu. Dữ liệu có thể là bất cứ thứ gì, và nếu nạp một loạt row mới thì đặc tính của nó có thể thay đổi rất mạnh bất cứ lúc nào
Bạn có thể thiết kế để tăng tốc lookup bằng các thuật toán như gradient descent, nhưng B-tree vốn đã rất nhanh, hiệu năng tệ nhất và nhu cầu I/O của nó đều dự đoán được, lại còn có nhiều ưu điểm như range scan, ordered traversal, điều kiện tiền tố
Ta có thể tạo ra thuật toán lookup hiệu quả hơn cho một phân bố dữ liệu cụ thể, nhưng thường phải đánh đổi bằng việc mất đi những thuộc tính quan trọng. Một thuật toán khác có thể cho ước lượng khởi đầu gần hơn, nhưng lại chậm hơn khi tìm tới phần tử cuối cùng; hoặc tuy nhanh hơn ở trung bình nhưng hiệu năng tệ nhất quá khủng khiếp nên khó dùng thực tế
Ngay cả với từ điển giấy, sau ước lượng đầu tiên người ta gần như cũng dùng binary search, và điều đó chỉ giảm được vài lần di chuyển. Khi đến gần vài trang đúng thì lại phải tìm tuyến tính nhiều hơn mức cần thiết; binary search nghiêm ngặt có thể nhanh hơn, nhưng còn phải cân bằng với thời gian lật trang
Ed Kmett sau đó đã phát triển ý tưởng này thành thư viện discrimination[2] cho Haskell, và bài nói chuyện kỹ thuật liên quan[3] cũng rất thú vị
[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
[2]: https://hackage.haskell.org/package/discrimination
[3]: https://www.youtube.com/watch?v=cB8DapKQz-I
Nếu đoán sai, nó bỏ toàn bộ phần công việc đã suy đoán, chịu một khoản phạt vài chu kỳ rồi bắt đầu lại từ điểm khác
Điều này có nghĩa là từ góc nhìn của bộ xử lý, mọi vòng lặp đều đã được unroll ở một mức độ nào đó, và chi phí chính của binary search là lấy dữ liệu từ bộ nhớ hoặc cache. Vì vậy trò chơi thật sự là phát yêu cầu cho dữ liệu sẽ cần đến về sau càng sớm càng tốt để giảm độ trễ
Quad search hay các kiểu tìm kiếm bậc cao hơn sẽ prefetch nông cho mọi khả năng có thể xảy ra, thay vì chỉ prefetch sâu cho một phía của mỗi branch. Nhờ đó, nó chắc chắn phát ra prefetch cho đường thực sự sẽ cần, đồng thời cũng giảm bớt một phần bandwidth bị tiêu cho dữ liệu không dùng tới trên đường thực thi thực tế
“Số phép so sánh” hầu như vô dụng như một chỉ số để so sánh thuật toán tìm kiếm nhằm dự đoán hiệu năng thực tế. Nút thắt không nằm ở lượng phép so sánh mà ở việc tận dụng tối đa bandwidth bộ nhớ và cache. Nếu xét cả cách branch hoạt động trên CPU hiện đại thì đúng là có thể xem như loop unrolling
Dù sao thì cả hai kiểu tìm kiếm đều là O(log N), chỉ khác ở hằng số. Trong lớp học thuật toán, hằng số ít quan trọng hơn, nhưng trong thực tế chúng có thể khá đáng kể
Trong workload của chúng tôi, nó mang lại tăng tốc 8 lần
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
Sau đó binary search giữa 2048 và 4096 là có thể tìm ra user mới nhất, và tiện thể cả số lượng user. Đây là thông tin khá hữu ích khi nghiên cứu các công ty SaaS cạnh tranh
Vì vậy tôi muốn thử một kiểu tìm kiếm “binary” là kiểm tra mọi giá trị trong “cache line ở giữa”, nếu không có thì đi sang trái/phải. Việc quét một cache line có thể thực hiện bằng một lệnh 512bit SIMD duy nhất
Một cache line là 64 byte, tức 32 số nguyên 16-bit, nên kiểu tìm kiếm này có thể nhanh hơn binary search đơn giản gần 32 lần. Ít nhất thì số lần truy cập bộ nhớ giảm 32 lần, và trong đa số chương trình thực tế đây mới là yếu tố chi phối
Nếu dùng key 4 byte và child pointer hoặc chỉ số mảng 4 byte, một internal node sẽ vừa khít cache line 64 byte với 7 key, 8 child pointer và 1 next pointer. Với 1 triệu entry, độ sâu cây giảm từ khoảng 20 xuống khoảng 7, và vài level trên cùng nhiều khả năng vẫn nằm trong cache
Ta cũng có thể áp dụng SIMD vào node của B-tree để tăng tốc tìm kiếm bên trong node, nhưng mức độ phụ thuộc dữ liệu là rất cao
Nhìn chung tôi thích bài này vì nó đào sâu rất trọn vẹn một điều tôi vẫn hay thắc mắc, dưới dạng một ablation study hữu ích
Nhanh nhất với mảng nhỏ là linear branchless search. Tức là không thoát sớm khỏi vòng lặp mà quét hết mọi phần tử. Ví dụ nếu chỉ cần biết một số có tồn tại trong mảng hay không thì có thể OR logic tất cả kết quả kiểm tra lại
Tôi không dùng SIMD, nhưng với mảng nhỏ, chi phí branch rất đắt nên cứ kiểm tra đơn giản mọi phần tử mà không branch lại nhanh hơn
Phần SIMD chỉ nằm ở bước cuối cùng để tìm trong 16 phần tử cuối
Phần Quad là kiểm tra 3 điểm để tạo ra 4 đường đi, nhưng mục tiêu không phải chỉ là tìm key đúng mà là tìm đúng block
Chi tiết này khá thú vị: tác giả dùng phần tử cuối của mỗi block cho quad search. Tôi tò mò thuật toán sẽ thay đổi thế nào nếu dùng phần tử đầu của mỗi block hoặc một phần tử tùy ý
Đại ý là 1) dùng gather để lấy nhiều phần tử ở 16 vị trí cách đều nhau, 2) so sánh song song bằng lệnh SIMD, 3) tập trung vào block đúng, 4) nếu block đủ nhỏ thì chuyển sang linear search, còn không thì lặp lại chu trình gather/compare
Lệnh gather đọc bộ nhớ không liên tục và đọc nhiều hơn binary search thông thường, nhưng nó cho phép multiway compare và gộp được 4 bước binary search, nên với bảng lớn có thể vẫn có lợi
Tuy vậy không phải kiểu dữ liệu nào cũng hỗ trợ so sánh 16 chiều đầy đủ. Tìm kiếm float64 bị giới hạn ở 8 chiều ngay cả với AVX-512, còn int32 và float32 thì có thể so sánh 16 chiều
Tôi cho rằng binary search trên thực tế sẽ vẫn nhanh hơn cách làm dựa trên gather
Chỉ cần lệch khỏi một trong các giả định đó là đã có rất nhiều tinh chỉnh để đạt hiệu năng tốt hơn
Điểm hay của thuật toán kinh điển là khi bạn biết thêm về một dạng dữ liệu cụ thể nào đó hoặc đặc điểm/quirk của một CPU cụ thể, chúng cung cấp một điểm xuất phát tuyệt vời để phát triển lời giải tối ưu và hiệu quả hơn
Ở tuyến đầu của tối ưu hóa, người ta thường nhìn vào cách dữ liệu được lưu trong bộ nhớ và được truy cập ra sao, cũng như liệu các thay đổi để cải thiện điều đó có gây hại cho các giai đoạn phía sau hay không. Ở chỗ làm cũ của tôi đã từng có người tối ưu một đoạn mã rất lâu, nhưng vì tối ưu đó làm đẩy nhiều thông tin cần cho giai đoạn sau ra khỏi cache hơn nên toàn bộ ứng dụng lại chậm đi
Có lẽ đây gần với quy tắc lập trình thứ 5 của Rob Pike, hay xa hơn nữa là cách diễn đạt lại điều Fred Brooks nói trong The Mythical Man Month. Tham khảo: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
Thay vì chỉ so sánh giá trị ở giữa, tôi so sánh giá trị tại điểm 1/3, rồi nếu còn quá thấp thì so sánh tiếp tại điểm 2/3
Nhưng rồi tôi nghĩ rằng so với binary search, mỗi bước không gian tìm kiếm giảm theo 1/3 thay vì 1/2, nhưng lại tốn trung bình 3/2 lần so sánh nên rốt cuộc là tương đương
Sửa: như câu trả lời của zamadatix chỉ ra, thực ra là 5/3 lần so sánh. Trường hợp 2/3 thì phải so sánh 2 lần
1/3 đầu cần 1 phép so sánh, 1/3 thứ hai cần 2 phép, và 1/3 cuối cũng cần 2 phép, nên trung bình là (1+2+2)/3 = 5/3. Rất dễ ngộ nhận kiểu “hoặc 1 hoặc 2 phép nên chắc 50/50”, nhưng thực tế xác suất dừng ở phép đầu là 1/3 còn xác suất phải làm 2 phép là 2/3
Vì vậy ternary tệ hơn một chút về tổng số phép so sánh trung bình. 5/3 * Log_3[n] = 1.052... * Log_2[n]
Nghĩa là số level có giảm, nhưng trung bình lại cần nhiều phép so sánh hơn để đi đến cùng. Điều này đúng cho mọi kiểu tìm kiếm có số nhánh tách lớn hơn 2 dưới một vài giả định tổng quát như giá trị cần tìm phân bố đều và chi phí phép toán được lý tưởng hóa. Những khác biệt của phần cứng thực tế mà bài viết nói tới chính là thứ chen vào ở đây
Chỉ là không đúng dưới dạng phiên bản ternary của binary search. Nó không phải ternary search thực sự mà gần với binary search bị lệch hơn. Vì phép so sánh về bản chất là nhị phân nên mọi thuật toán tìm kiếm dựa trên so sánh đều là một dạng binary search, và việc chọn điểm khác phần tử giữa là kém hiệu quả hơn về độ phức tạp thuật toán. Dĩ nhiên trên phần cứng thực tế, trong một số điều kiện nhất định nó có thể tốt hơn. Muốn có ternary search thật sự thì phép toán cơ bản phải là 3-way comparison
Phần thú vị là khi nghĩ về radix efficiency[1], lựa chọn tốt nhất là số tự nhiên gần e nhất, tức 3. Điều này cũng liên quan tới tree search, nơi ternary tree có thể tốt hơn binary tree
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
Ý tưởng đó có thể phi thực tế trên CPU thời ấy, nhưng ngày nay có thể thực tế hơn nhiều