Chắc bạn từng nghe câu chuyện này: có một câu hỏi trên Stack Overflow đại loại "tại sao xử lý mảng đã sắp xếp lại nhanh hơn mảng chưa sắp?", và nó thành huyền thoại. Cùng một đoạn code, cùng số phép tính, chỉ khác thứ tự các phần tử, mà bản đã sắp xếp chạy nhanh gấp mấy lần. Nghe như đùa.
Thủ phạm là dự đoán nhánh. Hình dung CPU như một người bẻ ghi đường ray: đoàn tàu (dòng lệnh) lao tới một ngã rẽ là câu lệnh if, nhưng người bẻ ghi chưa biết tàu cần đi hướng nào — kết quả điều kiện có khi còn đang chờ dữ liệu từ bộ nhớ. Anh ta không thể để tàu dừng lại đợi, nên phải đoán và bẻ ghi trước. Đoán trúng thì tàu chạy êm. Đoán trượt thì phải phanh gấp, lùi lại, bẻ ghi lại — mất cả chục nhịp.
Với một mảng đã sắp xếp, hướng rẽ cực dễ đoán: một loạt dài toàn rẽ trái, rồi một loạt dài toàn rẽ phải. Người bẻ ghi quen tay, gần như không bao giờ trượt. Còn mảng ngẫu nhiên thì trái phải loạn xạ, cứ tầm một nửa số lần là đoán sai. Tôi tò mò muốn xem con số thật ra sao, nên dựng lại thí nghiệm trong container gcc:13 (g++ 13.4) trên một máy ARM64 — và câu chuyện năm 2026 hóa ra có một khúc ngoặt mà cái huyền thoại kia không kể.
Thí nghiệm
Bài toán quen thuộc: cho một mảng 32.768 số trong khoảng 0–255, cộng dồn những số từ 128 trở lên.
for (int x : data)
if (x >= 128) sum += x;
Chạy vòng này thật nhiều lần trên hai phiên bản của cùng bộ dữ liệu — một bản để nguyên ngẫu nhiên, một bản đã sort — rồi so thời gian mỗi phần tử. Vì cả hai bản duyệt mảng y hệt nhau theo thứ tự, khác biệt (nếu có) không thể đổ cho cache; nó chỉ có thể đến từ cái if.
Con số
Tôi chạy ba biến thể, và chúng kể một câu chuyện thú vị hơn tôi tưởng:
| Cách biên dịch | Mảng ngẫu nhiên | Mảng sắp xếp |
|---|---|---|
Giữ nhánh thật (-fno-if-conversion -fno-tree-vectorize) |
0,776 ns | 0,355 ns → nhanh 2,2× |
-O2 mặc định |
0,130 ns | 0,129 ns → bằng nhau |
Tự viết không nhánh (sum += x & -(x>=128)) |
0,277 ns | 0,278 ns → bằng nhau |
Hàng đầu tiên là huyền thoại được xác nhận. Khi tôi ép g++ giữ lại một nhánh thật sự, mảng sắp xếp nhanh hơn đúng 2,2 lần. Toàn bộ khoảng cách đó là tiền phạt cho những lần người bẻ ghi đoán trượt trên mảng ngẫu nhiên.
Nhưng để ý cái điều kiện tôi phải thêm vào để có được hàng đó: -fno-if-conversion -fno-tree-vectorize. Tôi phải tắt bớt tối ưu thì hiệu ứng mới hiện ra. Bởi vì — và đây là khúc ngoặt — ở mức -O2 bình thường mà ai cũng dùng, g++ nhìn cái if kia rồi lặng lẽ dẹp luôn cái nhánh. Nó thay bằng một lệnh chọn-có-điều-kiện (trên ARM là csel: chọn x hoặc 0 tùy điều kiện rồi cộng), hoặc vector hóa cả vòng lặp thành SIMD có mặt nạ. Không còn nhánh nào để mà đoán trượt, nên thứ tự dữ liệu chẳng còn nghĩa lý gì: 0,130 với 0,129, coi như bằng nhau.
Cái huyền thoại "mảng sắp xếp nhanh hơn" ra đời ở thời trình biên dịch còn để nguyên nhánh. G++ bây giờ tự tay xóa nó đi. Nếu hôm nay bạn viết lại đúng benchmark đó để "chứng minh" điều mình đọc được, rất có thể bạn đang đo một cái nhánh mà compiler đã bỏ từ đời nào — và bối rối không hiểu vì sao chẳng thấy khác biệt.
Hàng thứ ba đóng đinh câu chuyện. Bản không-nhánh tôi tự viết bằng mặt nạ số học chạy 0,277 ns bất kể thứ tự, và nhanh hơn cả bản-có-nhánh-đã-sắp-xếp. Vì nó không có nhánh, nó không bao giờ đoán sai — chính là thứ mà g++ đã tự làm giúp bạn ở hàng thứ hai (bản mặc định còn nhanh hơn nữa nhờ được vector hóa).
Cái bẫy khi đo
Chỗ này đáng dừng lại một chút, vì nó là lý do người ta dựng lại thí nghiệm mà cứ thất bại. Nếu bạn chỉ gõ g++ -O2, đo, rồi kết luận "à, dự đoán nhánh chả ảnh hưởng gì" — bạn sai, nhưng sai vì compiler chứ không phải vì phần cứng. Hiệu ứng có thật; chỉ là bạn không còn nhánh nào để đo. Muốn nhìn thấy nó, phải ép giữ nhánh, hoặc mở assembly (-S, hay dán lên Godbolt) ra xem còn lệnh rẽ nhánh b.lt/cbz nào không, hay đã thành csel cả rồi. Đây cũng là bài học chung: trước khi kết luận về phần cứng, hãy chắc chắn compiler chưa viết lại code sau lưng bạn.
Ngoài đời thì sao
Vài điều rút ra, không chỉ cho C++.
Với một điều kiện khó đoán nằm trong vòng lặp nóng — kiểu phân bố 50/50, dữ liệu ngẫu nhiên thật — mà compiler không tự dẹp được, viết lại theo kiểu không nhánh thường thắng: dùng mặt nạ số học, min/max, hay bảng tra. Đây không phải chuyện riêng của C. JIT của Java cũng làm đúng trò cmov/csel này khi biên dịch nóng; các engine cột trong cơ sở dữ liệu (DuckDB, ClickHouse) cố tình viết toán tử lọc theo kiểu không nhánh để quét hàng triệu dòng mà không dính phạt đoán sai; và đó cũng là một lý do người ta thích xử lý theo lô, vector hóa thay vì if từng phần tử.
Nhưng đừng đi dẹp mọi cái if. Nhánh dễ đoán — kiểm tra lỗi hiếm khi xảy ra, điều kiện dừng vòng lặp — gần như miễn phí, vì người bẻ ghi đoán trúng gần như mọi lần. Branchless chỉ đáng khi cái nhánh vừa nóng, vừa thật sự khó đoán, vừa không được compiler xử lý sẵn. Và lời khuyên thực dụng nhất: xem compiler đã làm gì trước đã. Rất nhiều lần bạn chẳng phải làm gì cả, còn tối ưu tay lại ra chậm hơn bản nó tự sinh.
Điều tôi thích ở thí nghiệm nhỏ này là nó phá vỡ một hình dung sai rất phổ biến: rằng CPU là cái máy đếm phép tính, làm bao nhiêu việc thì tốn bấy nhiêu thời gian. Không phải. Nó là cái máy đoán, và nó đoán về chính code của bạn. Cùng một dữ liệu, cùng số phép tính, chỉ cần sắp xếp lại là nhanh gấp đôi — hoặc chẳng đổi gì, tùy vào việc compiler có kịp xóa cái nhánh đi hay chưa.
Tự thử
Nếu muốn tận mắt: tạo một mảng vài chục nghìn số ngẫu nhiên 0–255, viết vòng lọc if (x >= 128) sum += x, rồi đo trên bản ngẫu nhiên so với bản đã sort. Ở -O2 mặc định bạn sẽ thấy chúng bằng nhau đến phát bực — đó là lúc nên mở assembly ra và bắt gặp g++ đã thay if bằng csel. Thêm -fno-if-conversion -fno-tree-vectorize để buộc giữ nhánh rồi đo lại, khoảng cách gấp đôi sẽ hiện ra. Cuối cùng thử bản mặt nạ sum += x & -(x >= 128): nhanh, và trơ với thứ tự dữ liệu. Ba lần đo đó nói với bạn nhiều hơn bất kỳ bài viết nào — kể cả bài này.
