Hai vòng lặp làm đúng cùng số phép load và cộng, cùng O(n) — đếm phép thì tưởng cùng tốc độ. Nhưng đo ra duyệt ngẫu nhiên chậm 452 lần duyệt tuần tự trên mảng 256 MB. Chi phí thật không nằm ở phép cộng mà ở truy cập bộ nhớ: cache và prefetch. Big-O mù hoàn toàn trước điều đó. Tôi đo bằng C.
O(n log n) tốt hơn O(n²) — nên tôi định dùng merge sort cho mọi trường hợp. Nhưng đo ra ở n=64 insertion sort nhanh hơn (292 so 375 ns) vì hằng số ẩn. Big-O là hình dạng đường cong khi n tiến vô cùng, không phải tốc độ ở n cụ thể; phải đo cả đường cong, không đo một điểm. Tôi đo bằng C.
Chọn hàm băm nhanh nhất (identity) tưởng tối ưu, nhưng với khóa có mẫu nó dồn cả triệu khóa vào 256 bucket (max 3907). SHA rải hoàn hảo nhưng tính 184 ns, gấp 240 lần hàm trộn bit cho cùng phân bố. Hàm băm tốt không phải nhanh nhất hay mạnh nhất, mà là cân bằng đúng cho dữ liệu của bạn. Tôi đo.
Đếm số so sánh thì B-tree thua tìm nhị phân (bậc 64 làm 100 so với 20). Đo thời gian thì thắng (70 ns so với 98 ns) vì chỉ 4 lần nạp bộ nhớ thay vì 22 — số so sánh nói dối, đồng hồ nói thật. Và có bậc B tối ưu quanh cỡ dòng cache, không phải càng lớn càng nhanh. Tôi đo.
Không thuật toán sắp xếp đơn nào thắng mọi mặt, nên std::sort của C++ ghép quicksort + insertion + heapsort, mỗi cái che điểm yếu cái kia. Ngưỡng insertion chỉ đáng ~14% chứ không nhiều; và cùng mảng đã sắp giết quicksort pivot cuối (331 ms, đệ quy 50000 tầng) thì introsort xong trong 0,27 ms. 'Tốt nhất' là một kiến trúc, không phải một cái tên. Tôi đo.
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.