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.
Tưởng cứ -O3 -Ofast -march=native -funroll là nhanh nhất? Tôi đo một workload thật: -O3 bằng -O2, -march không đổi, -funroll chỉ 3%, chỉ -ffast-math nhanh 2,9 lần nhưng đổi kết quả số thực. Không có combo cờ thần — mỗi cờ là một đánh đổi phụ thuộc workload, và cách duy nhất chọn đúng là đo ở đúng máy, đúng cờ, đúng code của bạn.
Cần thêm phần tử ở đầu danh sách? Nhiều người bảo dùng vector cũng được. Tôi đo thử — và vector push_front hóa ra là O(n): mỗi lần thêm gấp đôi thời gian khi số phần tử gấp đôi (1552 → 3375 ns), vì nó phải dịch cả mảng. Một ring buffer chỉ lùi một chỉ số, O(1) (~3 ns), nhanh hơn 1136 lần ở N=100k. Còn std::deque thì push được hai đầu O(1), duyệt chỉ chậm hơn vector 19%.
Sắp xếp nào cũng như nhau, cứ std::sort? Tôi đo thử: sắp tại chỗ tốn ~0 bộ nhớ phụ nhưng không ổn định; sắp cấp thêm (merge) tốn 80 MB buffer cho 20 triệu int nhưng giữ thứ tự phần tử bằng nhau. Và quicksort pivot xấu trên dữ liệu đã sắp xếp thành O(n²), chậm 2428 lần.
Ai cũng dặn phải căn lề dữ liệu kẻo truy cập bộ nhớ chậm. Nhưng đo trên ARM, đọc lệch — kể cả cắt ngang dòng cache — nhanh y hệt căn lề. Chỉ có đúng một chỗ khiến nó lết: khi 8 byte vắt qua ranh giới trang, chậm gần 30 lần. Cái x86 bắt bạn sợ với cái thật sự nguy hiểm hóa ra không phải một.
Đo sáu vòng lặp bằng gcc và clang: clang nhanh hơn 2-4 lần ở vài vòng, hòa ở số khác. Tôi định kết 'clang nhanh hơn' và giải thích nó thắng popcount nhờ lệnh cnt. Đọc mã máy ra ngược hẳn — gcc mới dùng cnt mà vẫn chậm. Bài cuối sê-ri, và cái bẫy tôi rơi vào cả hai chân.
BST tra cứu O(log n)? Chỉ khi cây cân bằng. Tôi đo thử: chèn dữ liệu ĐÃ sắp xếp vào một BST thường làm cây lệch thành chuỗi cao đúng bằng N (50.000), tra cứu chậm hơn std::map 461 lần và xây cây chậm 594 lần. Dữ liệu sắp xếp — thứ trông đẹp nhất — hóa ra là worst case, không phải best.