Heapsort nghe như hoàn hảo: O(n log n) bảo đảm và tại chỗ — hơn quicksort có ca xấu, hơn merge tốn bộ nhớ. Nhưng đo ra nó chậm nhất trong ba (1,43× tới 2,37× quicksort), và tỉ số tăng theo n vì sift-down nhảy khắp mảng phá cache. Vai trò thật của nó là lưới an toàn, không phải tốc độ. Tôi đo.
Ai cũng bảo inline để khỏi tốn chi phí gọi hàm. Tôi đo và thấy bỏ một lệnh call chỉ tiết kiệm 0,15 ns — call trên CPU hiện đại gần như miễn phí. Lợi thật là tối ưu xuyên biên: gọi g(x,0) hằng số, inline giúp gấp hằng và khử nhánh chết, nhanh 1,8 lần. Nhưng inline hàm lớn vào 24 chỗ làm mã phình gấp đôi.
Đổi tiền bằng cách chộp đồng xu lớn nhất luôn đúng với hệ {1,5,10,25}. Nhưng đo hệ khác thì nó sai 25-40% số tiền — hệ {1,7,10}, số 14: tham lam 5 xu, tối ưu 2 xu. Tham lam nhanh hơn quy hoạch động 100 triệu lần cho một truy vấn (2,1 ns so 228 ms), nhưng nhanh mà sai thì vô dụng. Tôi đo.
PGO tối ưu theo hồ sơ chạy thật thay vì đoán tĩnh. Tôi đoán hồ sơ sai (thu trên dữ liệu lệch ngược) sẽ làm nó chậm hơn cả -O2 vì tối ưu nhầm nhánh — đo ra không hề: với một nhánh trong vòng nóng, PGO vẫn nhanh y hệt, vì cái nó thắng là bố cục mã, không phải hướng nhánh mà CPU đã tự đoán.
Compiler luôn kéo mọi thứ bất biến ra khỏi vòng? Đúng với số học thuần, và nó còn hoist cả strlen khi thân chỉ đọc. Nhưng một phép ghi vào chuỗi trong thân chặn đứng nó: for(i<strlen(s)) sửa chuỗi thành O(n²) thật — n=32.000 chậm 990 lần. Biên giới của tối ưu là aliasing.
Ai cũng bảo tránh virtual cho nhanh. Tôi đo và thấy nó phụ thuộc một thứ lời khuyên đó bỏ qua: khi một điểm gọi chỉ thấy một kiểu (monomorphic) thì gọi ảo gần bằng gọi trực tiếp — 0,722 ns; chỉ khi nhiều kiểu trộn khó đoán (megamorphic) mới chậm 6,6 lần. Cái đắt là đích nhảy khó đoán, không phải từ khóa virtual.