Viết một vòng lặp, bọc đồng hồ hai đầu, chia cho số phần tử — nghe là xong. Nhưng cùng một đoạn code, tôi đo được 0 nano-giây (nhanh vô hạn), rồi 0,57, rồi 2,62 ns, tùy vào những cái bẫy mà trình biên dịch giăng sau lưng. Chỉ một cách đo là ra con số thật.
Cây và list phải dùng con trỏ, đó là cách chuẩn? Tôi đo thử: thay con trỏ 8 byte bằng chỉ số 4 byte vào một arena làm node nhỏ hơn 33%, RAM ít hơn 33%, và tra cứu nhanh 1,86 lần — vì node nằm liền mạch thay vì malloc rải rác. Con trỏ không phải lựa chọn duy nhất, và thường không phải lựa chọn tốt nhất.
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.
fork một tiến trình 512MB chỉ tốn 28µs — nó không sao chép dữ liệu, chỉ chép bảng trang (nhanh hơn nghìn lần). Nhưng chi phí sao chép không mất, nó bị hoãn: ghi vào 64MB heap chung sau fork tốn 20,2ms với 16.419 COW fault, chậm ~200 lần ghi thường. Khi cái gì 'gần như miễn phí', hỏi tiếp chi phí đi đâu.
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.
Đ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.