Cần thêm phần tử ở đầu danh sách? Nhiều người bảo dùng vector cũng được. Tôi đo thử — và vector push_front hóa ra là O(n): mỗi lần thêm gấp đôi thời gian khi số phần tử gấp đôi (1552 → 3375 ns), vì nó phải dịch cả mảng. Một ring buffer chỉ lùi một chỉ số, O(1) (~3 ns), nhanh hơn 1136 lần ở N=100k. Còn std::deque thì push được hai đầu O(1), duyệt chỉ chậm hơn vector 19%.
Muốn một cấu trúc có thứ tự với tra cứu O(log n) thì bắt buộc phải cây cân bằng với logic xoay rắc rối? Đo ra: skip list đạt O(log n) kỳ vọng chỉ bằng tung đồng xu — chèn không xoay, code đơn giản hơn nhiều, chậm hơn std::map chỉ 8–12%. Nhưng nó không phải luôn thắng: cây đỏ-đen tối ưu kỹ vẫn nhanh hơn ở đơn luồng, và O(log n) của skip list chỉ là kỳ vọng.
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.
Gói nhiều trường vào một từ chỉ tiết kiệm bộ nhớ mà làm chậm CPU vì shift/mask? Đo ra: một bản ghi 4 trường nhỏ gói vào một uint32 nhỏ hơn 4 lần (16 → 4 byte), và shift/mask khi đọc gần như miễn phí — duyệt khối lớn còn nhanh hơn 1,1 lần nhờ cache, mảng nóng thì hòa. Nhưng lợi ích chính là bộ nhớ, không phải tốc độ: throughput chỉ nhanh 1,1 lần chứ không tỉ lệ với mức nén.
Serialize chỉ là copy dữ liệu ra byte nên nhanh? Đo ra: binary memcpy đúng là gần như chỉ sao chép (0,48 ns/bản ghi, ~38 GB/s), nhưng ghi ra text từng trường chậm hơn 52 lần và parse chậm hơn 29 lần vì phải format/parse mỗi số. Còn binary memcpy nhanh thì lại không di động: endianness, padding, con trỏ đều vô nghĩa qua máy khác.
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.