Phần 1 và phần 2 cho thấy một nhánh if khó đoán tốn cả chục chu kỳ mỗi lần CPU đoán sai. Cách né kinh điển là viết code không nhánh (branchless): thay if bằng số học và mask để CPU không phải đoán gì. Nhưng "bỏ nhánh cho nhanh" dễ thành một giáo điều — áp dụng mù ở mọi nơi. Tôi đo trong container gcc:13 trên host ARM để xem branchless thật sự thắng khi nào và thua khi nào, và câu trả lời có cả hai chiều.
Thay if bằng mask: luôn tính, chọn bằng bit
Ý tưởng branchless: thay vì rẽ nhánh (mà CPU phải đoán), luôn tính cả hai khả năng rồi chọn kết quả bằng phép bit hoặc số học — không có nhánh nên không có gì để đoán sai. Ví dụ, để cộng dồn chỉ các phần tử dương:
// có nhánh: CPU phải đoán if mỗi vòng
if (v > x) s += v;
// branchless: mask = 0 hoặc -1 (toàn bit 1), rồi AND
long long m = -(long long)(v > x); // v>x ? -1 : 0
s += v & m; // cộng v hoặc cộng 0
Bản branchless luôn thực hiện & m và +=, không rẽ nhánh. CPU chạy tuần tự, không mispredict. Câu hỏi đo: đánh đổi "luôn làm cả hai vế" lấy "không mispredict" có đáng không? Tôi đo trên mảng nhỏ nằm trong L1 (để cô lập chi phí nhánh, không dính bộ nhớ), với -fno-if-conversion để giữ nhánh thật (nếu không, trình biên dịch tự biến if thành lệnh chọn — sẽ nói ở dưới).
Đo: branchless thắng khi nhánh khó đoán
Tổng phần tử > 0, N=16384 (L1), host ARM, ns/phần tử:
THÂN RẺ (chỉ cộng):
có nhánh, data NGẪU NHIÊN (khó đoán ~50%) : 0,730 ns <- mispredict nhiều
có nhánh, data ĐÃ SẮP (nhánh dễ đoán) : 0,338 ns
branchless (bất kể data) : 0,244-0,247 ns
Trên dữ liệu ngẫu nhiên — nhánh if(v>0) đúng/sai ~50%, không đoán nổi — bản có nhánh tốn 0,730 ns, còn branchless chỉ 0,244 ns: nhanh gấp 3 lần. Toàn bộ khác biệt là mispredict: branchless không có nhánh nên không trả giá đoán sai. Đây là ca branchless tỏa sáng.
Trên dữ liệu đã sắp — nhánh gần như luôn cùng kết quả (một lần chuyển từ false sang true), predictor học được — bản có nhánh xuống 0,338 ns. Branchless vẫn 0,247 ns, chỉ còn nhanh hơn 1,4 lần. Khi nhánh dễ đoán, khoảng cách co lại nhiều: predictor gần như miễn phí, nên lợi thế của branchless mỏng đi.
Đo: nhưng branchless không phải lúc nào cũng thắng
Branchless luôn thực hiện cả vế điều kiện. Nếu vế đó rất đắt và hiếm khi cần chạy (nhánh dễ đoán là "bỏ qua"), thì có nhánh lại thắng vì nó bỏ qua được việc đắt:
Thân RẤT ĐẮT (8 phép chia), điều kiện ~1% thỏa (gần như luôn false):
có nhánh (bỏ qua 8 phép chia khi false) : 0,280 ns <- thắng
branchless (luôn làm 8 phép chia) : 0,445 ns
Ở đây thân điều kiện là 8 phép chia (phép đắt nhất), và điều kiện chỉ đúng ~1% (gần như luôn false, cực dễ đoán). Bản có nhánh bỏ qua 8 phép chia trong 99% trường hợp → 0,280 ns. Bản branchless vẫn làm 8 phép chia cho mọi phần tử → 0,445 ns, chậm hơn 1,6 lần. Branchless đổi "không mispredict" (mà ở đây gần như không có, vì nhánh dễ đoán) lấy "làm việc đắt vô ích" — một đánh đổi lỗ.
Và còn một cú lật nữa: "cứ viết if là có nhánh" cũng sai. Khi tôi biên dịch bản có nhánh với -O2 mặc định (không chặn if-conversion), trình biên dịch tự biến if thành lệnh csel (conditional select — chọn có điều kiện, không nhánh). Kết quả: bản "có nhánh" trên dữ liệu ngẫu nhiên xuống 0,445 ns (so với 0,730 ns khi giữ nhánh thật) — vì nó đã thành branchless mà tôi không viết dòng nào. Xem assembly thấy csel là bằng chứng compiler đã bỏ nhánh hộ.
Một lần tôi đo hớ: "branchless luôn nhanh hơn" và "cứ if là có nhánh"
Tôi vào đo với giáo điều tối ưu: "nhánh gây mispredict, cứ viết branchless là nhanh hơn". Đo phá tan: branchless chỉ thắng rõ khi nhánh khó đoán và thân rẻ (ngẫu nhiên: 3 lần). Khi nhánh dễ đoán, khoảng cách co còn 1,4 lần; và khi thân rất đắt mà hiếm chạy, branchless thua (0,445 vs 0,280) vì nó làm việc đắt cho mọi phần tử. Áp dụng branchless mù quáng có thể làm chậm code khi nhánh vốn đã dễ đoán hoặc vế điều kiện tốn kém.
Nhưng đo cũng phá một niềm tin ngược: "cứ viết if là tạo một nhánh, là rước mispredict". Sai — trình biên dịch -O2 thường tự if-convert if đơn giản thành csel/cmov, tức là đã branchless rồi (đo được: 0,445 vs 0,730 khi giữ nhánh thật). Nên nhiều lúc bạn không cần viết branchless bằng tay — compiler đã làm. Muốn biết chắc, phải xem assembly (csel hay lệnh nhánh b.gt), chứ không đoán từ mã nguồn.
Bài học đo lường: branchless (mask/số học) né mispredict, nhưng LUÔN tính cả hai vế. Đo: THẮNG khi nhánh KHÓ ĐOÁN + thân RẺ (sum>0 random: branchless 0,244 vs nhánh 0,730 = 3x); co còn 1,4x khi nhánh dễ đoán; THUA khi thân RẤT ĐẮT + nhánh dễ đoán (8 chia ~1% thỏa: có nhánh 0,280 vs branchless 0,445). VÀ -O2 tự if-convert 'if' thành csel (không nhánh) nhiều ca — 'có nhánh' random -O2 0,445 vs giữ nhánh thật 0,730. 'Branchless luôn nhanh hơn' và 'cứ if là có nhánh' đều SAI. Nếu tin "branchless luôn thắng" tôi làm chậm code nhánh-dễ/thân-đắt; nếu tin "if luôn là nhánh" tôi viết tay thứ compiler đã làm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: branchless đáng dùng khi nhánh KHÓ ĐOÁN và thân điều kiện RẺ. Lọc/phân loại/cộng-có-điều-kiện trên dữ liệu ngẫu nhiên (như phần 1) là ứng viên tốt — thay if bằng mask/min/max/select để né mispredict. Nhưng đo trước khi tin.
Hệ quả thứ hai: đừng branchless khi nhánh dễ đoán hoặc thân điều kiện đắt-hiếm-chạy. Nếu điều kiện gần như luôn cùng kết quả, predictor gần như miễn phí và branchless chỉ thêm việc. Nếu vế điều kiện tốn kém (chia, hàm nặng, truy cập bộ nhớ) mà hiếm khi cần, nhánh bỏ qua được — đó là lợi thế, đừng vứt.
Hệ quả thứ ba là tinh thần đo lường: branchless là một đánh đổi, không phải luật; và compiler thường tự chọn giúp. Con số mang theo: branchless thắng 3x khi nhánh khó đoán + thân rẻ; thua 1,6x khi thân đắt-hiếm-chạy + nhánh dễ đoán; -O2 tự if-convert 'if' thành csel nhiều ca (kiểm asm). Đo và xem assembly, đừng theo giáo điều. Cùng một bài toán, viết có nhánh hay không nhánh, nhanh chậm ngược nhau tùy dữ liệu đoán được không và vế điều kiện đắt cỡ nào — chỉ đo mới biết bên nào thắng.
Thử ba mươi giây
Viết hàm cộng dồn các phần tử > 0 của một mảng, hai cách: có nhánh if(a[i]>0) s+=a[i]; và branchless s += a[i] & -(long)(a[i]>0);. Bấm giờ trên hai loại dữ liệu: ngẫu nhiên (dấu lẫn lộn, nhánh khó đoán) và đã sắp (nhánh dễ đoán). Bạn sẽ thấy trên dữ liệu ngẫu nhiên, branchless nhanh vài lần; trên dữ liệu đã sắp, hai bản gần bằng nhau. Rồi đổi thân điều kiện thành thứ rất đắt (vài phép chia) và cho điều kiện hiếm khi đúng: lần này bản có nhánh thắng, vì nó bỏ qua được việc đắt. Cuối cùng, biên dịch bản có nhánh với -O2 và xem assembly (g++ -O2 -S): rất có thể bạn thấy csel/cmov thay vì lệnh nhảy — trình biên dịch đã bỏ nhánh giúp. Ba mươi giây đó cho bạn thấy điều mà "branchless luôn nhanh" giấu đi: bỏ nhánh là một đánh đổi — né mispredict nhưng làm cả hai vế — và bên thắng phụ thuộc nhánh có đoán được không, vế điều kiện đắt cỡ nào, và cả việc trình biên dịch có tự làm hộ hay chưa.
