O(log n) đánh bại O(n) — nên ai cũng mặc định dùng nhị phân. Nhưng đo ra ở n=64 tìm tuyến tính nhanh hơn (14,5 so 20,2 ns): nhị phân ít bước nhưng mỗi bước là một nhánh 50/50 mà CPU hay đoán sai, còn tuyến tính quét tuần tự CPU đoán trúng suốt. Big-O đếm số bước, bỏ qua giá mỗi bước. Tôi đo bằng C.
Ai cũng biết compiler tính sẵn 2+3 thành 5. Tôi đo xem nó đi xa tới đâu: cùng một hàm ba phép nhân, khi đầu vào là hằng 100 thì gcc gấp toàn bộ thành một literal 64-bit (5 lệnh, 0 phép nhân, 0 ns); khi đầu vào từ volatile thì phải tính đủ (22 lệnh, 3 phép nhân, 0,99 ns). Ranh giới nằm ở một câu hỏi.
Tổng kết 45 phần đo thật hệ điều hành trong container Linux: một thang độ trễ trải ~36.000 lần (từ 0,25ns đọc RAM tuần tự tới 9µs đánh thức luồng), và bốn mẫu trực giác-sai lặp đi lặp lại — chi phí per-thao-tác, cái đắt là phải ngủ, cấp phát lười, đoán được hơn nhanh thô.
Hai luồng, mỗi luồng tăng bộ đếm riêng — độc lập hoàn toàn, phải chạy song song? Tôi đo thử: nếu hai bộ đếm nằm cùng một cache line, chúng chậm hơn 3,8–4,9 lần vì dòng cache ping-pong giữa hai lõi (false sharing). Tách sang cache line riêng (padding) là khắc phục. Không chia sẻ một byte dữ liệu nào vẫn bị phạt vì chung dòng.
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.
Tưởng seq_cst đắt hơn relaxed nhiều nên nên hạ xuống cho nhanh? Tôi đọc assembly và bấm giờ trên ARMv8: ba mức sinh lệnh khác nhau nhưng thời gian chênh ~1% vì ARM có sẵn ldar/stlr/ldaddal, không cần rào dmb nặng. Chọn ordering cho đúng ngữ nghĩa, không phải tốc độ — seq_cst mặc định gần như miễn phí.