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 vào đo 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ỳ. 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. Đây chính là chỗ đánh đổi mà tôi không cân nhắc đủ.
Tôi đo trong container gcc:13 (ARM AArch64): 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%.
Đo hớ: "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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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?
Hệ quả thứ ba là bài học đo lường quen thuộc của sê-ri: một lời khuyên tối ưu không kèm điều kiện thường là một nửa sự thật. "Branchless nhanh hơn" đúng ở một nửa đường cong và sai ở nửa kia; chỉ đo đường cong (nhiều độ đoán được) mới thấy chỗ lật. Con số mang theo: csel/cmov (không nhánh) bỏ phạt đoán sai (~15-20 chu kỳ) nhưng luôn tính cả hai vế và không được bỏ qua việc — nên nó thắng khi nhánh khó đoán (50/50: nhanh 5,3 lần, 2,512 so 0,474 ns) và THUA khi nhánh dễ đoán (99%: có nhánh 0,312 so csel 0,481), điểm hòa quanh 95-99% đoán đúng. Đừng ép branchless mọi nơi; đo độ đoán được của nhánh trên dữ liệu thật rồi hãy quyết.
Thử ba mươi giây
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.
