Sê-ri mới, cùng một cam kết: đo, đừng đoán — lần này xoáy vào phần cứng CPU. Và không ví dụ nào nổi tiếng hơn câu hỏi kinh điển: "vì sao xử lý một mảng đã sắp xếp lại nhanh hơn mảng ngẫu nhiên, dù làm y hệt một việc?". Câu trả lời sách vở là dự đoán nhánh (branch prediction): CPU chạy lệnh theo đường ống, gặp một if nó phải đoán đi nhánh nào; mảng sắp xếp làm nhánh dễ đoán nên nhanh. Tôi đo lại ví dụ này trong container gcc:13 trên host ARM — và phát hiện câu chuyện năm 2026 phức tạp hơn sách: hiệu ứng có thật, nhưng trình biên dịch hiện đại thường xóa nó đi trước khi bạn kịp thấy.
CPU đoán nhánh, và cái giá khi đoán sai
CPU không chạy từng lệnh xong mới sang lệnh sau — nó xếp nhiều lệnh gối lên nhau trong một đường ống (pipeline). Vấn đề: khi gặp một if, CPU chưa biết kết quả điều kiện (có thể đang chờ dữ liệu từ bộ nhớ), nhưng không thể đứng chờ — nên nó đoán nhánh nào sẽ đi và chạy tiếp theo dự đoán đó.
- Đoán đúng: pipeline chạy mượt, không mất gì.
- Đoán sai: mọi lệnh đã chạy theo hướng sai phải bị xả (flush), và CPU làm lại từ nhánh đúng — phạt cỡ chục chu kỳ.
Ví dụ kinh điển: lọc mảng bằng if (x >= 128) s += x.
- Mảng sắp xếp: các số nhỏ nằm đầu, số lớn nằm cuối — nên điều kiện là một chuỗi dài toàn sai rồi một chuỗi dài toàn đúng. CPU đoán đúng gần như luôn (chỉ sai một lần ở chỗ chuyển) → nhanh.
- Mảng ngẫu nhiên: đúng/sai xen kẽ ~50/50 → CPU đoán sai khoảng một nửa số lần → xả pipeline liên tục → chậm.
Điểm quan trọng: đây không phải chuyện cache — cùng một mảng, cùng cách truy cập tuần tự, chỉ khác thứ tự giá trị. Nếu thời gian chênh nhau, thủ phạm là dự đoán nhánh.
Đo: hiệu ứng có thật, nhưng compiler xóa nó
Tôi lọc cùng 32.768 số (0–255) nhiều lần, so mảng ngẫu nhiên với mảng sắp xếp:
Cùng 32768 số (0..255), lọc if(x>=128) s+=x, g++ -O2, host ARM AArch64:
A. NHÁNH THẬT (buộc bằng -fno-if-conversion -fno-tree-vectorize):
mảng NGẪU NHIÊN (đoán sai ~50%) : 0,776 ns/phần tử
mảng SẮP XẾP (nhánh dễ đoán) : 0,355 ns/phần tử -> sắp xếp nhanh 2,2 lần
B. MẶC ĐỊNH -O2:
mảng NGẪU NHIÊN : 0,130 ns/phần tử
mảng SẮP XẾP : 0,129 ns/phần tử -> gần như BẰNG NHAU (hiệu ứng biến mất)
C. BRANCHLESS (mask tay: m = -(x>=128); s += x & m):
ngẫu nhiên : 0,277 ns | sắp xếp : 0,278 ns -> không đổi theo thứ tự
Nhìn A — khi có một nhánh thật: tôi phải buộc trình biên dịch giữ nhánh (tắt cả if-conversion lẫn vector hóa) mới thấy hiệu ứng kinh điển. Lúc đó mảng ngẫu nhiên mất 0,776 ns còn mảng sắp xếp 0,355 ns — sắp xếp nhanh hơn 2,2 lần. Toàn bộ khác biệt là dự đoán nhánh: ~50% đoán sai trên mảng ngẫu nhiên, mỗi lần xả pipeline. Cùng dữ liệu, cùng phép tính, chỉ khác thứ tự — đúng như lý thuyết.
Nhìn B — chỗ khiến tôi ngớ người: ở -O2 mặc định, mảng ngẫu nhiên (0,130) và sắp xếp (0,129) gần như bằng nhau, hiệu ứng biến mất hoàn toàn. Vì trình biên dịch hiện đại không để lại một nhánh: nó chuyển if (x>=128) s+=x thành mã không nhánh — hoặc một lệnh conditional-select (trên ARM là csel: "chọn x hay 0 tùy điều kiện, cộng vào"), hoặc vector hóa thành SIMD có mask. Không còn nhánh nào để đoán sai → thứ tự dữ liệu không còn ảnh hưởng. Ví dụ "mảng sắp xếp nhanh hơn" nổi tiếng từ thời trình biên dịch còn để lại nhánh; g++ ngày nay xóa nó đi.
Nhìn C — code không nhánh viết tay (dùng mask thay if): 0,277 ns bất kể thứ tự, và nhanh hơn cả bản nhánh-sắp-xếp (0,355). Vì nó không có nhánh nên không bao giờ đoán sai — chính là điều trình biên dịch đã tự làm cho bạn ở phần B. (Bản mặc định B nhanh hơn nữa vì được vector hóa SIMD.)
Một lần tôi đo hớ: "thời gian chỉ phụ thuộc dữ liệu" và "sắp xếp để thấy hiệu ứng sorted-array"
Tôi vào đo với một trực giác nền tảng: "cùng dữ liệu, cùng số phép tính thì cùng thời gian — máy chỉ làm nhiều hay ít việc". Đo phá tan: cùng 32.768 số, cùng phép lọc, chỉ khác thứ tự sắp xếp mà bản có nhánh thật chênh 2,2 lần. CPU không phải cỗ máy đếm phép tính — nó đoán tương lai, và khi đoán sai thì trả giá bằng cả một pipeline bị xả. Thời gian phụ thuộc cả vào việc dữ liệu có làm nhánh dễ đoán hay không, chứ không chỉ vào số phép tính.
Nhưng đo cũng phá một niềm tin ngược — cái mà chính người thuộc bài "sorted array" dễ mắc: "vậy cứ sắp xếp mảng trước là thấy/được hiệu ứng tăng tốc". Sai theo hai hướng. Thứ nhất, ở -O2 mặc định trên máy hiện đại, hiệu ứng biến mất — g++ tự bỏ nhánh (csel/SIMD) nên sắp xếp và ngẫu nhiên bằng nhau; nếu bạn "chứng minh" sorted-array nhanh hơn mà quên điều này, benchmark của bạn đang đo một nhánh mà trình biên dịch thật ra đã xóa. Thứ hai, ngay cả khi có nhánh thật, sắp xếp không phải cách thắng đúng: nó tốn O(n log n) để sắp, và code không nhánh (mask, 0,277 ns) còn nhanh hơn cả bản nhánh-đã-sắp-xếp mà chẳng cần sắp gì. Cách xử lý nhánh khó đoán không phải là sắp xếp dữ liệu, mà là bỏ nhánh đi.
Bài học đo lường: dự đoán nhánh là chi phí THẬT — với một nhánh khó đoán, thứ tự dữ liệu quyết định tốc độ (đo: nhánh thật, mảng ngẫu nhiên 0,776 vs sắp xếp 0,355 ns = 2,2x, do đoán sai ~50% xả pipeline; KHÔNG phải cache). NHƯNG g++ -O2 hiện đại thường TỰ bỏ nhánh (conditional-select csel / vector hóa SIMD có mask) nên hiệu ứng 'sorted array nhanh hơn' BIẾN MẤT ở mặc định (0,130 ≈ 0,129); và code branchless viết tay (mask) 0,277 ns nhanh hơn cả bản nhánh-sắp-xếp. Cách thắng nhánh khó đoán là viết KHÔNG nhánh, không phải sắp xếp. Nếu tôi tin "chỉ phụ thuộc dữ liệu" tôi bỏ qua pipeline; nếu tin "sắp xếp để thấy hiệu ứng" tôi đo một nhánh compiler đã xóa và chọn sai cách tối ưu.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: trên đường nóng với nhánh khó đoán, cân nhắc viết không nhánh (branchless). Nếu một điều kiện trong vòng lặp nóng khó đoán (phân bố ~50/50, dữ liệu ngẫu nhiên) và trình biên dịch không tự bỏ được nó, một phiên bản dùng mask/số học (s += x & -(cond)), std::min/max, hoặc bảng tra có thể nhanh hơn nhiều vì không bao giờ đoán sai. Nhưng đừng branchless mọi nhánh — nhánh dễ đoán (kiểm tra lỗi hiếm, vòng lặp) gần như miễn phí nhờ CPU đoán đúng.
Hệ quả thứ hai: kiểm xem trình biên dịch đã làm gì trước khi tối ưu tay. Rất nhiều if đơn giản được g++/clang tự chuyển thành csel/SIMD ở -O2 — bạn không cần làm gì, và tối ưu tay có khi chậm hơn bản compiler sinh. Xem assembly (-S, hay Godbolt) để biết còn nhánh thật hay không; chỉ can thiệp khi thấy một nhánh khó đoán thực sự còn đó. Và nhớ: hiệu ứng phụ thuộc kiến trúc — x86 và ARM có bộ dự đoán khác nhau.
Hệ quả thứ ba là tinh thần đo lường: CPU là cỗ máy đoán, không phải máy đếm — và trình biên dịch đứng giữa bạn và phần cứng. Con số mang theo: nhánh khó đoán chênh ~2x theo thứ tự dữ liệu (đoán sai xả pipeline), nhưng g++ -O2 thường bỏ nhánh (csel/SIMD) làm hiệu ứng biến mất, và branchless nhanh hơn cả sắp-xếp. Đo với nhánh thật để thấy dự đoán nhánh; đo mặc định để thấy compiler làm gì. Ví dụ kinh điển vẫn đúng về nguyên lý, nhưng thực tế 2026 phải đo mới biết nhánh còn tồn tại hay đã bị xóa.
Thử ba mươi giây
Tạo một mảng vài chục nghìn số ngẫu nhiên 0–255 và lọc if (x >= 128) s += x nhiều lần, bấm giờ hai bản: mảng ngẫu nhiên và mảng đã sort. Ở -O2 mặc định, bạn có thể ngạc nhiên thấy chúng bằng nhau — vì trình biên dịch đã biến if thành lệnh không nhánh. Giờ biên dịch lại với -fno-if-conversion -fno-tree-vectorize để buộc giữ nhánh thật, đo lại: lần này mảng sắp xếp nhanh hơn rõ (khoảng hai lần trên máy tôi), vì mảng ngẫu nhiên làm CPU đoán sai liên tục. Cuối cùng, viết bản không nhánh bằng mask (s += x & -(x >= 128)) và đo: nó nhanh, và không đổi theo thứ tự — bằng chứng rằng cái đắt là bản thân nhánh khó đoán, không phải dữ liệu. Ba mươi giây đó cho bạn thấy điều mà "cùng dữ liệu thì cùng thời gian" giấu đi: CPU đoán nhánh của bạn, đoán sai thì phạt, và trình biên dịch hiện đại thường đã âm thầm xóa nhánh giùm bạn — nên muốn hiểu hiệu năng thật, phải đo cả phần cứng lẫn thứ trình biên dịch sinh ra.
