std::unordered_map dùng chaining nên chaining là cách nhanh nhất xử lý va chạm? Đo ra: open addressing (dò trong một mảng liền) tra cứu nhanh hơn ở hệ số tải vừa (10,4 vs 15,1 ns ở tải 0,5) và gọn hơn 3,4 lần bộ nhớ. Nhưng ở tải 0,9, dò dồn cụm trung bình 5,45 lần khiến open chậm hẳn và chaining vượt lên — một điểm giao rõ ràng.
Page cache giữ file trong RAM để đọc lại tức thì (Cached 5,5GB, đọc 256MB ở ~36GB/s, 0 lỗi trang nặng). Nhưng trong container tôi không tạo nổi lần đọc 'nguội': overlayfs không có đĩa chậm thật bên dưới, FUSE thì bỏ qua page cache khách nên luôn chậm. Đo I/O trong container là đo tầng ảo hóa, không phải đĩa.
Immutable chậm vì cứ phải copy mỗi lần đổi? Đo ra: đúng một nửa — cập nhật một trường nhiều lần thì immutable naive chậm hơn mutable 101 lần (142,7 vs 1,4 ns) vì mỗi lần đổi phải copy cả đối tượng. Nhưng chia sẻ để đọc thì ngược lại: immutable chia sẻ tự do không tốn gì, còn mutable phải copy phòng thủ mỗi lần trao đi — chậm hơn immutable 97 lần.
Đọc lại bit của một int như float bằng ép kiểu con trỏ nghe vô hại. Tôi đo: cùng hàm trả về 1 với -O2 nhưng 1073741824 với -fno-strict-aliasing — một cờ đổi kết quả là bằng chứng chắc chắn của hành vi không xác định. Strict aliasing cho tốc độ ~9%, nhưng type-punning ép kiểu vi phạm nó; memcpy mới đúng, mà vẫn nhanh.
Hash map O(1) nên luôn nhanh nhất cho tra cứu? Đo ra: với khóa chuỗi (băm phải đọc cả 24 ký tự ~10ns), quét tuyến tính một mảng nhỏ thắng hash map tới n≈16 — vì hằng số nhỏ hơn nhiều: cache liền, so sánh thoát sớm, không băm, không con trỏ. Big-O là tiệm cận n→vô cùng; ở n nhỏ chính hằng số quyết định, và điểm giao tùy giá của khóa.
mmap trông như miễn phí vì không có syscall read — phép đo đầu cho nó nhanh gấp 8 lần. Nhưng getrusage tố cáo nó mới chạm 2176 trang chứ chưa đọc hết file. Cho cả hai cùng cộng 256MB: read() nhanh gấp 5 lần mmap (87 so với 430 ms). Benchmark chỉ có nghĩa khi hai bên làm đúng cùng một việc.