Tìm kiếm nhị phân branchless nhanh nhất

 (mhdm.dev)
1 điểm bởi GN⁺ 2023-08-13 | 1 bình luận | Chia sẻ qua WhatsApp
  • sb_lower_bound giữ nguyên giao diện như std::lower_bound, nhưng cho kết quả nhanh hơn tối đa 2 lần so với tìm kiếm nhị phân thông thường khi nhánh so sánh được biên dịch thành conditional move (cmov)
  • Kết quả so sánh trong tìm kiếm nhị phân thường gây ra branch misprediction vì không thể biết trước vị trí cần tìm, và trên x86 tùy chọn clang -mllvm -x86-cmov-converter=false giúp giảm vấn đề này
  • Cách cài đặt này giảm length còn một nửa ở mỗi vòng lặp và chỉ cập nhật first theo kết quả so sánh để giảm số lệnh, đồng thời luôn thực hiện k+1 phép so sánh trong khoảng 2^k <= n < 2^(k+1)
  • Trong benchmark clang -cmov, thời gian chạy trung bình là std::lower_bound 61.30ns, sb_lower_bound 33.24ns, bb_lower_bound 32.73ns; trung bình hình học cũng chênh lệch lớn với các giá trị lần lượt là 39.17ns, 19.81ns, 21.33ns
  • Với tìm kiếm chuỗi 8 byte khi hàm so sánh chậm, std::lower_bound đôi khi nhỉnh hơn một chút; còn với mảng lớn, biến thể có thêm prefetching nhanh hơn trung bình khoảng 2.3 lần so với std::lower_bound

Cấu trúc cơ bản của sb_lower_bound

  • sb_lower_bound là hàm C++ có cùng dạng với std::lower_bound
    • Đầu vào gồm first, last, value, comp
    • Giá trị trả về là iterator tại vị trí đầu tiên mà phép so sánh thất bại; nếu mọi phần tử đều thỏa điều kiện thì trả về last
  • Vòng lặp cốt lõi giảm length đi một nửa và chỉ di chuyển first về phía trước khi comp(first[length], value) là đúng
  • Ở đây “branchless” không có nghĩa là if biến mất, mà là if đó được biên dịch thành lệnh di chuyển có điều kiện như cmov thay vì conditional jump
  • Trong clang, có thể dùng tùy chọn -mllvm -x86-cmov-converter=false để biên dịch mẫu này thành conditional move

Điểm khiến std::lower_bound chậm đi

  • Tìm kiếm nhị phân thông thường so sánh phần tử giữa với value, rồi chọn nửa trái hoặc nửa phải
  • Khi không biết trước vị trí của giá trị cần tìm, if (comp(first[half], value)) rất dễ trở thành một nhánh khó dự đoán
  • CPU dùng branch prediction để thực thi trước lệnh tiếp theo, nhưng nếu dự đoán sai thì phải bỏ toàn bộ phần việc đã làm
  • Dùng conditional move cho phép chọn giá trị theo kết quả so sánh trong khi giảm số lần dùng conditional jump
  • clang -cmov cũng có thể biến một phần if/else trong std::lower_bound thành conditional move, giúp nhanh hơn khoảng 25%
  • gcc không có tùy chọn tốt để ép tạo conditional move trong cùng tình huống, và sb_lower_bound hiện cũng không được xuất thành mã branchless bất kể mức tối ưu hóa

Tìm kiếm “tối ưu” xét theo số lần so sánh

  • “Tối ưu” ở đây có nghĩa là tìm kiếm nhị phân có số lần so sánh nhỏ nhất
  • Với danh sách kích thước n, std::lower_bound có n+1 kết quả khả dĩ: n vị trí phần tử cộng thêm 1 vị trí cuối
  • Nếu kích thước danh sách là 2^k - 1 thì số kết quả khả dĩ là 2^k, và vì mỗi phép so sánh cho 1 bit thông tin đúng/sai nên số lần so sánh tối ưu là k
  • Trong trường hợp “đẹp” với độ dài 2^k - 1, có thể thực hiện tìm kiếm tối ưu bằng một vòng lặp rất ngắn
  • Nếu độ dài không khớp thì có thể xảy ra truy cập ngoài phạm vi, chẳng hạn khi value là 4 trong [0, 1, 2, 3, 4, 5]

