Chèn từng phần tử để dựng heap 'phải là' O(n log n). Nhưng đo dữ liệu ngẫu nhiên thì nó phẳng 2,3 thao tác/phần tử — cũng O(n). O(n log n) chỉ hiện ở ca xấu (chèn giảm dần): thao tác leo 16→22 theo log n. Heapify thì O(n) bất kể đầu vào. Và heap không sắp xếp — nó chỉ cho min rẻ. Tôi đo.
Thay nhân bằng dịch bit luôn nhanh hơn rõ, chia hằng thành magic luôn thắng? Tôi đo và cả hai đều tùy: trên ARM hiện đại nhân đã rẻ ngang cộng nên dịch chỉ nhanh hơn tí, còn chia-hằng chỉ thắng ở thông lượng — trong chuỗi phụ thuộc nó còn chậm hơn cả phép chia thật. Compiler tự làm hết, đừng tự tay.
Ai cũng khuyên viết branchless (csel/cmov) cho nhanh. Tôi đo cả một đường cong theo độ đoán được và thấy nó chỉ đúng một nửa: nhánh 50/50 khó đoán thì không-nhánh nhanh 5,3 lần, nhưng nhánh 99% dễ đoán thì có-nhánh lại nhanh hơn — vì nhánh dễ đoán gần như miễn phí và còn được bỏ qua việc.
Ai cũng bảo dữ liệu lệch lề thì crash hoặc chậm thảm họa. Tôi đo trên ARM AArch64 và thấy gần như vô hại: đọc lệch bằng căn lề, vắt cache line chỉ chậm 1%, atomic lệch không crash. Bất ngờ ngược: padding struct để 'căn lề cho nhanh' lại làm CHẬM vì mảng phình gây nhiều cache miss.
Căn lề mã cho tốc độ ổn định, cứ tăng -falign-loops là tốt? Tôi đo và thấy tác động nhỏ (~2%) và thất thường trên ARM. Quan trọng hơn: căn lề mã chính là nguồn nhiễu benchmark khét tiếng — giữ hot loop y hệt, chỉ chèn một hàm chết để dịch địa chỉ, thời gian đổi ~4%, còn lớn hơn cả việc cố ý chỉnh căn lề.
Khai struct local là chắc chắn tốn ô nhớ stack, malloc thì tốn heap? Tôi đo và thấy compiler làm biến mất cả hai khi chứng minh được đối tượng không thoát khỏi hàm: struct thành thanh ghi, malloc/free bốc hơi, tốc độ y hệt. Cái đắt không phải việc khai hay cấp phát — mà là lấy địa chỉ (&) khiến nó thoát ra ngoài.