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.
Đọc một byte thì chỉ tốn một byte băng thông? Đo ra: CPU nạp cả một dòng cache mỗi lần chạm bộ nhớ, nên đọc thưa (mỗi phần tử một dòng) chậm gấp 10 lần đọc liền. Và ngưỡng bão hòa lộ kích thước dòng thật của máy: host ARM này (Apple Silicon) dùng dòng 128 byte, không phải 64 byte như x86 quen thuộc.