Đặc tính hiệu năng và ràng buộc của sb_lower_bound

  • Khi chia đoạn có độ dài chẵn, sb_lower_bound không phải lúc nào cũng bỏ qua đủ nhiều phần tử ngay cả khi kết quả so sánh là đúng
  • Trong khoảng 2^k <= n < 2^(k+1), nó luôn thực hiện k+1 phép so sánh
  • Trong cùng khoảng đó, std::lower_bound thực hiện k hoặc k+1 phép so sánh, trung bình khoảng log2(n+1) lần
  • Số lần so sánh có thể nhiều hơn, nhưng số lệnh trong vòng lặp ít hơn đáng kể nên tổng thời gian chạy vẫn nhanh hơn
  • Nếu hàm so sánh rất chậm thì khác biệt giữa k+1 và log2(n+1) phép so sánh có thể ảnh hưởng đến hiệu năng
  • Để ép conditional move trong gcc, có thể dùng inline assembly chỉ dành cho x86 với cmov, nhưng cách đơn giản sẽ tăng số lệnh còn cách khác thì phải viết assembly riêng theo từng kiểu dữ liệu

Biến thể nhanh hơn bb_lower_bound

  • bb_lower_bound chia đoạn theo cách khác cho đến khi độ dài đạt dạng 2^k - 1, rồi tìm kiếm bằng vòng lặp thứ hai nhanh hơn
  • length & (length + 1) được dùng để kiểm tra độ dài có ở dạng 11..1, tức 2^k - 1, hay không
  • Với độ dài không chuẩn, nó dùng giá trị MAGIC auto step = length / 8 * 6 + 1 để nhanh chóng tiến gần tới một đoạn “đẹp”
  • step nhìn chung nên lớn hơn hoặc bằng length / 2 để thường xuyên chuyển sang vòng lặp nhanh, nhưng nếu quá gần length thì sẽ mất lợi thế của tìm kiếm nhị phân
  • Vì có break, bb_lower_bound trở thành dạng có nhánh
  • Cách dùng bảng tra cứu tính sẵn step nhanh nhất cho mọi độ dài vẫn là một hướng chưa được khám phá

Bản cài đặt branchless hoàn toàn không nhanh hơn

  • Trên máy 64 bit, vòng lặp của sb_lower_bound lặp tối đa 64 lần, nên có thể tạo phiên bản “branchless hoàn toàn” bỏ luôn cả kiểm tra length bằng switch và fall-through có chủ đích
  • Cách này nhảy tới vị trí mã tương ứng với số lần so sánh cần thiết dựa trên std::bit_width(length)
  • Hiệu năng thực tế không nhanh hơn
  • CPU x86 hiện đại xử lý tốt các nhánh dễ đoán như điều kiện vòng lặp, nên việc bỏ kiểm tra length không mang lại lợi ích
  • Xét cả việc tránh dùng template, macro và tránh sao chép-chỉnh sửa 64 case, tác giả đánh giá vòng lặp thông thường vẫn tốt hơn

Kết quả benchmark

  • Thời gian chạy trung bình (ns) với clang -cmov như sau
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • Trung bình hình học (ns) cũng cho thấy sb_lower_ thấp nhất
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound là biến thể dùng first += comp(first[length], value) * (length + rem) thay cho if để khuyến khích gcc sinh ra conditional move
  • Tối ưu hóa này có thể biến mất trong các phiên bản gcc sau, nên cần chú thích và lưu ý
  • Lệnh benchmark sử dụng g++-10, clang++-10, clang++-10 -mllvm -x86-cmov-converter=false và thêm -march=haswell
  • -march=native hoặc không chỉ định -march không ảnh hưởng lớn đến thứ hạng; bài test được chạy trên Intel i7 Kaby Lake

