Trong phân tích thuật toán, đếm thao tác và bước. Điều này hợp lý khi máy tính mất thời gian thực hiện thao tác nhiều hơn lấy dữ liệu cho thao tác. Ngày nay chi phí thực hiện thao tác thấp hơn đáng kể chi phí lấy dữ liệu từ bộ nhớ.
Thời gian chạy nhiều thuật toán bị chi phối bởi số tham chiếu bộ nhớ (số cache misses) thay vì số thao tác. Vì vậy, khi thiết kế thuật toán, phải tập trung giảm không chỉ số thao tác mà cả số truy cập bộ nhớ. Cũng phải thiết kế thuật toán che giấu độ trễ bộ nhớ.
Giả sử mô hình máy tính đơn giản: bộ nhớ gồm L1 cache, L2 cache, main memory. Thực hiện phép toán logic/số học bằng ALU trên dữ liệu trong thanh ghi (R).
Sơ đồ khối:
Từ sơ đồ cũng biết kích thước: Main memory hàng trăm/nghìn MB. L2 cache một phần MB. L1 cache vài KB. Thanh ghi vài bit. Khi chạy chương trình, tất cả dữ liệu trong bộ nhớ. Nếu thêm phép ADD, số đầu tiên lưu vào thanh ghi, dữ liệu trong thanh ghi cộng, kết quả ghi vào bộ nhớ.
Giả sử một chu kỳ là thời gian cộng dữ liệu đã ở thanh ghi. Thời gian nạp từ L1 cache vào thanh ghi: 2 chu kỳ. Nếu không có trong L1 nhưng có trong L2: L1 miss, lấy từ L2 lên L1 và thanh ghi trong 10 chu kỳ. Nếu không có trong L2: L2 miss, lấy từ main memory lên L2, L1, thanh ghi trong 100 chu kỳ. Ghi dữ liệu tính 1 chu kỳ ngay cả khi ghi vào main memory, vì không chờ ghi xong mới chuyển thao tác tiếp theo.