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%.
Đo sáu vòng lặp bằng gcc và clang: clang nhanh hơn 2-4 lần ở vài vòng, hòa ở số khác. Tôi định kết 'clang nhanh hơn' và giải thích nó thắng popcount nhờ lệnh cnt. Đọc mã máy ra ngược hẳn — gcc mới dùng cnt mà vẫn chậm. Bài cuối sê-ri, và cái bẫy tôi rơi vào cả hai chân.
fork một tiến trình 512MB chỉ tốn 28µs — nó không sao chép dữ liệu, chỉ chép bảng trang (nhanh hơn nghìn lần). Nhưng chi phí sao chép không mất, nó bị hoãn: ghi vào 64MB heap chung sau fork tốn 20,2ms với 16.419 COW fault, chậm ~200 lần ghi thường. Khi cái gì 'gần như miễn phí', hỏi tiếp chi phí đi đâu.
Kiểu số nào cũng 'một phép tính' nên tốc độ như nhau? Đo trên host ARM: cùng một phép trên mảng, khi vector hóa thì int8 nhanh gấp 10 lần int64 — thanh ghi NEON 128-bit gói 16 số int8 nhưng chỉ 2 số int64 mỗi lệnh. Dữ liệu lớn (memory-bound) kiểu hẹp cũng thắng ~9 lần vì ít byte. Nhưng ở chế độ vô hướng mọi kiểu int lại y hệt, và kiểu nhỏ dễ tràn — nên quy tắc là hẹp nhất đủ dùng.
Sắp xếp nào cũng như nhau, cứ std::sort? Tôi đo thử: sắp tại chỗ tốn ~0 bộ nhớ phụ nhưng không ổn định; sắp cấp thêm (merge) tốn 80 MB buffer cho 20 triệu int nhưng giữ thứ tự phần tử bằng nhau. Và quicksort pivot xấu trên dữ liệu đã sắp xếp thành O(n²), chậm 2428 lần.
Ai cũng dặn phải căn lề dữ liệu kẻo truy cập bộ nhớ chậm. Nhưng đo trên ARM, đọc lệch — kể cả cắt ngang dòng cache — nhanh y hệt căn lề. Chỉ có đúng một chỗ khiến nó lết: khi 8 byte vắt qua ranh giới trang, chậm gần 30 lần. Cái x86 bắt bạn sợ với cái thật sự nguy hiểm hóa ra không phải một.