Là một lập trình viên yêu công nghệ, thích viết blog để chia sẻ kiến thức, kinh nghiệm lập trình và những điều thú vị trong thế giới tech.
Một vòng 2 tỉ phép tính mà kết quả không ai dùng đo ra đúng 0,00 ns — gcc -O2 xóa cả vòng, hàm chỉ còn ret. Thêm một volatile sink là số nhảy lên 1,37 ns thật. Khử mã chết còn xóa dead store và mã sau return, và đây chính là lý do mọi benchmark cần 'quan sát' kết quả.
Ma trận kề ngốn 1.527 MB ở V=40.000 và OOM quanh V~90.000, còn danh sách kề chỉ 2,6 MB. Bảng DP đầy đủ dùng 382 MB, bản cuộn hai biến dùng 1 MB cùng thời gian. Merge sort tốn gấp đôi RAM nhưng nhanh hơn heapsort 3,7 lần. Không gian là bức tường cứng, không phải tài nguyên miễn phí — tôi đọc VmHWM để đo.
Định bắt quả tang -ffast-math làm sai số. Đo ra ngược hẳn: bản IEEE strict kẹt ở 2^24 (16777216) sai nặng, fast-math gần đúng hơn và nhanh 4 lần. Nhưng nó âm thầm xóa lá chắn NaN. Đo thật, đọc assembly trong container.
Mọi sắp xếp dựa trên so sánh bị chặn ở O(n log n). Nhưng radix và counting sort chạy O(n): radix thắng introsort 5–11 lần trên số 32-bit ở mọi cỡ, counting sort nhanh 15,6 lần với khóa nhỏ. Giới hạn thật không ở n nhỏ mà ở bề rộng khóa (32-bit 4 lượt, 64-bit 8 lượt) và scatter phá cache. Tôi đo.
Mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần (0,21 µs so 3.869 µs) — nhưng phải dựng mảng trước, tốn 358 ms cho văn bản 2 triệu ký tự. Cho một lần tìm, KMP thắng đậm; suffix array chỉ có lãi sau ~93 truy vấn trên cùng văn bản. 'Nhanh nhất' vô nghĩa nếu chưa hỏi tìm bao nhiêu lần. Tôi đo.
PGO trông nhanh hơn -O2 hẳn 1,3 lần — cho tới khi tôi nhận ra file hồ sơ chưa từng được đọc, và cái nhanh thật ra đến từ mấy cờ mà -fprofile-use tự bật. Đo thật, và một bài học về đo nhầm đại lượng.