Ở bài trước về tối ưu theo hồ sơ, trình biên dịch dùng số liệu đo được để sắp nhánh nóng ra đường đi thẳng. __builtin_expect là phiên bản thủ công của việc đó: bạn tự nói cho trình biên dịch nhánh nào hay chạy, thay vì để nó đo hay đoán. Macro likely()/unlikely() trong nhân Linux chính là nó. Bài này biên dịch thật, đọc assembly để thấy gợi ý đổi cái gì, và đo xem nó giúp được bao nhiêu — rồi phát hiện gợi ý "đúng" của tôi chẳng làm gì cả, còn cái thật sự đổi thời gian là một gợi ý sai.
Gợi ý nhánh đổi cái gì
__builtin_expect(biểu_thức, giá_trị_kỳ_vọng) trả về chính biểu_thức, nhưng kèm một lời nhắn cho trình biên dịch rằng kết quả thường bằng giá_trị_kỳ_vọng. Hai macro quen thuộc: LIKELY(x) là __builtin_expect(!!(x), 1), UNLIKELY(x) là __builtin_expect(!!(x), 0).
Điều quan trọng cần tách bạch ngay: gợi ý này chỉ đổi bố cục mã, không đụng tới bộ dự đoán nhánh của phần cứng. Bộ dự đoán phần cứng là một cơ chế động, tự học lịch sử mỗi nhánh lúc chạy, và nó rất giỏi. Cái mà __builtin_expect điều khiển là tĩnh: nhánh nào được đặt làm đường đi thẳng (fall-through) ngay sau lệnh so sánh, và nhánh nào bị đẩy ra một khối xa hơn. Đặt nhánh nóng thành đường thẳng giúp mã nóng nằm gọn, ít nhảy, thân thiện với cache lệnh. Đó là toàn bộ những gì gợi ý làm — và cũng là giới hạn của nó.
Đo: gợi ý đúng không nhanh thêm, gợi ý sai thì chậm hẳn
Tôi viết một vòng lặp kiểu kiểm-lỗi trên 8 triệu phần tử: nếu a[i] < 0 thì gọi một hàm rare() đắt tiền, ngược lại chỉ cộng dồn. Ba bản: không gợi ý (plain), gợi ý nhánh âm là hiếm (UNLIKELY — đúng, vì tôi cho ít số âm), và gợi ý nó là thường (LIKELY — sai). Chạy với dữ liệu 3% số âm (nhánh hiếm, dễ dự đoán), ghim một lõi, lấy nhỏ nhất trong 9 lần:
| Bản | Thời gian (3% âm) |
|---|---|
plain (không hint) |
4,21 ms |
UNLIKELY (hint đúng) |
4,22 ms |
LIKELY (hint sai) |
7,80 ms |
Ba con số này kể một câu chuyện tôi không ngờ. Gợi ý đúng (UNLIKELY) cho 4,22 ms — đúng bằng bản không gợi ý (4,21). Còn gợi ý sai (LIKELY) nhảy lên 7,80 ms, chậm gần gấp đôi.
Một lần tôi đo hớ: gợi ý đúng của tôi là thừa
Tôi vào bài với niềm tin gọn: thêm UNLIKELY vào nhánh lỗi hiếm sẽ giúp vòng lặp nhanh hơn, vì trình biên dịch sẽ biết mà tối ưu cho đường thường. Đo ra 4,22 ms — không nhanh hơn bản plain một mảy may. Gợi ý "tối ưu" của tôi hoàn toàn thừa.
Đọc assembly thì rõ vì sao. Trình biên dịch vốn đã có heuristic tĩnh mặc định: một phép so a[i] < 0 mà nhánh true đi gọi một hàm thì gcc đã đoán sẵn là hiếm (mẫu "kiểm tra rồi xử lý lỗi" quá phổ biến để nó không nhận ra). Nên bản plain đã đặt đường cộng-dồn thường làm fall-through, và khối gọi rare() bị đẩy ra xa — y hệt cái UNLIKELY yêu cầu. Tôi ra lệnh một việc trình biên dịch đã tự làm.
Cái thật sự đổi thời gian lại nằm ở hướng ngược: gợi ý sai. Khi tôi đánh dấu nhánh hiếm là LIKELY, trình biên dịch tin lời tôi và đặt đường đắt (gọi rare()) làm fall-through, đẩy đường cộng-dồn thường ra thành khối xa. Đọc assembly thấy rõ cấu trúc bị đảo: bản UNLIKELY dùng một lệnh tbz cho case thường đi thẳng tiếp vòng; bản LIKELY đảo lại, thêm một nhánh nhảy vòng cho chính cái case đang chạy 97% thời gian. Kết quả: mỗi vòng lặp ở case thường phải nhảy thêm, và thời gian gần gấp đôi (7,80 so với 4,21 ms).
Và có một phép đo thứ hai đóng đinh giới hạn của gợi ý: khi tôi đổi dữ liệu sang 50% số âm — nhánh giờ ngẫu nhiên, không dự đoán được — cả ba bản chạy quanh 33 ms, khác nhau trong khoảng nhiễu. Ở đây gợi ý nào cũng vô dụng, vì cái tốn kém là dự đoán sai của phần cứng (một nhánh 50/50 khiến bộ dự đoán động đoán trật nửa số lần), mà gợi ý tĩnh không thể sửa — nó chỉ đổi bố cục, không đổi khả năng đoán của CPU.
Bài học đo lường: một gợi ý tối ưu là một lời hứa với trình biên dịch — hứa đúng thì thừa (nó đã biết), hứa sai thì bị phạt. Tôi suýt viết bài kết luận "thêm UNLIKELY giúp nhanh hơn", trong khi phép đo nói ngược: nó không giúp gì, và sức mạnh thật của gợi ý lên thời gian chạy chủ yếu là tiêu cực khi ta đoán sai. "Nhanh hơn" là vô nghĩa nếu chưa hỏi "so với bản không hint" — mà so ra thì bằng nhau.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng rắc likely/unlikely khắp nơi mong nhanh hơn. Với những nhánh có mẫu rõ ràng — kiểm lỗi, kiểm null, nhánh xử lý trường hợp biên — trình biên dịch gần như luôn đã đoán đúng theo heuristic tĩnh, nên gợi ý của bạn chỉ là tiếng ồn trong mã. Tệ hơn, mỗi gợi ý là một chỗ có thể đoán sai: nếu bạn tưởng một nhánh hiếm nhưng thực tế nó thường xảy ra (dữ liệu production khác dữ liệu bạn hình dung), gợi ý sẽ làm chậm đúng đường nóng — như bài PGO đã cho thấy, một hồ sơ/giả định lệch còn tệ hơn không có.
Hệ quả thứ hai: gợi ý nhánh không cứu được một nhánh không dự đoán được. Nếu vòng nóng của bạn rẽ theo dữ liệu ngẫu nhiên (50/50), vấn đề là bộ dự đoán phần cứng đoán trật, và không lời gợi ý tĩnh nào chữa được — nó chỉ sắp lại thứ tự khối mã, không dạy CPU đoán giỏi hơn. Cách chữa thật cho nhánh khó đoán là bỏ nhánh đi: dùng mã không nhánh (branchless) như phép chọn theo bit, cmov, hay tính cả hai vế rồi trộn — đó mới là thứ tấn công đúng gốc rễ, còn __builtin_expect thì không.
Hệ quả thứ ba, và là cái đáng mang theo: để đo thay cho đoán. Cách bền vững để sắp bố cục nhánh nóng không phải rải likely bằng trực giác, mà là để PGO làm — nó đo phân bố nhánh thật rồi xếp bố cục chính xác, không lệ thuộc phán đoán của bạn. Hãy để dành __builtin_expect cho vài chỗ thật sự nóng mà bạn chắc chắn về hướng (và lý tưởng là đã kiểm bằng assembly hoặc perf). Con số mang theo: gợi ý nhánh chỉ đổi bố cục mã tĩnh, không đổi bộ dự đoán động; một gợi ý đúng thường thừa vì trình biên dịch đã đoán vậy (4,22 so 4,21 ms), còn một gợi ý sai đặt đường đắt làm fall-through và làm chậm gần gấp đôi (7,80 ms) — nên đừng đoán, hãy đo. Gợi ý là một lời hứa; và như restrict hay volatile, một lời hứa sai không báo lỗi, nó chỉ âm thầm phạt bạn.
Thử ba mươi giây
Lấy một vòng lặp có một nhánh kiểm-lỗi hiếm, biên dịch với gcc -O2 -S và đọc assembly quanh nhánh đó: bạn sẽ thấy khối xử lý lỗi thường đã bị đẩy ra sau thân hàm (một nhánh nhảy tiến, rồi khối lỗi nằm cuối) — trình biên dịch đã tự đoán nó hiếm, chẳng cần bạn nhắc. Giờ thêm __builtin_expect(dieu_kien_loi, 1) (cố tình sai — bảo nó rằng lỗi là thường) và biên dịch lại: bạn sẽ thấy bố cục đảo, khối lỗi leo lên làm đường đi thẳng. Đó là toàn bộ những gì gợi ý làm — đổi cái nào nằm thẳng — và là lý do một gợi ý sai làm hại đúng con đường bạn muốn nhanh.
