Hình dung một ngã ba đường. Cách thứ nhất: đoán rẽ trái hay phải rồi phóng đi luôn — nếu đoán đúng thì mượt, đoán sai thì phải lùi lại quay đầu, tốn thời gian. Nhưng nếu ngày nào bạn cũng rẽ đúng một hướng, cái đoán ấy gần như không tốn gì, và bạn khỏi phải đi con đường kia. Cách thứ hai: đi cả hai nhánh một đoạn rồi mới chọn — không bao giờ đoán sai phải quay đầu, nhưng luôn phải trả công cho cả con đường bị bỏ. CPU xử lý một câu if đúng theo hai cách đó, và câu "code không nhánh luôn nhanh hơn" quên mất rằng cách nào thắng là tùy bạn đoán dễ hay khó.

Một if nhỏ như if(a > b) m = a; else m = b; có thể biên dịch theo hai kiểu rất khác nhau. Kiểu quen thuộc là một rẽ nhánh có điều kiện: CPU đoán hướng đi rồi chạy tiếp. Kiểu kia là một lệnh chọn có điều kiện không rẽ nhánh — csel trên ARM, cmov trên x86 — tính cả hai khả năng rồi chọn kết quả, không nhánh nào để đoán. Lời khuyên "viết code không nhánh (branchless) cho nhanh" rất phổ biến. Tôi đo trong container gcc:13 (ARM) với niềm tin đó, và tìm ra nó chỉ đúng một nửa.

Hai cách biên dịch một if

Khi gặp if, CPU hiện đại không chờ biết điều kiện đúng hay sai — nó đoán và chạy tiếp theo phỏng đoán (như dự đoán nhánh đã bàn). Đoán đúng thì gần như miễn phí. Đoán sai thì phải xả (flush) toàn bộ ống lệnh đã chạy nhầm và làm lại — phạt khoảng 15-20 chu kỳ, đúng cái lùi xe quay đầu. Cái giá của rẽ nhánh vì thế nằm ở tỉ lệ đoán sai.

Lệnh không nhánh (csel/cmov) tránh hẳn chuyện đoán: nó tính cả hai vế rồi dùng cờ điều kiện chọn giá trị đúng. Không có nhánh, không có phạt đoán sai. Nhưng đổi lại, nó luôn làm việc của cả hai vế và không bao giờ được bỏ qua phần việc của vế không được chọn — đúng cảnh đi cả hai con đường rồi mới chọn. Đây chính là chỗ đánh đổi mà tôi không cân nhắc đủ.

Tôi đo một vòng cộng a[i] chỉ khi a[i] >= 128, trên 40 triệu phần tử. objdump xác nhận hai bản đúng như tên gọi: bản có nhánh dùng tbz (test bit rồi rẽ — một nhánh phụ thuộc dữ liệu), bản không nhánh dùng csel. Rồi tôi đổi độ đoán được của nhánh bằng cách đổi tỉ lệ p số phần tử thỏa điều kiện.

Đo: đường cong lật theo độ đoán được

p (tỉ lệ điều kiện đúng)   có nhánh (tbz)   không nhánh (csel)   ai thắng
50%  (khó đoán nhất)          2,512 ns           0,474 ns         csel, nhanh 5,3 lần
90%                            0,729 ns           0,474 ns         csel
99%  (dễ đoán)                 0,312 ns           0,481 ns         CÓ nhánh

Nhìn cột "có nhánh" trước: nó dao động mạnh theo p. Ở p = 50% (nhánh ngẫu nhiên, khó đoán nhất), mỗi phần tử là một canh bạc 50/50 — bộ dự đoán sai khoảng một nửa số lần, và mỗi lần sai phạt 15-20 chu kỳ, đẩy thời gian lên 2,512 ns. Ở p = 99% (nhánh gần như luôn đúng), bộ dự đoán gần như không bao giờ sai, và thời gian rớt xuống 0,312 ns.

Cột "không nhánh" thì phẳng — khoảng 0,47-0,48 ns bất kể p. Vì csel không đoán gì, độ đoán được của dữ liệu không ảnh hưởng tới nó. Nó làm cùng một lượng việc mọi lúc.

Hai đường cắt nhau. Ở nhánh khó đoán, csel thắng lớn — 5,3 lần ở p=50%. Ở nhánh dễ đoán, bản có nhánh lại nhanh hơn: 0,312 so với 0,481 ns ở p=99%.

Cú vấp: "không nhánh luôn nhanh" là sai

