Giải thuật 03/09/2026 8 phút

switch luôn O(1) nhanh hơn if-else? Tôi đo và niềm tin đó sai ở ba chỗ khác nhau

Ai cũng nghe switch được compiler biến thành bảng nhảy O(1) nên nhanh hơn if-else. Tôi đo và thấy nó sai nhiều mặt: switch chỉ thành bảng khi case dày, bảng nhảy có chi phí nhảy gián tiếp khó đoán nên thua if-else khi case nóng ở đầu, và 12 phép so sánh gần bằng 1 khi nhánh đoán được.

Giải thuật 03/09/2026 7 phút

Đọc lệch lề crash hoặc chậm gấp đôi? Trên ARM đời nay tôi đo ra gần như miễn phí

Ai cũng bảo dữ liệu lệch lề thì crash hoặc chậm thảm họa. Tôi đo trên ARM AArch64 và thấy gần như vô hại: đọc lệch bằng căn lề, vắt cache line chỉ chậm 1%, atomic lệch không crash. Bất ngờ ngược: padding struct để 'căn lề cho nhanh' lại làm CHẬM vì mảng phình gây nhiều cache miss.

Giải thuật 03/09/2026 7 phút

Thêm một hàm không bao giờ chạy, benchmark của tôi đổi 4% — thủ phạm là căn lề mã

Căn lề mã cho tốc độ ổn định, cứ tăng -falign-loops là tốt? Tôi đo và thấy tác động nhỏ (~2%) và thất thường trên ARM. Quan trọng hơn: căn lề mã chính là nguồn nhiễu benchmark khét tiếng — giữ hot loop y hệt, chỉ chèn một hàm chết để dịch địa chỉ, thời gian đổi ~4%, còn lớn hơn cả việc cố ý chỉnh căn lề.

Giải thuật 03/09/2026 8 phút

restrict để vector hóa? gcc -O3 tự lo mà không cần — và khai sai một chữ là kết quả sai lặng lẽ

Không có restrict thì không vector hóa được, luôn chậm? Tôi đo và thấy gcc -O3 tự chèn kiểm tra alias lúc chạy rồi vector hóa cả khi thiếu restrict. restrict chỉ giúp vòng nhỏ gọi nhiều (~20%), không giúp vòng lớn. Và nó là lời hứa compiler tin tuyệt đối — khai sai khi con trỏ thật sự trùng thì kết quả sai, không một lời cảnh báo.

Giải thuật 03/09/2026 7 phút

Đảo byte tôi tự viết bằng shift/mask nhanh ngang builtin — vì gcc nhận ra tôi đang làm gì

Phải dùng builtin/intrinsics mới nhanh, viết C tay luôn chậm? Tôi đo và thấy đúng nửa: builtin thắng rõ ở phép C không có cách viết tự nhiên (popcount nhanh 1,8 lần), nhưng nhiều phép compiler tự nhận mẫu — đảo byte viết tay bằng shift/mask cũng ra đúng một lệnh rev, bằng builtin. Đo trước khi cho rằng viết tay là chậm.

Giải thuật 03/09/2026 8 phút

likely/unlikely: mách đúng cho compiler được ~0, mách sai mất 10% — một canh bạc lỗ

Thêm likely/unlikely tưởng tăng tốc nhánh rõ rệt. Tôi đo và thấy một canh bạc bất đối xứng xấu: mách đúng thì lợi gần như bằng không (bộ dự đoán nhánh động của CPU đã lo hướng), nhưng mách sai làm chậm 10%. Cái nó đổi chỉ là bố cục mã, không phải hướng đoán — nên hãy để PGO lo, đừng rắc theo cảm tính.