LRU cài đúng đạt O(1) nhờ băm + danh sách liên kết đôi (nhanh 323 lần bản O(n) ở cache 10.000). Nhưng cache to gấp 25 lần chỉ thêm 37 điểm hit, và một lượt quét tuần tự lớn hơn cache khiến LRU trúng 0% — đuổi ngẫu nhiên lại được 41,6%. Hiệu quả cache phụ thuộc hoàn toàn vào mẫu truy cập. Tôi đo.
Mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần (0,21 µs so 3.869 µs) — nhưng phải dựng mảng trước, tốn 358 ms cho văn bản 2 triệu ký tự. Cho một lần tìm, KMP thắng đậm; suffix array chỉ có lãi sau ~93 truy vấn trên cùng văn bản. 'Nhanh nhất' vô nghĩa nếu chưa hỏi tìm bao nhiêu lần. Tôi đo.
Chia việc cho 10 lõi tưởng nhanh gấp 10, nhưng đo ra: việc song song thuần nhất chỉ đạt 7,38x, thêm 10% việc tuần tự tụt còn 4,53x (khớp luật Amdahl), và việc nghẽn băng thông bộ nhớ chỉ 3,28x vì mọi lõi tranh một bus. Phần tuần tự nhỏ bé mới là thứ đặt trần. Tôi đo.
Kẹp đồng hồ hai đầu vòng lặp rồi đọc số nghe đơn giản, nhưng con số ấy nói dối bốn kiểu: bỏ sink thì compiler xóa vòng và đo ra 0 ns cho việc chưa chạy; lần đầu chậm 27% vì cache lạnh; trên VM một lần vọt 2,7 lần median; và clock_gettime tốn 16 ns nên đo việc vài ns ra rác. Cách đo cho đáng tin.
Ai cũng được dạy lưu biểu thức chung vào biến tạm cho khỏi tính lại. Tôi đo và thấy compiler tự làm: bản viết lặp và bản lưu tạm sinh mã giống hệt. Nhưng một phép ghi qua con trỏ có thể trùng lại chặn đứng nó, buộc tính lại — và restrict khôi phục, nhanh 1,34 lần ở phép chia. Aliasing mới là thứ quyết định.
Tưởng CPU luôn chạy theo thứ tự mình viết, còn reorder bộ nhớ chỉ là lý thuyết trong sách? Tôi đo litmus store-buffer trên ARM: reorder xảy ra thật (11 ca trong 60 triệu vòng), rào dmb ish dập được về 0. Nhưng nó hiếm tới ~1 trên 5,5 triệu vòng — nên code sai vẫn qua sạch mọi test rồi nổ ở production.