free() xong là bộ nhớ trả về hệ điều hành ngay? Tôi đo thử: sau khi free 90% của 4 triệu ô nhỏ, RSS vẫn giữ 655 MB trong khi dữ liệu sống chỉ 55 MB — gấp 12 lần. Tệ hơn, những hố nhỏ rời rạc không lấp được request lớn hơn: cấp lại các ô 512B làm heap phình thêm 563 MB, còn cùng cỡ thì tái dùng đúng hố, +0 MB.
Giữ nhiều bản sao của cùng một chuỗi thì tốn gì đâu? Tôi đo thử: 8 triệu tham chiếu tới chỉ 1000 giá trị duy nhất, nếu mỗi nơi giữ một bản riêng tốn 732 MB, còn interning (một bản duy nhất + chỉ số 4 byte) chỉ 30,8 MB — ít hơn 24 lần. Chưa hết: interning còn biến so sánh bằng thành so một số nguyên O(1), nhanh hơn 6,4 lần so từng ký tự.
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.