Đo branch misprediction

  • Khi đo bằng perf, bản chạy clang thông thường ghi nhận khoảng 6.94 tỷ branches và khoảng 1.20 tỷ branch-misses, tương đương tỷ lệ branch-misses 17.34%
  • Bản chạy clang -cmov ghi nhận khoảng 4.07 tỷ branches và khoảng 35.95 triệu branch-misses, giảm tỷ lệ branch-misses xuống 0.88%
  • -cmov đã loại bỏ khoảng 2.9 tỷ nhánh và khoảng 1.2 tỷ lần dự đoán nhánh sai
  • Các nhánh bị loại bỏ vốn có xác suất dự đoán sai khoảng 41%
  • Đây là giá trị gần với mức 50% có thể kỳ vọng từ những nhánh hoàn toàn không thể dự đoán

Với hàm so sánh chậm thì kết quả khác đi

  • Để xem tình huống hàm so sánh chậm hơn, tác giả thử tìm kiếm chuỗi 8 byte
  • Ở thời gian chạy trung bình (ns), std::lower_bound hơi nhanh hơn hoặc tương đương sb_lower_bound
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • Trong trường hợp này, std::lower_bound nhanh hơn sb_lower_bound một chút nhưng khá nhất quán
  • Để đạt hiệu năng tối ưu, thư viện có thể dùng sb_lower_bound cho kiểu nguyên thủy và dùng std::lower_bound cho các trường hợp còn lại

Khác biệt thể hiện trong assembly

  • Hot loop của std::lower_bound dưới clang -cmov có cmova, cmovbe và các conditional move khác, nhưng dùng nhiều lệnh để cập nhật độ dài và vị trí
  • Hot loop của sb_lower_bound tính nửa độ dài, phần dư và con trỏ cần di chuyển, rồi cập nhật first bằng cmova
  • Assembly của branchless_lower_bound rất ngắn và gọn, nhưng trong thử nghiệm hiệu năng thì sb_lower_bound cho kết quả tốt hơn nhờ overhead thấp hơn

Cập nhật: sb_lower_bound ngắn hơn nữa

  • Sau bình luận từ tác giả orlp.net, sb_lower_bound có thể được refactor để giảm số lệnh assembly trong hot loop từ 9 xuống 8
  • Ý chính là length - half bằng với half + length % 2
  • Dạng refactor tính half = length / 2, nếu so sánh đúng thì thực hiện first += length - half, sau đó cập nhật length = half
  • Với clang -cmov, thời gian chạy trung bình được cải thiện nhẹ từ khoảng 33ns xuống khoảng 32ns

Với mảng lớn, prefetching phát huy hiệu quả

  • Prefetching được đề xuất trong phần bình luận là cách đưa trước dữ liệu cần thiết vào cache L1/L2 để giảm độ trễ khi truy cập thật sự
  • Ví dụ độ trễ là khoảng 4 chu kỳ cho L1, 12 chu kỳ cho L2, 40 chu kỳ cho L3 và khoảng 200 chu kỳ cho bộ nhớ chính
  • Cả gcc lẫn clang đều hỗ trợ __builtin_prefetch()
  • Nếu prefetch tại vị trí length / 4 thì sẽ lãng phí 1 trong 2 lần; nếu thêm cả length / 8 thì sẽ lãng phí 5 trong 6 lần
  • Bản thân việc tính vị trí prefetch và gọi nó cũng tạo ra overhead, và trong hot loop đã được rút ngắn thì chi phí này rất quan trọng
  • Nhiều chiến lược prefetch khác nhau không giúp ích cho mảng nhỏ hơn 256KB
  • Từ 256KB trở lên, sbp_lower_bound có thêm prefetching cải thiện thời gian chạy trung bình từ khoảng 32ns xuống khoảng 26ns trong các thử nghiệm tới khoảng 4 triệu phần tử, tức 16MB
  • Ở bài test mở rộng sau đó lên khoảng 128 triệu phần tử, tức 512MB, phiên bản có prefetch nhanh hơn std::lower_bound khoảng 2.3 lần theo thời gian trung bình
    • Mốc so sánh là std::lower_bound khoảng 161ns và bản prefetch khoảng 71ns

