Bỏ if cho nhanh: mẹo hay hay giáo điều?

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: thay if bằng số học và mask để CPU khỏi phải đoán gì. Nghe hợp lý tới mức nó dễ biến thành một câu thần chú — "bỏ nhánh cho nhanh" — rồi được rải khắp nơi bất kể ngữ cảnh.

Nghĩ về nó như chọn giữa hai kiểu nấu ăn. Kiểu "có nhánh": mỗi món khách gọi mới bắt tay nấu — nếu khách chỉ gọi vài món thì tiết kiệm, nhưng cứ phải dừng lại hỏi "món này có làm không" mỗi lần. Kiểu "branchless": nấu sẵn tất cả các món rồi ai gọi gì thì bưng ra — không bao giờ phải dừng hỏi, nhưng nấu cả những món chẳng ai đụng tới. Kiểu nào lợi hơn tùy vào hai thứ: câu hỏi "có làm không" khó trả lời tới đâu, và nấu một món tốn kém cỡ nào. Tôi đo cả hai trong container gcc:13 trên host ARM, và câu trả lời rẽ về cả hai phía.

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 — chuyện này quan trọng, tôi quay lại ngay 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

Đây là chỗ câu thần chú sụp đổ. 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, ra 0,280 ns. Bản branchless vẫn làm 8 phép chia cho mọi phần tử, ra 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ỗ. Đúng là ông đầu bếp nấu sẵn cả 8 món mà khách chỉ gọi 1.

Và còn một cú lật nữa, cái này làm tôi bất ngờ nhất: "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ộ.

Hai giáo điều đối nghịch, cùng sai

Tôi vào đo với câu thần chú tối ưu: "nhánh gây mispredict, cứ viết branchless là nhanh hơn". Con số bác ngay: 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 nếu vì thế mà tin điều ngược lại — "cứ viết if là tạo một nhánh, là rước mispredict" — thì cũng 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 thì phải xem assembly (csel hay lệnh nhánh b.gt), chứ đừng đoán từ mã nguồn.

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

Việc đầ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.

Việc thứ hai: đừng branchless khi nhánh dễ đoán hoặc thân điều kiện đắt-hiếm-chạy. Điều kiện gần như luôn cùng kết quả thì predictor gần như miễn phí, branchless chỉ thêm việc. 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 thì nhánh bỏ qua được — đó là lợi thế, đừng vứt.

Điều thú vị là ở tầng cao, cái đánh đổi này gần như biến mất khỏi tầm tay bạn — và thường là điều tốt. JIT của JVM tự if-convert giống hệt trình biên dịch C, dựa trên hồ sơ nhánh nó thu tại runtime, nên viết branchless bằng tay trong Java hiếm khi đáng và đôi khi còn cản JIT. Nhưng cái tinh thần "luôn làm cả hai vế" thì lên tầng cao lại đội lốt và cắn bạn ở chỗ đắt hơn nhiều: trong SQL, một CASE WHEN dieu_kien THEN ham_nang(...) END hay một COALESCE(truy_van_con_dat_tien, ...) có thể khiến engine tính cả nhánh đắt cho mọi hàng thay vì chỉ khi cần — đúng bài toán "8 phép chia" ở trên, chỉ là mỗi "phép chia" giờ là một hàm hay một truy vấn con. Cũng vậy, trong code ứng dụng, foo() || bar() với bar() nặng dựa vào short-circuit để bỏ qua bar() — viết lại thành một biểu thức "luôn tính cả hai" là tái tạo đúng cái bẫy branchless-lỗ này. Nguyên tắc xuyên suốt: né rẽ nhánh chỉ đáng khi việc bị làm thừa là rẻ.

Muốn tự thấy thì 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). 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 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 tùy 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.