Phần 4 cho thấy tải cao giết hash table. Nhưng tôi đo tiếp: ngay ở CÙNG tải 0,70, đổi hàm băm tốt sang xấu làm probe trung bình nhảy từ 2,17 lên 358,9 — tra cứu chậm 23 lần. Băm hằng số thì thoái hóa hoàn toàn về O(n). Tải thấp là điều kiện cần, không đủ.
Tưởng mỗi push_back copy cả mảng nên vector chậm, hoặc grow-by-1 tiết kiệm RAM nên tốt? Tôi đo thử: nhân đôi amortize xuống 2,57ns/push (O(1)) xây 20 triệu phần tử, còn grow-by-1 là O(N²) — chỉ 50 nghìn phần tử đã 1,25 tỷ copy, 3213ns/push, nếu 20 triệu thì mất 7 giờ.
Ai cũng nói hash table là O(1). Tôi đo thử: O(1) chỉ đúng khi hệ số tải thấp — tải 0,25 tốn 1,17 probe (3,2ns), nhưng đẩy tải lên 0,99 thì probe trung bình nổ lên 43 và tra cứu chậm 10 lần. O(1) là trung bình có điều kiện, không phải bảo đảm vô điều kiện.
Tưởng giới hạn CPU của cgroup giống nice, chỉ cắn khi máy bận? Tôi đo: --cpus=0.5 vẫn chậm 2,2 lần và --cpus=0.25 chậm 6,5 lần dù 9/10 lõi ngồi không. Nó là hạn ngạch tuyệt đối, không phải ưu tiên — và ở hạn ngạch nhỏ còn tệ hơn tỉ lệ.
Chia là chia, tốn như nhau? Tôi đo và thấy cùng dấu / cho hai chi phí khác hẳn: chia cho hằng số biến thành nhân magic + dịch (vector hóa được, gần như miễn phí), còn chia cho biến là udiv đắt 2,7 lần. Nhưng trong chuỗi phụ thuộc, cái mẹo magic lại không thắng — lợi ở thông lượng, không ở độ trễ.
O(1) < O(log n), nên hash luôn hơn cây? Tôi đo thử: tra cứu điểm hash nhanh hơn cây đỏ-đen 32 lần (16ns vs 518ns). Nhưng range query — tìm mọi phần tử >= x theo thứ tự — cây làm trong 7,8µs còn hash phải sort lại toàn bộ, 54,2ms. 'Cái nào nhanh hơn' là câu hỏi sai; chọn theo loại truy vấn.