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.
Sách bảo linked list chèn O(1) thắng mảng O(n), nên tải chèn nhiều thì chọn linked list. Nhưng đo ra list chậm hơn vector 31 lần ngay ở chèn — vì O(1) splice bị nuốt bởi O(n) đi tìm vị trí đầy cache-miss; và duyệt chậm 395 lần. Big-O một thao tác bỏ qua chi phí tìm và locality. Tôi đo bằng C.
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.
Hash map được hứa O(1), nên tưởng mọi lần tra/chèn nhanh như nhau. Đo latency từng lần chèn: trung vị 42 ns, nhưng có một lần 9,8 mili giây khi bảng rehash cả 2 triệu phần tử — chậm hơn 233.000 lần. Tra cũng chậm dần theo load factor, và hàm băm xấu đẩy probe lên 5707. O(1) là trung bình khấu hao. 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.
Cây tìm kiếm nhị phân được dạy là O(log n). Nhưng đổ khóa đã sắp (id tăng, timestamp — rất thường gặp) vào thì nó thoái hóa thành xâu: chiều cao 40000 thay vì 34, tra 32672 ns thay vì 51 ns, chậm 640 lần đúng bằng quét tuyến tính. Và một mảng nhị phân đẹp cache cũng không nhanh hơn cây cân bằng. Tôi đo.