Phần 24 cho thấy branchless không phải lúc nào cũng thắng. Phần này soi thẳng vào ranh giới ấy bằng một phép đo quét: cùng một lựa chọn s = cond ? a : b, làm bằng nhánh thật hay bằng cmov/csel (chọn có điều kiện, không nhánh), rồi quét xác suất điều kiện đúng từ 0% tới 100%. Kết quả vẽ ra một bức tranh gọn ghẽ: chi phí của nhánh là một đường cong hình chuông, còn branchless là một đường thẳng phẳng — và chỗ chúng giao nhau chính là nơi bạn nên đổi từ cái này sang cái kia. Tôi đo trong container gcc:13 trên host ARM.
Nhánh: chi phí tùy đoán được hay không
Một nhánh if(cond) tốn bao nhiêu không cố định — nó phụ thuộc dự đoán nhánh có đúng không (phần 1). Nếu cond gần như luôn cùng kết quả (luôn đúng hoặc luôn sai), bộ dự đoán học được và đoán đúng gần như mọi lần → nhánh gần như miễn phí. Nếu cond ngẫu nhiên 50/50, không đoán nổi → mispredict ~50% số lần, mỗi lần xả pipeline mất cả chục chu kỳ. Vậy chi phí nhánh là một hàm của xác suất cond đúng.
Ngược lại, cmov/csel (hay branchless bằng số học) luôn tính cả hai vế rồi chọn — không có nhánh nên không đoán, không mispredict. Chi phí của nó cố định, không phụ thuộc xác suất. Câu hỏi đo: đường cong của nhánh và đường thẳng của branchless cắt nhau ở đâu?
Đo: đường cong chuông gặp đường thẳng
Tôi chọn a[i] hay b[i] tùy cond[i] (đúng với xác suất p ngẫu nhiên), quét p từ 0 tới 100%, đo cả hai bản (nhánh thật giữ bằng -fno-if-conversion; branchless bằng số học, đã kiểm assembly không có lệnh nhánh nào):
Chọn a[i]/b[i] tùy cond[i] (p = xác suất true), N=16384 (L1), ns/phần tử:
p (%) | nhánh thật | branchless
-----------|------------|------------
0 (luôn sai/đúng, dễ đoán) | 0,221 | 0,343
10 | 0,336 | 0,366
25 | 0,407 | 0,404
50 (50/50, khó đoán nhất) | 0,582 | 0,369 <- nhánh đỉnh chuông
75 | 0,422 | 0,379
90 | 0,331 | 0,409
100 (dễ đoán) | 0,221 | 0,348
Nhìn cột nhánh thật: một đường cong hình chuông hoàn hảo. Ở p=0% và p=100% (điều kiện luôn cùng kết quả, dễ đoán), nhánh chỉ 0,221 ns — bộ dự đoán đúng gần như mọi lần, nhánh gần miễn phí. Càng gần p=50%, càng khó đoán, chi phí càng leo, và đỉnh ở p=50% là 0,582 ns — mispredict ~50%, đắt nhất.
Nhìn cột branchless: phẳng lì ~0,34–0,41 ns ở mọi p. Không có nhánh nên xác suất không ảnh hưởng gì; nó luôn làm cả hai vế và có một độ trễ cố định (chọn phải chờ cond, tạo phụ thuộc dữ liệu).
Điểm giao rơi vào khoảng p≈15% và p≈85%: ngoài vùng đó (nhánh dễ đoán), nhánh thắng; trong vùng giữa (nhánh khó đoán), branchless thắng. Ở p=50%, branchless nhanh hơn nhánh 1,6 lần (0,369 vs 0,582); nhưng ở p=0/100%, nhánh nhanh hơn branchless (0,221 vs 0,35). Cùng một phép chọn, bên nào thắng đảo tùy dữ liệu.
Một lần tôi đo hớ: "cmov luôn tốt hơn nhánh" và "nhánh luôn tốn mispredict"
Tôi vào đo với niềm tin của phe branchless: "cmov/csel né được mispredict nên luôn tốt hơn nhánh". Đo phá tan: khi nhánh dễ đoán (p gần 0 hoặc 100%), nhánh chỉ 0,221 ns — nhanh hơn branchless 0,35 ns. Vì một nhánh được đoán đúng gần như miễn phí (CPU chạy thẳng, không xả pipeline), còn branchless luôn làm cả hai vế và tạo một phụ thuộc dữ liệu. cmov không phải bùa vạn năng; ở vùng dễ đoán nó thua.
Nhưng đo cũng phá một niềm tin ngược: "nhánh luôn kèm một chi phí mispredict cố định". Sai — chi phí nhánh là một đường cong: ~0 ở hai đầu (dễ đoán), đỉnh ở giữa (khó đoán). Một nhánh trong vòng lặp không mặc định đắt; nó chỉ đắt khi khó đoán. Cả hai sai lầm đến từ việc gán một con số cố định cho thứ vốn biến thiên theo xác suất. Bức tranh đúng là: nhánh = chuông, branchless = phẳng, và điểm giao quyết định bên nào thắng.
Bài học đo lường: cmov/branchless vs nhánh: bên nào thắng TÙY XÁC SUẤT điều kiện. Nhánh = ĐƯỜNG CONG CHUÔNG (đo: ~0,22 ns ở p=0/100 dễ đoán, đỉnh 0,58 ns ở p=50 mispredict ~50%); branchless = PHẲNG ~0,37 ns mọi p. Giao ~p=15%/85%: dễ đoán (gần 0/100) -> NHÁNH thắng (đoán đúng gần free); khó đoán (giữa) -> BRANCHLESS thắng 1,6x (né mispredict). 'cmov luôn tốt hơn' và 'nhánh luôn tốn mispredict' đều SAI. Nếu tin "cmov luôn thắng" tôi branchless-hóa cả nhánh dễ đoán và chậm đi; nếu tin "nhánh luôn tốn" tôi sợ mọi if.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: chọn nhánh hay branchless theo khả năng đoán của điều kiện. Nếu điều kiện gần như luôn cùng kết quả (kiểm tra biên hiếm xảy ra, if(unlikely)), để nhánh — nó gần miễn phí. Nếu điều kiện ngẫu nhiên ~50/50 (phân loại dữ liệu lẫn lộn), dùng branchless (cmov, mask, min/max, select). Không có lựa chọn "đúng" tuyệt đối; có lựa chọn đúng cho phân bố dữ liệu của bạn.
Hệ quả thứ hai: giúp trình biên dịch chọn đúng — nó không biết xác suất trước. Trình biên dịch quyết định if-convert (thành csel) hay giữ nhánh mà không biết p thật. Bạn có thể gợi ý: __builtin_expect/[[likely]]/[[unlikely]] cho biết nhánh dễ đoán về phía nào, hoặc dùng profile-guided optimization (PGO) để nó đo p thật rồi chọn. Khi nghi ngờ, xem assembly (csel hay b.gt) và đo trên dữ liệu thật.
Hệ quả thứ ba là tinh thần đo lường: chi phí một nhánh không phải hằng số — nó là hàm của xác suất, và branchless là đường ngang cắt qua đường cong ấy. Con số mang theo: nhánh = chuông (~0 ở dễ đoán, đỉnh ~0,58 ns ở p=50); branchless = phẳng ~0,37 ns; giao ~p=15%/85%. Dễ đoán để nhánh, khó đoán dùng branchless; gợi ý compiler bằng expect/PGO. Cùng một if, trên dữ liệu này thì để nhánh nhanh hơn, trên dữ liệu kia thì branchless nhanh hơn — chỉ đo phân bố thật mới biết bạn đang ở phía nào của điểm giao.
Thử ba mươi giây
Viết một vòng lặp chọn s += cond[i] ? a[i] : b[i] hai cách: một dùng if thật (biên dịch với -fno-if-conversion để giữ nhánh), một branchless bằng số học (long m = -(long)(cond[i]!=0); s += b[i] + ((a[i]-b[i]) & m);). Sinh mảng cond sao cho tỉ lệ true là p, ngẫu nhiên, rồi quét p = 0, 10, 25, 50, 75, 90, 100% và bấm giờ. Bạn sẽ thấy bản nhánh vẽ một đường cong chuông — rẻ ở hai đầu (dễ đoán), đắt nhất ở p=50% (mispredict) — còn bản branchless phẳng lì ở mọi p. Tìm chỗ hai đường cắt nhau: đó là ngưỡng khó-đoán mà từ đó branchless bắt đầu thắng. Ba mươi giây đó cho bạn thấy điều mà "cmov luôn tốt hơn nhánh" giấu đi: một nhánh dễ đoán gần như miễn phí, còn branchless trả một giá cố định — nên bên thắng không phải là một quy tắc, mà là phân bố dữ liệu của bạn nằm ở đâu trên trục xác suất.
