Phần trước cho thấy nhánh dễ đoán chạy nhanh, nhánh khó đoán chạy chậm — nhưng chậm bao nhiêu, và vì sao? Phần này đo thẳng cái giá của một lần đoán sai (misprediction penalty). Câu hỏi cụ thể: khi CPU đoán sai một nhánh, nó mất bao nhiêu chu kỳ? Tôi quét một nhánh qua mọi tỉ lệ đúng/sai và đo trong container gcc:13 trên host ARM, và đường cong kết quả — một hình chuông đỉnh ở giữa — cho phép tách ra chính xác cái giá của mỗi lần CPU đoán trật.
Một lần đoán sai là một lần xả pipeline
Khi CPU đoán một nhánh và đoán sai, nó không chỉ "chọn nhầm" — nó đã lỡ chạy một loạt lệnh theo hướng sai, đưa chúng vào sâu trong đường ống. Để sửa, CPU phải:
- Xả (flush) toàn bộ những lệnh sai đang nằm trong pipeline — công đã làm bị vứt đi.
- Quay lại lấy đúng nhánh và nạp lại pipeline từ đầu.
Vì pipeline hiện đại sâu cả chục tầng, nạp lại từ đầu tốn cỡ chục chu kỳ — một khoảng thời gian đủ để CPU đáng lẽ chạy xong nhiều lệnh hữu ích. Đó là misprediction penalty.
Cách đo nó gián tiếp mà chính xác: lấy một nhánh có tỉ lệ "được lấy" là p, rồi quét p từ 0% đến 100%. Ở p=0 hoặc p=100, nhánh luôn cho cùng một kết quả → CPU đoán đúng gần như luôn → không có phạt. Ở p=50, đúng/sai xen kẽ 50/50 → không thể đoán → CPU đoán sai khoảng một nửa số lần → phạt tối đa. Vẽ thời gian theo p sẽ ra một hình chuông; chênh lệch giữa đỉnh (50%) và đáy (0/100%), chia cho tỉ lệ đoán sai, chính là phạt mỗi lần đoán sai.
Đo: hình chuông đỉnh 50%, phạt ~12 chu kỳ
Tôi giữ một nhánh thật (buộc trình biên dịch không chuyển thành lệnh không nhánh, như đã học ở phần 1) và quét p:
Nhánh thật (-fno-if-conversion -fno-tree-vectorize), 2 triệu phần tử, g++ -O2, ARM:
p (nhánh được lấy) | if (nhánh thật) | branchless (mask)
-------------------|-----------------|------------------
0% | 0,450 ns | 0,30 ns
10% | 0,848 ns | 0,31 ns
25% | 1,423 ns | 0,31 ns
50% | 2,382 ns | 0,31 ns <- ĐỈNH (tệ nhất)
75% | 1,350 ns | 0,31 ns
90% | 0,714 ns | 0,31 ns
100% | 0,237 ns | 0,30 ns
-> đường cong ns theo p là hình CHUÔNG, đỉnh ở 50%
PHẠT mỗi lần đoán sai: (2,382 - 0,450) / 0,5 ≈ 3,86 ns ≈ ~12 chu kỳ (giả sử ~3 GHz)
Nhìn cột if: thời gian vẽ thành một hình chuông hoàn hảo. Ở hai đầu (p=0 và p=100), nhánh đoán được nên chỉ tốn 0,24–0,45 ns — gần như miễn phí. Càng tiến về 50%, càng khó đoán, thời gian càng leo, đạt đỉnh 2,382 ns ở p=50 — chậm hơn đầu đường cong tới ~5–10 lần. Cùng một nhánh, cùng một phép tính; chỉ tỉ lệ đúng/sai của dữ liệu thay đổi, mà thời gian biến thiên cả chục lần. (Hai đầu hơi lệch: p=100 nhanh hơn p=0 một chút vì luồng lệnh khác nhau, nhưng cả hai đều đoán được và đều rẻ.)
Từ đường cong, tách được cái giá cốt lõi: ở p=50, tỉ lệ đoán sai khoảng 0,5 (một nửa số nhánh); thời gian thêm so với đáy là 2,382 − 0,450 = 1,932 ns cho nửa số lần đoán sai, tức ~3,86 ns mỗi lần đoán sai. Nếu CPU chạy ~3 GHz (một chu kỳ ~0,33 ns), đó là ~12 chu kỳ — đúng cỡ lý thuyết cho một lần xả pipeline (thường 10–20 chu kỳ). (Tần số CPU thật trên ARM ảo hóa không chắc chắn, nên con số chu kỳ là ước lượng — nhưng bậc độ lớn khớp.)
Nhìn cột branchless: bản viết không nhánh (dùng mask thay if) phẳng lì ~0,30 ns bất kể p. Vì nó không có nhánh nào để đoán, nên không bao giờ đoán sai — thời gian không phụ thuộc dữ liệu chút nào. Đây là bằng chứng cuối: toàn bộ cái chuông kia là chi phí của việc đoán nhánh, không phải của phép tính.
Một lần tôi đo hớ: "nhánh nào cũng tốn như nhau" và "đoán sai chỉ chậm chút"
Tôi vào đo với một mô hình đơn giản: "một cái if là một cái if, tốn một lượng cố định". Đo phá tan: cái giá của một nhánh không cố định — nó phụ thuộc dữ liệu chạy qua nó. Nhánh dễ đoán (p=0/100) gần như miễn phí (0,24–0,45 ns), còn nhánh 50/50 tốn 2,38 ns — chênh 5–10 lần, vẽ thành một hình chuông đỉnh ở giữa. Cùng một dòng code if, hai workload khác nhau về tính đoán-được, cho hai chi phí khác hẳn. "Nhánh nào cũng như nhau" bỏ qua chuyện CPU là một cỗ máy đoán tương lai, và độ đoán-được của dữ liệu quyết định giá.
Nhưng đo cũng phá một niềm tin ngược: "đoán sai thì chỉ chậm đi một chút, chuyện nhỏ". Sai — mỗi lần đoán sai xả cả pipeline, đo được ~3,86 ns ≈ ~12 chu kỳ, đủ để một nhánh khó đoán trong vòng lặp nóng chậm gấp mấy lần. Với hàng triệu lần lặp, những chục-chu-kỳ đó cộng thành khác biệt lớn — đó là lý do một nhánh 50/50 trên đường nóng là một trong những "chi phí ẩn" đắt nhất mà Big-O không hé lộ. Một mispredict không phải "chậm chút" — nó là toàn bộ công của một pipeline bị ném đi.
Bài học đo lường: phạt đoán sai nhánh là ~chục chu kỳ (đo được ~3,86 ns ≈ ~12 chu kỳ ở 3GHz, đúng cỡ lý thuyết 10-20). Quét tỉ lệ nhánh được lấy p cho đường cong hình CHUÔNG: đoán được (p=0/100) ~0,24-0,45 ns gần miễn phí, 50/50 (p=50) đỉnh 2,38 ns — chênh 5-10x. Giá của một nhánh KHÔNG cố định, phụ thuộc tính đoán-được của DỮ LIỆU. Branchless (mask) phẳng ~0,30 ns vì không có nhánh để đoán sai. Nếu tôi tin "nhánh nào cũng như nhau" tôi bỏ qua chi phí phụ thuộc dữ liệu; nếu tin "đoán sai chỉ chậm chút" tôi coi thường một khoản chục-chu-kỳ mỗi lần.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: trên đường nóng, để ý nhánh nào KHÓ ĐOÁN — đó mới là nhánh đắt. Một if kiểm tra lỗi hiếm (gần như luôn không xảy ra, p≈0) hay điều kiện vòng lặp (gần như luôn tiếp tục, p≈100) thì gần miễn phí — CPU đoán đúng luôn. Cái đắt là nhánh mà kết quả thật sự khó lường (dữ liệu ngẫu nhiên, phân bố ~50/50). Đừng tối ưu mọi if; tìm đúng nhánh khó đoán trong vòng lặp nóng.
Hệ quả thứ hai: với nhánh khó đoán trong vòng nóng, cân nhắc bỏ nhánh. Viết không nhánh bằng mask/số học, std::min/max, cmov, hoặc bảng tra — như bản branchless phẳng lì trong đo — loại bỏ hoàn toàn phạt mispredict. Nhưng nhớ hai điều: (1) trình biên dịch thường đã làm điều này cho bạn ở -O2 (xem phần 1), nên kiểm assembly trước; (2) branchless không phải luôn thắng — nếu nhánh dễ đoán, giữ if thường nhanh hơn vì CPU đoán đúng và bỏ qua công của nhánh không chạy.
Hệ quả thứ ba là tinh thần đo lường: chi phí một thao tác có thể phụ thuộc DỮ LIỆU, không chỉ mã. Con số mang theo: phạt đoán sai nhánh ~12 chu kỳ (~3,86 ns); nhánh đoán được gần miễn phí, nhánh 50/50 đỉnh chuông ~2,4 ns; giá một nhánh phụ thuộc tính đoán-được của dữ liệu, không cố định; branchless loại bỏ phạt (phẳng ~0,30 ns). Cùng một dòng if có thể rẻ hay đắt tùy dữ liệu chạy qua — đo với đúng dữ liệu của bạn mới biết nhánh nào đang đốt chu kỳ.
Thử ba mươi giây
Tạo một mảng cờ boolean với tỉ lệ true là p, và một vòng lặp if (flag[i]) s += data[i], biên dịch với -fno-if-conversion -fno-tree-vectorize để giữ nhánh thật. Bấm giờ với p = 0, 10, 25, 50, 75, 90, 100 — bạn sẽ thấy thời gian vẽ thành một hình chuông, thấp ở hai đầu (nhánh đoán được) và cao vọt ở giữa (p=50, không đoán nổi). Lấy chênh lệch giữa đỉnh và đáy chia cho tỉ lệ đoán sai (~0,5 ở p=50), bạn ước lượng được phạt mỗi lần đoán sai — trên máy tôi khoảng 12 chu kỳ, đúng cỡ một lần xả pipeline. Cuối cùng, viết bản không nhánh bằng mask và đo lại: đường của nó phẳng bất kể p, vì không có nhánh nào để đoán. Ba mươi giây đó cho bạn thấy điều mà "một cái if tốn một lượng cố định" giấu đi: CPU đoán nhánh của bạn, và cái giá của nó không nằm trong dòng code — nó nằm trong việc dữ liệu của bạn có làm nhánh đó đoán được hay không.
