Có một câu người ta hay nói chắc nịch trong các bài tối ưu: "viết code không nhánh (branchless) đi, cmov nhanh hơn if". Nghe gọn gàng, dứt khoát, và tôi cũng từng gật gù. Nhưng phần 24 đã hé ra rằng branchless không phải lúc nào cũng thắng, và phần này tôi muốn soi thẳng vào cái ranh giới đó bằng cách đo quét toàn dải.

Hình dung một người gác cổng. Nếu khách đến gần như ai cũng được vào, anh ta cứ mở sẵn cửa — gần như không tốn công. Nếu ai cũng bị chặn, anh ta cứ đóng — cũng nhàn. Nhưng nếu cứ một người vào một người ra, đoán không nổi ai là ai, anh ta phải mở-đóng liên tục, mệt nhất. Đó chính là một nhánh if trong CPU: cái giá của nó không cố định, mà tùy điều kiện có đoán được không. Còn branchless giống một cánh cửa xoay luôn quay đều — tốn một mức công cố định bất kể dòng người thế nào. Câu hỏi thật không phải "cái nào tốt hơn", mà "hai cái cắt nhau ở đâu". Tôi đo cùng một lựa chọn s = cond ? a : b, làm bằng nhánh thật và bằng cmov/csel, rồi quét xác suất điều kiện đúng từ 0% tới 100%, 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 là 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 trú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 khoảng một nửa 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 như anh gác cổng ở trên.

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 dính gì tới xác suất. Nên câu hỏi đo gọn lại thành: đườ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: đúng một đường cong hình chuông. Ở 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 trú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 khoảng một nửa, đắ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 chẳng ảnh hưởng gì; nó luôn làm cả hai vế và có một độ trễ cố định (chọn thì phải chờ cond, tạo một phụ thuộc dữ liệu).

Chỗ hai đường giao nhau rơi vào khoảng p≈15% và p≈85%: ngoài vùng đó (nhánh dễ đoán) thì nhánh thắng; trong vùng giữa (nhánh khó đoán) thì 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 lại nhanh hơn branchless (0,221 vs 0,35). Cùng một phép chọn, bên nào thắng đảo chiều tùy dữ liệu — đó mới là điều đáng nhớ.

Hai niềm tin đối nghịch, cùng sai

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". Con số bác ngay: 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 trúng thì 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 nếu vì thế mà tin điều ngược lại — "nhánh luôn kèm một chi phí mispredict cố định, tránh mọi if" — thì cũng sai nốt. Chi phí nhánh là một đường cong: gần 0 ở hai đầu (dễ đoán), chỉ vọt lên ở 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 đều đến từ cùng một chỗ: 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 vẽ đường chuông, branchless là đường ngang, và điểm giao mới là thứ quyết định.

Về đến code hằng ngày

Việc đầu tiên: chọn nhánh hay branchless theo khả năng đoán của điều kiện, không theo khẩu hiệ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)) thì cứ để nhánh — gần miễn phí. Điều kiện ngẫu nhiên ~50/50 (phân loại dữ liệu lẫn lộn) thì dùng branchless (cmov, mask, min/max, select). Không có lựa chọn đúng tuyệt đối; chỉ có lựa chọn đúng cho phân bố dữ liệu của bạn.

Việc 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 ý bằng __builtin_expect/[[likely]]/[[unlikely]], hoặc dùng profile-guided optimization (PGO) để nó đo p thật rồi tự chọn. Khi nghi, mở assembly (csel hay b.gt) và đo trên dữ liệu thật.

Chuyện này cũng không riêng gì C. Ở đâu có điều kiện chạy hàng triệu lần, cái đường chuông ấy đều hiện ra. JIT của JVM âm thầm làm đúng bài toán này: nó theo dõi một if ngả về hướng nào tại runtime rồi biên dịch lại cho hợp — và một nhánh mà dữ liệu production đổi phân bố so với lúc "học" có thể tự dưng chậm đi, đúng kiểu bạn đi từ hai đầu chuông vào giữa. Rõ nhất là ở database: bộ tối ưu truy vấn dựa vào selectivity — ước lượng bao nhiêu phần trăm hàng thỏa điều kiện — để quyết định quét tuần tự hay đi index; một điều kiện lọc ra 1% hàng (dễ đoán, rất chọn lọc) và một điều kiện lọc 50% hàng được xử lý bằng hai chiến lược khác hẳn nhau, và thống kê lệch khiến nó chọn nhầm là nguyên nhân kinh điển của truy vấn chậm. Cùng một nguyên lý: cái giá của "rẽ theo điều kiện" phụ thuộc xác suất điều kiện đúng, ở mọi tầng.

Muốn tự thấy thì viết một vòng 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 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 ấy cho 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 một quy tắc, mà là phân bố dữ liệu của bạn đang nằm ở đâu trên trục xác suất.