Quan sát trên tập dữ liệu lớn và các lựa chọn thay thế

  • Với kích thước rất lớn, std::lower_bound branchless do clang -cmov sinh ra lại chậm hơn bản có nhánh
  • CPU hiện đại có thể đi theo nhánh đã dự đoán và tiến hành load bộ nhớ cùng speculative execution, điều này trên thực tế có thể hoạt động giống prefetch
  • sbpm_lower_bound là phiên bản thêm prefetch vào sbm_lower_bound, đồng thời dùng phép nhân boolean để khiến gcc sinh mã branchless
  • Có hiện tượng nhảy vọt trên đồ thị hiệu năng trong khoảng 1 triệu đến 10 triệu phần tử, cho thấy về mặt lý thuyết vẫn còn chỗ cho một bản cài đặt nhanh hơn
  • Tuy vậy, mã prefetch ngày càng phức tạp và có thêm nhiều hằng số magic, nên tác giả cho rằng khả năng đóng góp vào gcc/libstdc++ hay llvm/libc++ càng thấp khi độ phức tạp tăng
  • Một lựa chọn thay thế phá vỡ ràng buộc của std::lower_bound là Eytzinger Binary Search, sắp xếp lại mảng đầu vào theo dạng heap trung vị nhị phân để truy vấn thân thiện với cache hơn
  • Trong bài test int 16-ary tree của Sergey Slotin tại CppCon 2022, cách này nhanh hơn std::lower_bound từ 7 đến 15 lần

