Kết sê-ri 45 phần bằng một phép đo gói trọn luận điểm: cùng 10 triệu số nguyên, cùng phép tính tổng O(n), nhưng mảng liền mạch chạy 0,225 ns mỗi phần tử còn mảng con trỏ rải rác 5,48 ns — chênh 24 lần chỉ vì cache và con trỏ, thứ mà Big-O hoàn toàn giấu. Bài học cả sê-ri: đừng đoán, hãy đo — và đo cho đúng.
Câu đố kinh điển trên Stack Overflow: cùng một vòng lọc, mảng đã sắp xếp chạy nhanh hơn hẳn mảng xáo trộn. Tôi dựng lại thí nghiệm trên máy ARM và thấy hai điều: hồi đó nó đúng, và bây giờ thì g++ đã âm thầm dẹp luôn cái hiệu ứng ấy.
Đoán sai một nhánh chỉ chậm đi một chút? Đo ra: quét tỉ lệ nhánh được lấy từ 0% đến 100%, thời gian vẽ thành một hình chuông đỉnh ở 50% — nhánh đoán được (0% hoặc 100%) tốn 0,24–0,45 ns còn nhánh 50/50 tốn 2,38 ns. Từ đó suy ra phạt mỗi lần đoán sai ~3,86 ns, tức khoảng 12 chu kỳ CPU — đúng cỡ một lần xả pipeline.
Cùng số phép tính thì cùng thời gian? Đo ra: cộng dồn một mảng bằng một biến tích lũy tốn 0,569 ns mỗi phép cộng, nhưng dùng 8 biến độc lập rồi gộp cuối chỉ tốn 0,085 ns — nhanh 6,7 lần dù y hệt số phép cộng. Khác biệt là đồ thị phụ thuộc: chuỗi phụ thuộc phải chờ từng bước, còn các phép độc lập chạy song song trong một lõi (ILP).
Trình biên dịch -O2 tự vector hóa hết mọi vòng lặp số? Đo ra: một kernel tính từng phần tử độc lập nhanh 3,9 lần khi vector hóa (NEON 128-bit gói 4 float mỗi lệnh), nhưng một vòng có phụ thuộc — y[i] cần y[i-1] — thì không vector hóa được, vector và scalar bằng nhau y hệt. SIMD nhanh N lần chỉ khi vòng vector hóa được và compute-bound.
Một lần truy cập bộ nhớ tốn thời gian như nhau? Đo ra: đuổi con trỏ qua vùng làm việc lớn dần, thời gian mỗi truy cập vẽ thành một bậc thang — 0,91 ns khi dữ liệu ở L1, nhảy lên 3,5 ns qua L2, rồi 46 ns, rồi 103 ns khi ra RAM: chênh 113 lần theo tầng cache. Và các ngưỡng nhảy chính là kích thước từng tầng cache của máy.