Cùng một đoạn code, cùng những con số, chỉ khác mảng được sắp trước hay chưa: bản chưa sắp chạy 660 ms, bản đã sắp 379 ms — chênh 1,7 lần. Không phải ít phép tính hơn, không phải cache. Thủ phạm là dự đoán nhánh của CPU, thứ big-O không hề thấy. Viết không nhánh xóa hẳn (183 ms). Tôi đo.
Bài kết sê-ri Cơ sở dữ liệu: quy trình tối ưu đúng là đo trước, đọc kế hoạch thật, sửa một thứ, đo lại. Một vòng trọn vẹn: WHERE khach=X quét cả 2 triệu hàng (17 ms) chỉ để tìm 40; EXPLAIN chỉ thẳng, thêm index, đo lại 0,15 ms — nhanh 113 lần. Không đoán, không cãi — đo là xong.
objdump -d tháo mã máy thật ra ba cột: địa chỉ, byte, lệnh. Nhưng tháo một .o chưa liên kết thấy 'bl 0 <puts>' — số 0 là chỗ trống chờ trình liên kết điền, không phải địa chỉ thật. Đo thật trong container.
Union-find chỉ là đi lên gốc cây parent, đơn giản mà? Tôi đo thử: thiếu nén đường và union by rank, cây suy biến thành chuỗi và find thành O(n) — 28.368 ns/find. Thêm hai tối ưu, mỗi thao tác còn 3,8 ns, gần O(1) (α(n) — Ackermann ngược), nhanh hơn cả O(log n).
GROUP BY 100 nhóm trên 2 triệu hàng dùng HashAggregate chỉ 24kB; nhưng GROUP BY 2 triệu nhóm phân biệt làm nó tràn 62MB ra đĩa. Tôi suýt kết luận 'GROUP BY nhẹ RAM bất kể bảng lớn'. Bộ nhớ tính theo SỐ NHÓM phân biệt, không phải số hàng — và đó cũng là cái bẫy của COUNT(DISTINCT).
Tưởng cứ thêm #pragma omp parallel for là tự động nhanh? Tôi đo: OpenMP tiện thật, speedup ngang pthread mà chỉ một dòng — nhưng bọc quanh vòng quá nhỏ thì chậm hơn tuần tự 105 lần, chọn sai schedule chậm 1,38 lần, và vẫn dính trần Amdahl. Pragma là công cụ phải đo, không phải nút bấm là nhanh.