Mã nguồn và điều kiện sử dụng

  • Nếu phần tìm kiếm hoặc so sánh là nút thắt chậm nhất của chương trình, và bộ xử lý khó dự đoán kết quả so sánh, bạn có thể thử tùy chọn -mllvm -x86-cmov-converter=false của clang trên x86
  • Nếu cần một tìm kiếm nhị phân nhanh hơn, có thể thử sb_lower_bound; trên gcc, sbm_lower_bound cũng là một lựa chọn
  • Mã được phát hành theo giấy phép MIT
  • Có thể xem mã và benchmark tại github.com/mh-dm/sb_lower_bound/

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-08-13
Ý kiến trên Hacker News

  • Mỗi khi thấy mọi người cố gắng loại bỏ nhánh, tôi lại tự hỏi liệu họ có biết rằng việc dự đoán nhánh sai khiến pipeline dài bị khựng lại không phải là yếu tố bắt buộc của kiến trúc CPU hay không
    Lý do pipeline dài là vì có rất nhiều phân tích và biến đổi được thực hiện ngay trước khi thực thi, nhưng phần lớn có thể được làm trước vì đây cũng không phải là thuật toán phụ thuộc nhiều vào trạng thái
    CPU Transmeta Crusoe từng hoạt động theo kiểu này, và ta có thể tưởng tượng một thế giới nơi không cần bận tâm đến các nhánh
    Nhìn sâu hơn thì mọi phép toán đều là một nhánh nhìn vào trạng thái bit rồi thay đổi kết quả, nhưng các nhánh cục bộ như vậy bên trong ALU không phải là nhánh trên pipeline chính, nên không gây hại lớn cho hiệu năng

    • Có phải Dave không? :-) Trước đây từng có một bài báo so sánh superscalar CISC với uniscalar RISC dưới góc độ thông lượng theo thời gian và số lệnh mỗi chu kỳ xung nhịp
      Tôi nhớ hồi đó cũng đã nói với srk rằng việc chọn chỉ số IPC hay thông lượng sẽ ảnh hưởng đến cách nhìn nhận cái gì là tốt hay xấu
      Phe IPC cho rằng nếu tạo ra IPC cao hơn thì phía công nghệ chế tạo sẽ nâng xung nhịp lên và tất cả cùng thắng; còn phe thông lượng thì có cách tiếp cận thực tế hơn, cho rằng định luật Moore đã chết, chạy silicon nhanh hơn sẽ làm nó nóng chảy, nên bên thắng sẽ là bên thiết kế ISA một cách thông minh
      Trong 20 năm qua cả hai phía đều có thành công và thất bại, và thật thú vị khi gần đây RISC-V đang quay lại với những câu hỏi kiểu này trong kiến trúc CPU
      Đây cũng là nơi tốt để theo dõi cách các ý tưởng superscalar hiện đại được bổ sung dựa trên tính linh hoạt của tập lệnh, và về dài hạn tôi nghĩ hướng này sẽ thắng
    • Đây là một suy nghĩ hoàn toàn sai lầm
      Việc chuyển dịch của Transmeta không hề loại bỏ chi phí của nhánh
      Tôi nhớ Linus, khi còn làm ở Transmeta, từng nói trong một thread trên comp.arch đại ý rằng “việc của CPU là tạo ra cache miss nhanh nhất có thể”
      Cache miss bắt buộc vẫn tồn tại, và không JIT nào có thể loại bỏ chúng
      Trong thế giới thực, dù có những cache khổng lồ như hiện nay, cũng không thể tránh được capacity miss
      Itanium cũng từng cho rằng phân tích tĩnh có thể loại bỏ chi phí nhánh, và chỉ cần nhớ kết quả của nó ra sao là đủ
      Tôi mong các lập trình viên đọc thêm vài cuốn sách về kiến trúc máy tính trước khi tự tin kết luận rằng họ có thể dễ dàng tạo ra thứ tốt hơn các bộ xử lý hiện đại
      Tôi cho rằng họ đang đánh giá thấp quy mô nỗ lực trí tuệ đã được đưa vào các bộ xử lý hiện nay ít nhất khoảng 7 chữ số
    • Có thể không có trạng thái, nhưng nó phụ thuộc rất nhiều vào các yếu tố chưa biết tại thời điểm biên dịch
      Một trong số đó là dữ liệu đầu vào được xử lý
      Tìm kiếm nhị phân chính là trường hợp như vậy: compiler không biết kết quả sẽ được tìm thấy ở vị trí nào
      Một yếu tố khác là vi kiến trúc, đặc biệt là hệ phân cấp cache và cấu hình các đơn vị thực thi
      Nếu chuyển sang một ISA có các lệnh tương tự micro-operation của CPU hiện tại, mọi vi kiến trúc đều sẽ phải biên dịch lại
      Tuy vậy, về mặt kỹ thuật điều này có thể được giải quyết bằng OS JIT, theo kiểu các chương trình được phân phối dưới dạng bytecode (DXBC, SPIR-V, NVPTX) như GPU hiện nay, rồi driver GPU ở user mode biên dịch lại thành lệnh phần cứng thực tế
      Biến số lớn hơn là các luồng CPU khác đang chạy mã mà ta không biết
      Ngay cả khi loại bỏ hyperthreading để các lõi độc lập với nhau, vẫn còn các tài nguyên được chia sẻ trên toàn chip như cache L3, bộ nhớ ngoài, băng thông I/O, điện năng và nhiệt
    • Tôi nghĩ điểm mấu chốt nằm ở định nghĩa của nhánh
      Nếu định nghĩa lại mọi thứ thành Branch™, thì một số Branch™, bao gồm cả những thứ không phải nhánh thực sự, có thể được tính trước
      Nhưng việc loại bỏ nhánh theo cách nói thông thường chẳng phải là xử lý những trường hợp đường tính toán thực sự rẽ nhánh trong mã kiểu if/else sao
      Ngay cả trong thế giới đó vẫn có thể có các tối ưu hóa hữu ích, nhưng chúng sẽ bị giới hạn ở các Branch™ cố gắng tính đồng thời nhiều kết quả trong tương lai
    • Cũng có thể diễn đạt lại lý do pipeline dài là vì bên trong bộ xử lý có nhiều công việc độc lập có thể thực hiện đồng thời
      Mỗi khi có các phép toán có thể thực hiện độc lập, sẽ xuất hiện khả năng chạy chúng đồng thời
      Không chỉ nói về giải mã, nạp lệnh và thực thi
      Nếu có ALU và bộ dịch bit độc lập, thì trong lúc cộng cũng có thể dịch bit; nếu có bộ cộng và bộ nhân chuyên dụng, không có lý do gì để không thử làm cả hai cùng lúc
      Điều này đồng nghĩa với việc ta sẽ muốn có nhiều lệnh cùng đang được xử lý, và cần có khả năng nạp cũng như giải mã lệnh nhanh hơn tốc độ xử lý
      Nó cũng tự nhiên dẫn đến tình huống muốn sắp xếp lại để N lệnh Add không ngăn ta nhìn thấy một lệnh Shift độc lập
      Có thể bạn cho rằng cấu trúc hiện nay phức tạp hơn mức cần thiết, và cũng có thể bạn không sai
      Nhưng vì có lượng kỹ thuật khổng lồ được đầu tư để tạo ra cấu trúc hiện tại, nên nếu nghĩ rằng có thể làm nhanh hơn nhiều bằng một cách khác, cần đào sâu xem lập luận đó chính xác đến mức nào

  • Ở đoạn “Ước gì có một ngôn ngữ bare-metal sạch và nhanh để viết tất cả những thứ này…”, tác giả có chèn chú thích “BUT RUST..” và “BUT ZIG..”, nhưng tôi tò mò không biết Nim thì sao
    Có vẻ có phần triển khai thư viện native cho lowerBound: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    Nói nghiêm ngặt thì nó không phải ngôn ngữ “bare-metal”, nhưng vì biên dịch sang C hoặc C++, nên sẽ thú vị nếu xem nó được biên dịch thành mã gì ở đây
    Và tôi cũng tò mò C thì có vấn đề gì

  • Tôi vẫn không chắc đây có còn là lower_bound không
    Có thể tôi đọc nhầm mã, nhưng có vẻ khi có phần tử trùng lặp, nó trả về một mục khớp bất kỳ chứ không phải mục khớp đầu tiên
    Nếu hàm so sánh đang tìm một tiền tố chuỗi cụ thể để phục vụ tự động hoàn thành, thì ngay cả trong danh sách duy nhất cũng có thể có nhiều mục khớp, và khi đó ta muốn mục đầu tiên trong danh sách

    • Mỗi lần khớp thì nó giảm một nửa độ dài còn lại, và chỉ thoát vòng lặp khi độ dài bằng 0, nên nó phải trả về mục đầu tiên
    • Có một tùy chọn nhanh hơn mà không quan tâm chính xác là mục khớp nào thì có vẻ hay
    • Theo tôi thấy thì nó trả về mục khớp đầu tiên
      Tôi tò mò vì sao bạn lại nghĩ là không

  • Ước gì mọi bài blog đều bắt đầu như bài này: “Chắc các bạn bận, nên tôi sẽ đi thẳng vào vấn đề. Đây là triển khai tìm kiếm nhị phân C++ nhanh nhất, tổng quát nhất và đơn giản nhất”

  • Thư viện chuẩn Zig không gọi C++ để tìm kiếm nhị phân
    Tìm kiếm nhị phân hiện nằm ở đây: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • Tôi không hiểu lắm
    Vấn đề của tìm kiếm nhị phân và nhánh không phải là bản thân nhánh, mà là trước khi hoàn tất phép so sánh, ta không biết cần lấy vị trí bộ nhớ nào tiếp theo trong mảng
    Dù dùng nhánh hay thứ gì khác cũng không quan trọng; cuối cùng vấn đề là ta muốn bộ xử lý làm gì
    Có sự phụ thuộc dữ liệu
    Trước khi đọc chỉ số giữa, ta không biết sẽ tìm trong nửa trên hay nửa dưới
    Có thể suy đoán và phát lệnh đọc cả hai phía; như vậy sẽ giải quyết được phụ thuộc, nhưng lại tăng lưu lượng bộ nhớ
    Trọng tâm là liệu đó có phải đánh đổi đúng hay không, còn chỉ loại bỏ nhánh thì không phải câu trả lời

    • Với mảng lớn, prefetching là đánh đổi đúng
      Phần cuối bài có bàn đến: https://mhdm.dev/posts/sb_lower_bound/#prefetching
    • Đúng vậy
      Vì thế tìm kiếm nhị phân nhanh hơn một cách đúng đắn sẽ dùng bố trí mảng Eytzinger: https://algorithmica.org/en/eytzinger
    • Nếu mảng nằm hoàn toàn trong cache L1, chẳng phải chi phí dự đoán sai nhánh lớn hơn nhiều so với việc nạp bộ nhớ sao?

  • Trên bộ xử lý Cascade Lake của tôi, -mllvm -x86-cmov-converter=false làm hiệu năng tìm kiếm nhị phân giảm gần một nửa
    Các con số là nanosecond cho mỗi lần bsearch trên mảng uint32 100MB
    clang 15.0.7 có vẻ kém gcc 13.2.1 hơn rất nhiều trong việc tối ưu hóa đoạn mã cụ thể này
    Có thể xem assembly tại đây: https://godbolt.org/z/cbx5Kdjs6
    Assembly của gcc trông gọn gàng hơn nhiều

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4

  • Có ai biết liên kết “BUT RUST” ban đầu đáng lẽ trỏ tới đâu không?
    Vì không cố định phiên bản nên có vẻ nó đã hỏng, và không biết có phải định trỏ vào giữa phần chú thích tài liệu của starts_with hay không

    • Nhìn các bản chụp archive.org ngay trước [1] và ngay sau [2] khi bài được công bố, có vẻ nó định trỏ tới dòng mã này, hiện đã trở thành dòng 2779 [3]
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Vốn định liên kết tới triển khai tìm kiếm nhị phân của Rust
    Đã được cập nhật thành https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

  • Điều thú vị là với hàm so sánh comp phức tạp hơn thì kết quả này không còn giữ nguyên
    Bài viết cho biết họ đã nghĩ đến các kịch bản tìm kiếm nhị phân khá thực tế, trong đó hàm so sánh chậm, như ID, số điện thoại, tài khoản, từ khóa, nên đã thử nghiệm tìm kiếm chuỗi 8 byte
    Trong trường hợp này, std::lower_bound nhanh hơn sb_lower_bound rất nhẹ nhưng nhất quán; để luôn đạt hiệu năng tốt nhất, thư viện nên dùng sb_lower_bound khi xử lý trực tiếp các kiểu nguyên thủy, còn các trường hợp khác thì dùng std::lower_bound
    Muốn xem phần phân tích ở đây

    • Tôi cho rằng điều này xảy ra nhờ dự đoán nhánh, vì có thể đưa nhiều phép so sánh vào pipeline cùng lúc và quay lui khi bộ dự đoán sai
      Nếu dữ liệu và đầu vào thật sự ngẫu nhiên, dự đoán sẽ sai khoảng một nửa
      Cách dùng CMOV bị chặn sau hàm so sánh do phụ thuộc dữ liệu
      Trung bình, cách dùng nhánh thực hiện hai phép so sánh cùng lúc, còn CMOV thực hiện một phép, nên khi thời gian so sánh lớn hơn penalty do dự đoán nhánh sai, có lẽ sẽ xuất hiện điểm đảo chiều
    • Nếu vậy, rất có thể có phiên bản tìm kiếm nhị phân tốt hơn nhiều cho các kiểu nguyên thủy
      Một bản tôi từng làm qua loa bằng SIMD trước đây nhanh hơn std::lower_bound 3 lần cho đến khi bị giới hạn bởi băng thông bộ nhớ: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • Tôi không tìm thấy bảo đảm nào về tập dữ liệu đầu vào hay nội dung khóa tìm kiếm ngoài việc bài viết nói là “không thể dự đoán”
      Giả sử là hoàn toàn ngẫu nhiên, nhưng nếu các chuỗi 8 byte này không phải là thông tin thuần túy, bộ dự đoán nhánh hiện đại có thể dễ dàng đạt hiệu năng tốt hơn cmov

  • Có vẻ thuộc tính unpredictable giờ đã ảnh hưởng đến pass chuyển đổi cmov
    Tính đến ngày 1/6, nên có lẽ sẽ được đưa vào clang 17/18: https://reviews.llvm.org/D118118