Tìm kiếm nhị phân không nhánh nhanh nhất

• Bài viết này bàn về một triển khai tìm kiếm nhị phân C++ tổng quát ngắn gọn hơn và nhanh gấp đôi so với hàm chuẩn std::lower_bound.
• Triển khai mới là "không nhánh" vì nó được biên dịch thành các lệnh di chuyển có điều kiện thay vì phân nhánh/nhảy có điều kiện.
• Tìm kiếm nhị phân hoạt động bằng cách chia một danh sách đã sắp xếp thành hai phần tại phần tử giữa, rồi so sánh giá trị ở giữa với giá trị cho trước. Dựa trên kết quả so sánh, nó quyết định sẽ tiếp tục tìm trong phần nào của hai phần đó.
• Bài viết cũng thảo luận về khái niệm dự đoán nhánh, một kỹ thuật mà bộ xử lý dùng để thực thi lệnh song song nhằm tăng tốc. Tuy nhiên, vì tìm kiếm nhị phân khó dự đoán nên dự đoán nhánh không phải là lựa chọn lý tưởng.
• Tác giả giới thiệu một triển khai tìm kiếm nhị phân mới, sb_lower_bound, nhanh hơn cả triển khai chuẩn lẫn phiên bản branchless_lower_bound. Nó nhanh hơn vì có ít lệnh hơn đáng kể bên trong vòng lặp.
• Tác giả cũng đưa ra một phiên bản nhanh hơn nữa, bb_lower_bound, sử dụng một cách khác để chia danh sách tìm kiếm.
• Bài viết kết thúc bằng gợi ý rằng nếu phần chậm nhất của chương trình có chứa thao tác tìm kiếm và/hoặc so sánh mà bộ xử lý không thể dự đoán, hãy thử dùng clang với -mllvm -x86-cmov-converter=false. Nếu cần tìm kiếm nhị phân nhanh hơn, hãy thử sb_lower_bound.
• Tác giả cũng cung cấp mã cho các triển khai tìm kiếm nhị phân mới và thảo luận chi tiết về hiệu năng của từng phiên bản.
• Bài viết đã được cập nhật với một phiên bản tái cấu trúc của sb_lower_bound giúp giảm số lệnh assembly trong vòng lặp nóng từ 9 xuống 8, nhờ đó cải thiện tốc độ đôi chút.
• Tác giả cũng thảo luận về khái niệm prefetching, tức là đưa trước một phần bộ nhớ cụ thể vào cache để khi dữ liệu được prefetch thực sự cần đến thì chỉ còn độ trễ của cache L1/L2. Một phiên bản sb_lower_bound có thêm prefetching cho 256KB+ cũng được cung cấp.
• Bài viết do Mihail Dumitrescu viết và được xuất bản vào ngày 24 tháng 6 năm 2023.

[GN⁺]

Ý kiến trên Hacker News

• Bài viết thảo luận về khái niệm tìm kiếm nhị phân không phân nhánh và những lợi ích tiềm năng của nó.
• Một bình luận đặt câu hỏi về sự cần thiết của việc loại bỏ nhánh, cho rằng tình trạng pipeline bị đình trệ do dự đoán nhánh sai không phải là phần bản chất của kiến trúc.
• Bình luận này nói rõ thêm rằng mọi thao tác về bản chất đều là nhánh, và lý do những nhánh này không gây hại đến hiệu năng là vì chúng không phải là các nhánh trên pipeline chính.
• Một bình luận khác đề xuất sử dụng ngôn ngữ Nim, được biên dịch sang ngôn ngữ "bare-metal", để triển khai lowerBound.
• Có thảo luận về việc đoạn mã có trả về kết quả khớp đầu tiên hay chỉ trả về một kết quả khớp bất kỳ, nhấn mạnh tầm quan trọng của việc hiểu chức năng của đoạn mã.
• Một bình luận khen phần giới thiệu trực quan của bài blog, vì nó nhanh chóng đưa ra một triển khai C++ tìm kiếm nhị phân tổng quát nhanh nhất.
• Một bình luận chỉ ra rằng Zig stdlib không gọi C++ để thực hiện tìm kiếm nhị phân, đồng thời cung cấp liên kết đến phần tìm kiếm nhị phân của Zig stdlib.
• Có thảo luận về vấn đề của tìm kiếm nhị phân và nhánh, cho rằng vấn đề không nằm ở bản thân nhánh mà ở sự phụ thuộc dữ liệu: không biết vị trí bộ nhớ cần nạp tiếp theo cho đến khi phép so sánh hoàn tất.
• Một bình luận chia sẻ kết quả hiệu năng của tìm kiếm nhị phân trên bộ xử lý Cascade Lake, cho rằng clang tối ưu đoạn mã cụ thể này kém hơn gcc.
• Một bình luận đặt câu hỏi về đích đến của liên kết "BUT RUST", nói rằng liên kết này có vẻ đã cũ.
• Một bình luận chỉ ra rằng kết quả này không còn giữ được với các hàm so sánh phức tạp hơn, và cho rằng hiệu năng tốt nhất có thể đạt được bằng cách dùng sb_lower_bound cho các kiểu cơ bản và std::lower_bound cho các trường hợp khác.
• Bình luận cuối cùng nhắc rằng thuộc tính không thể dự đoán hiện nay cũng ảnh hưởng đến pass chuyển đổi cmov, đồng thời cung cấp một liên kết để tham khảo thêm.