Dijkstra là thuật toán tham lam nhưng đúng — nhờ đúng một điều kiện: trọng số không âm. Cho nó một cạnh âm (2→1 = -3), nó chốt dist[1]=4 sai trong khi đáp án thật là 2, mà không một cảnh báo. Và cấu trúc bên trong quyết định quy mô: heap nhanh hơn mảng 36 lần trên đồ thị thưa. Tôi đo.
Bloom filter trả lời 'phần tử này có trong tập không' một cách không chính xác: dương tính giả 0,81% ở 10 bit/phần tử, 14,7% ở 4 bit, giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0. Đổi lại nó không bao giờ báo âm tính giả và chỉ tốn 1,2 MB thay vì 25 MB. Có số hàm băm tối ưu. Tôi đo.
Cấp rồi giải 3 triệu object nhỏ tốn 47 ms, còn arena chỉ 6,2 ms (nhanh 8 lần). 1 triệu object 16 byte ngốn 38,6 MB thay vì 16 MB vì metadata và căn lề. Và free sạch rồi RSS vẫn đứng 168 MB. malloc trong vòng nóng là kẻ giết hiệu năng ẩn — gom vào arena chữa cả ba. Tôi đo.
Thêm vào mảng động là O(1) khấu hao, nhưng đo đường cong từng thao tác thấy gai O(n): lần cấp phát cuối sao chép 2,1 triệu phần tử mất 392µs, gấp 400.000 lần một lần thêm thường. Và tăng dung lượng mỗi lần +1 để 'tiết kiệm bộ nhớ' hóa ra là O(n²), chậm 17.851 lần. Tôi đo cả đường cong.
Quicksort pivot cố định gặp mảng đã sắp xếp làm 2,05 tỉ so sánh (901 ms); pivot ngẫu nhiên chỉ 1,3 triệu (1,1 ms) — ít hơn 1524 lần. Và skip list cân bằng bằng tung đồng xu, đạt ~log n mà không một phép xoay. Gieo ngẫu nhiên đúng chỗ là tăng an toàn, không phải thêm rủi ro. 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.