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?

Hình dung một đoàn tàu tới chỗ bẻ ghi, và người điều khiển phải chọn đường trước khi biết chắc, dựa trên thói quen. Đoán đúng thì tàu chạy thẳng, không mất giây nào. Đoán sai thì tệ hơn nhiều so với "đứng lại chọn lại": tàu đã lỡ chạy một quãng sai, phải lùi toàn bộ về chỗ bẻ ghi rồi mới đi hướng đúng — cả công đi quãng sai đổ sông đổ biển. CPU dự đoán nhánh y hệt: đoán sai không phải "chọn nhầm rồi sửa nhẹ", mà là xả sạch cả một pipeline lệnh đã trót chạy. Phần này tôi đo thẳng cái giá của một lần đoán sai. Câu hỏi cụ thể: khi CPU đoán trật 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á đó.

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 (quãng tàu chạy sai).
  • 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.

Hai niềm tin đối nghịch, cùng sai

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". Con số bác ngay: 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 nếu nghĩ ngược — "đoán sai thì chỉ chậm đi một chút, chuyện nhỏ" — thì cũng 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, y như quãng tàu chạy sai phải lùi lại.

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

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

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

Cái đường chuông này không nằm yên trong C — nó chi phối hiệu năng ở tận tầng cao, và biết nó giúp giải thích một hiện tượng nổi tiếng. Câu hỏi Stack Overflow được vote nhiều nhất mọi thời về hiệu năng ("Why is processing a sorted array faster than an unsorted array?") chính là bài này: cùng code Java, mảng đã sắp làm nhánh trở nên dễ đoán (chạy vào một chuỗi dài toàn true rồi toàn false) nên nhanh gấp mấy lần mảng ngẫu nhiên — JIT của JVM cũng dự đoán nhánh y như CPU. Ở tầng cao hơn, đây là lý do sâu vì sao xử lý dữ liệu đã sắp xếp hay phân nhóm thường nhanh bất ngờ, và vì sao các engine cột (ClickHouse) thích lưu dữ liệu theo thứ tự để lọc dự đoán được. Còn phía database, bộ tối ưu dùng selectivity (một điều kiện lọc ra bao nhiêu phần trăm hàng) để chọn kế hoạch — một biến thể "tính đoán-được" ở quy mô truy vấn. Nguyên tắc chung: cái giá của "rẽ theo điều kiện" phụ thuộc phân bố dữ liệu, không phải bản thân dòng code.

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