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ễ.
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ờ.
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ệ.
Tưởng duyệt mảng và danh sách liên kết tốn như nhau vì cùng O(n)? Tôi đo thử: duyệt 20 triệu phần tử, mảng 0,24ns/phần tử còn linked list 104ns — chậm 442 lần, vì mỗi con trỏ next là một cache miss còn mảng thì được prefetch. Big-O đếm số thao tác, không đếm giá mỗi thao tác.
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.
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 đủ.