GIẢI THÍCH: Vấn đề nằm ở CPU cache

Đáp án cho câu hỏi trong bài: https://daohainam.com/2021/12/30/vi-sao-duyet-mang-theo-dong-lai-nhanh-hon-theo-cot/

Khi nằm trong bộ nhớ, các mảng nhiều chiều sẽ được diễn dịch thành một mảng 1 chiều (vì bộ nhớ về cơ bản cũng chỉ là mảng 1 chiều). Mỗi dòng sẽ được sắp xếp liên tục theo thứ tự. Mỗi khi cần truy xuất đến 1 ô nào đó có địa chỉ m[dòng, cột], trình biên dịch sẽ biến đổi thành m[dòng * chiều rộng mảng + cột] (xem hình minh họa).

Như vậy, nếu ta đi chuyển theo dòng->cột (tương ứng với calculate_sum(sum, 1) trong https://github.com/…/clanc…/blob/master/CachingTests.cpp), thứ tự truy xuất trong bộ nhớ sẽ được tăng dần, trong khi đó, nếu ta di chuyển theo cột->dòng, thứ tự truy xuất theo hình minh họa sẽ là 0, 4, 8, 1, 5…

Bộ nhớ cache trong CPU được tổ chức theo từng lance (không biết dịch ra thế nào, trong tiếng Việt ta vẫn dùng từ lance để chỉ các phần đường phân cách nhau). Mỗi lance có kích thước 64 byte, mỗi khi nạp từ RAM vào cache, hay từ cache vào RAM nó sẽ luôn làm việc với từng lance như vậy. Do đó khi đọc vào 1 byte, tất cả các byte lân cận trong cùng lance sẽ nằm sẵn ngay trong cache, khi bạn đọc đến byte kế tiếp bạn chỉ cần lấy nó ra từ cache (cache hit). Tốc độ của cache lại nhanh hơn RAM rất nhiều, người ta tính toán rằng cache L1 trong CPU có tốc độ nhanh hơn vài chục tới cả trăm lần so với truy xuất từ RAM.

Kết quả là việc đọc/ghi dữ liệu tuần tự sẽ cho tốc độ tốt hơn nhiều so với truy xuất ngẫu nhiên. Điều này cũng tương tự như khi bạn đọc dữ liệu từ ổ SSD, vốn không có các cơ cấu cơ học và không có thời gian di chuyển đầu đọc như HDD, tuy nhiên khi copy 1 file lớn vẫn nhanh hơn nhiều so với copy nhiều file nhỏ. Đó cũng là do khi đọc/ghi tuần tự thì xác suất cache hit sẽ lớn hơn nhiều so với cache miss.Khi làm việc với các ứng dụng lớn, việc tổ chức cách lưu trữ dữ liệu rất quan trọng!