Giữ nhiều phiên bản của một cấu trúc thì phải copy cả nó mỗi lần sửa, tốn O(n)? Đo ra: một persistent vector kiểu trie nhánh 32 chỉ copy đường dẫn tới phần đổi — update nhanh hơn copy cả mảng 319 lần, và mỗi phiên bản mới tốn 1,76 KB thay vì 4 MB, ít hơn 2345 lần. Còn đọc thì chỉ chậm hơn mảng phẳng 1,1 lần vì nhánh rộng giữ cây nông.
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).
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.
Dữ liệu nhỏ hơn cache thì luôn nằm trong cache? Đo ra: chỉ 8 con trỏ — vài chục byte dữ liệu thật — cũng chậm gấp 3-4 lần nếu chúng cách nhau đúng 64KB (lũy thừa 2), vì tất cả dồn vào cùng một tập cache và đá nhau ra (conflict miss). Cách nhau một số không lũy thừa 2 thì phẳng lì. Và ngưỡng conflict lộ luôn số way của cache.
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.
Đọ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.