Niềm tin của tôi khi vào bài là "code không nhánh luôn nhanh hơn". Đo ra nó chỉ đúng khi nhánh khó đoán. Với nhánh dễ đoán, bản có nhánh nhanh hơn vì hai lý do. Thứ nhất, một nhánh đoán đúng 99% gần như miễn phí — CPU đã chạy sẵn đúng hướng, không tốn gì. Thứ hai, và quan trọng hơn: nhánh cho phép bỏ qua việc. Khi điều kiện sai, bản có nhánh không cộng gì cả, chỉ nhảy qua. Bản csel thì luôn tính s + a[i] rồi mới quyết định giữ hay bỏ — nó trả tiền cho phép cộng ngay cả khi kết quả bị vứt đi. Ở nhánh dễ đoán, cái "phí công tính cả hai vế" đó lớn hơn cái phạt đoán sai hiếm hoi mà nó tránh được.

Điểm hòa nằm đâu đó quanh 95-99% đoán đúng. Dưới ngưỡng đó, phạt đoán sai tích lũy đủ lớn để csel đáng giá; trên ngưỡng đó, nhánh gần như miễn phí và khả năng bỏ qua việc khiến nó thắng. Đây là lý do compiler không biến mọi if thành csel: nó dùng heuristic (và PGO nếu có hồ sơ) để đoán nhánh nào khó, chỉ dùng branchless ở đó. Ép branchless mọi nơi — bằng mẹo bit tự chế hay cưỡng bức compiler — làm chậm chính những nhánh dễ đoán mà lẽ ra nên để nguyên.

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

Điều đầu tiên: đừng viết mẹo branchless bằng tay theo phản xạ. "Code không nhánh nhanh hơn" là một câu thần chú nửa đúng. Nếu nhánh của bạn dễ đoán — điều kiện gần như luôn đúng hoặc luôn sai, hay theo một mẫu đều — thì if bình thường vừa nhanh hơn vừa dễ đọc. Compiler đã cân nhắc và thường chọn đúng; can thiệp tay chỉ hại. Chỉ khi bạn biết (bằng đo) rằng nhánh khó đoán mới nên nghĩ tới branchless.

Điều thứ hai: độ đoán được là thuộc tính của dữ liệu, không phải của code. Cùng một if(a[i] >= 128) là dễ đoán trên dữ liệu đã sắp xếp (một chuỗi dài false rồi một chuỗi dài true) và khó đoán trên dữ liệu ngẫu nhiên. Đây là lý do nổi tiếng vì sao "sắp xếp mảng trước khi lọc" đôi khi làm vòng lặp nhanh hơn nhiều lần — không phải vì sắp xếp rẻ, mà vì nó biến nhánh khó đoán thành dễ đoán. Trước khi tối ưu một nhánh, hỏi: dữ liệu thật của tôi làm nó dễ hay khó đoán?

Và cái đánh đổi này không chỉ nằm ở tầng C/CPU — nó lặp lại nguyên vẹn ở mọi tầng có "đoán so với làm chắc". JIT của JVM biên dịch nhánh theo hồ sơ chạy: nếu một nhánh gần như luôn đi một hướng, nó tối ưu mạnh cho hướng đó (và deoptimize nếu đoán sai về sau) — đúng logic "nhánh dễ đoán thì để nguyên là tốt". Nhưng chỗ rõ nhất là CSDL: bộ tối ưu chọn giữa quét tuần tự và dùng index chính bằng độ chọn lọc (selectivity) — nếu điều kiện lọc ra rất ít dòng (như nhánh 99% "bỏ qua"), index thắng; nếu lọc ra gần nửa bảng (như nhánh 50/50), quét thẳng cả bảng lại rẻ hơn vì nhảy index lung tung còn tệ hơn. Cùng một hình dạng đánh đổi: làm-có-điều-kiện thắng khi kết quả lệch hẳn về một phía (đoán được / chọn lọc cao), còn làm-đều-tay thắng khi kết quả chia đôi khó lường — và bạn phải biết phân bố dữ liệu thật mới chọn đúng, ở CPU cũng như ở CSDL.

Muốn tự thấy thì viết một vòng cộng a[i] khi a[i] >= 128 trên một mảng lớn, và chạy hai lần: một lần mảng ngẫu nhiên, một lần mảng đã sắp xếp (cùng dữ liệu, chỉ khác thứ tự). Bọc bằng clock_gettime. Bạn sẽ thấy bản mảng đã sắp xếp nhanh hơn nhiều lần — dù thuật toán y hệt — vì nhánh trên dữ liệu sắp xếp dễ đoán hơn hẳn. Đó là phạt đoán sai hiện ra bằng đồng hồ. Rồi thử ép branchless (s += (a[i]>=128) * a[i];) và đo lại cả hai: bản branchless gần như không đổi giữa hai thứ tự — phẳng — và bạn thấy tận mắt vì sao nó cứu mảng ngẫu nhiên nhưng không giúp (thậm chí hơi hại) mảng đã sắp xếp.