-ffast-math nghe như nút tăng tốc miễn phí cho code toán. Tôi đo: cùng tổng 20 triệu float, -O3 cho 1999531776 trong 0,571 ns/phần tử, còn -ffast-math cho 1999546496 trong 0,143 ns — nhanh 4 lần nhưng KHÁC kết quả, vì nó sắp lại phép cộng để vector hóa mà số thực máy không kết hợp. Tốc độ đổi lấy độ chính xác.
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.
Union-Find không tự nhiên O(1): bản naive để cây thoái hóa thành chuỗi, đường find trung bình 9999 (=n/2), find hết mất 88 ms. Hai tối ưu vài dòng ép đường find về ~1, nhanh 3000 lần — và đẹp nhất, ở 10 triệu phần tử đường find trung bình vẫn phẳng lì ở 1,01. 'Gần O(1)' là sự thật đo được. Tôi đo.
Tra chuỗi chính xác, bảng băm nhanh hơn trie 3,4 lần và tốn ít bộ nhớ hơn 40 lần — trie nhảy con trỏ từng ký tự, mỗi bước một cache-miss. Nhưng đếm mọi khóa có tiền tố cho trước, trie nhanh hơn 32 lần vì băm phải quét cả bảng. Lợi thật của trie là tiền tố, không phải tốc độ tra. Tôi đo.
Đổ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.
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.