Xây một heap từ n phần tử — push từng cái cũng như make_heap chứ gì? Tôi đo thử: n lần push là O(n log n), còn heapify bottom-up là O(n); với dữ liệu xấu nhất heapify nhanh hơn 6,3 lần. Và bất ngờ: heap không cần cây con trỏ — nó chỉ là một mảng liền mạch.
Stack và queue đều O(1) push/pop dù cài bằng mảng hay linked list — chọn cách nào cũng vậy? Tôi đo thử: stack bằng mảng 0,3ns/thao tác, bằng linked list 4,0ns — chậm 13 lần, vì linked list trả malloc+free (5,5ns) mỗi thao tác. Cùng O(1), khác hằng số cả chục lần.
O(log n) < O(n), nên tìm nhị phân luôn thắng tuyến tính? Tôi đo thử: với mảng nhỏ, tuyến tính NHANH HƠN — điểm giao ở khoảng N≈32; dưới đó quét tuần tự thắng nhờ cache và không branch misprediction. Big-O là hành vi tiệm cận (N lớn); N nhỏ thì hằng số và phần cứng mới quyết định.
Bố cục struct chỉ là cách tổ chức, không đổi tốc độ? Tôi đo thử: duyệt một trường trên 15 triệu phần tử, SoA nhanh hơn AoS 3,6 lần vì cache line không bị lãng phí. Nhưng truy cập ngẫu nhiên mọi trường thì AoS lại nhanh gấp đôi. Không có bố cục nào luôn thắng — chọn theo mẫu truy cập.
Hai luồng, mỗi luồng tăng bộ đếm riêng — độc lập hoàn toàn, phải chạy song song? Tôi đo thử: nếu hai bộ đếm nằm cùng một cache line, chúng chậm hơn 3,8–4,9 lần vì dòng cache ping-pong giữa hai lõi (false sharing). Tách sang cache line riêng (padding) là khắc phục. Không chia sẻ một byte dữ liệu nào vẫn bị phạt vì chung dòng.
Thứ tự khai báo trường trong struct chỉ là chuyện phong cách? Tôi đo thử: đảo thứ tự cùng ba trường làm struct từ 24 byte xuống 16 byte — phí 33% RAM chỉ vì đệm căn lề, và duyệt mảng bản 16B nhanh hơn 1,35 lần vì nhét gấp đôi số struct mỗi cache line. Sắp trường lớn tới nhỏ.