Tôi tin rằng những gì bạn đang xem là ảnh hưởng của locality of reference trong hệ thống phân cấp bộ nhớ của máy tính.
Thông thường, bộ nhớ máy tính được tách biệt thành các loại khác nhau mà có những đặc điểm hiệu suất khác nhau (điều này thường được gọi là memory hierarchy). Bộ nhớ nhanh nhất nằm trong thanh ghi của bộ xử lý, có thể được truy cập và đọc trong một chu kỳ đồng hồ đơn. Tuy nhiên, thường chỉ có một số ít các thanh ghi này (thường không quá 1KB). Bộ nhớ chính của máy tính, mặt khác, là rất lớn (nói, 8GB), nhưng là chậm hơn nhiều để truy cập. Để cải thiện hiệu suất, máy tính thường được xây dựng vật lý để có several levels of caches ở giữa bộ xử lý và bộ nhớ chính. Các cache này chậm hơn so với các thanh ghi nhưng nhanh hơn nhiều so với bộ nhớ chính, vì vậy nếu bạn truy cập bộ nhớ có vẻ gì đó trong bộ nhớ cache, nó sẽ nhanh hơn rất nhiều nếu bạn phải vào bộ nhớ chính (thông thường, từ 5-25x nhanh hơn). Khi truy cập bộ nhớ, trước tiên bộ xử lý sẽ kiểm tra bộ nhớ cache cho giá trị đó trước khi quay lại bộ nhớ chính để đọc giá trị. Nếu bạn truy cập vào các giá trị trong bộ nhớ cache, bạn sẽ có hiệu suất tốt hơn nhiều nếu bạn bỏ qua bộ nhớ, truy cập ngẫu nhiên các giá trị.
Hầu hết các chương trình được viết theo cách mà nếu một byte trong bộ nhớ được đọc vào bộ nhớ, chương trình sẽ đọc nhiều giá trị khác nhau xung quanh vùng bộ nhớ đó. Do đó, các cache này thường được thiết kế để khi bạn đọc một giá trị duy nhất từ bộ nhớ, một khối bộ nhớ (thường ở đâu đó giữa 1KB và 1MB) các giá trị xung quanh giá trị đó cũng được đưa vào bộ đệm. Bằng cách đó, nếu chương trình của bạn đọc các giá trị gần đó, chúng đã có trong bộ nhớ cache và bạn không cần phải đi đến bộ nhớ chính.
Bây giờ, một chi tiết cuối cùng - trong C/C++, mảng được lưu trữ theo thứ tự hàng lớn, có nghĩa là tất cả các giá trị trong một hàng của ma trận được lưu trữ cạnh nhau. Vì vậy, trong bộ nhớ mảng trông giống như hàng đầu tiên, sau đó hàng thứ hai, sau đó hàng thứ ba, vv
Cho điều này, chúng ta hãy nhìn vào mã của bạn. Phiên bản đầu tiên trông giống như sau:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Bây giờ, hãy nhìn vào dòng mã bên trong nhất. Trên mỗi lần lặp lại, giá trị của k đang thay đổi ngày càng tăng. Điều này có nghĩa là khi chạy vòng lặp trong cùng, mỗi lần lặp của vòng lặp có thể bị thiếu bộ nhớ cache khi tải giá trị của b[k][j].Lý do là vì ma trận được lưu trữ theo thứ tự hàng lớn, mỗi khi bạn tăng k, bạn sẽ bỏ qua toàn bộ hàng của ma trận và nhảy xa hơn vào bộ nhớ, có thể vượt quá các giá trị bạn đã lưu trong bộ nhớ cache . Tuy nhiên, bạn không bỏ lỡ khi tra cứu c[i][j] (kể từ i và j giống nhau), cũng như bạn sẽ không bỏ lỡ a[i][k], bởi vì các giá trị theo thứ tự hàng lớn và nếu giá trị a[i][k] được lưu trong bộ nhớ cache trước đó lặp lại, giá trị của a[i][k] đọc trên lần lặp này là từ một vị trí bộ nhớ liền kề. Do đó, trên mỗi lần lặp của vòng lặp trong cùng, bạn có thể có một bộ nhớ cache bỏ lỡ.
Nhưng xem xét phiên bản thứ hai này:
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
for (int j = 0; j < n; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Bây giờ, kể từ khi bạn đang tăng j trên mỗi lần lặp, chúng ta hãy suy nghĩ về bao nhiêu bộ nhớ cache nhớ bạn có thể sẽ có trên báo cáo kết quả trong cùng. Bởi vì các giá trị nằm trong thứ tự hàng lớn, giá trị của c[i][j] có thể nằm trong bộ nhớ cache, bởi vì giá trị của c[i][j] từ lần lặp trước đó có khả năng được lưu vào bộ nhớ cache và sẵn sàng để đọc. Tương tự, b[k][j] có thể được lưu trong bộ nhớ cache và vì i và k không thay đổi, rất có thể là a[i][k] cũng được lưu trong bộ nhớ cache. Điều này có nghĩa rằng trên mỗi lần lặp của vòng lặp bên trong, bạn có thể không có bộ nhớ cache bị bỏ sót.
Nói chung, điều này có nghĩa là phiên bản thứ hai của mã không có khả năng bị mất bộ nhớ cache trên mỗi lần lặp của vòng lặp, trong khi phiên bản đầu tiên gần như chắc chắn sẽ xảy ra. Do đó, vòng lặp thứ hai có thể nhanh hơn lần đầu tiên, như bạn đã thấy.
Điều thú vị là nhiều trình biên dịch bắt đầu có hỗ trợ mẫu để phát hiện phiên bản thứ hai của mã nhanh hơn phiên bản đầu tiên. Một số sẽ cố gắng tự động viết lại mã để tối đa hóa tính song song. Nếu bạn có một bản sao của Purple Dragon Book, Chương 11 sẽ thảo luận cách thức các trình biên dịch này hoạt động.
Ngoài ra, bạn có thể tối ưu hóa hiệu suất của vòng lặp này hơn nữa bằng cách sử dụng các vòng phức tạp hơn. Ví dụ, một kỹ thuật được gọi là blocking có thể được sử dụng để tăng hiệu suất bằng cách tách mảng thành các phần con có thể được lưu trong bộ nhớ cache lâu hơn, sau đó sử dụng nhiều thao tác trên các khối này để tính toán kết quả tổng thể.
Hy vọng điều này sẽ hữu ích!
+1 Giải thích tuyệt vời thực sự! Ngoài ra gợi ý @Kerrek SB thực hiện về việc gỡ lỗi bộ nhớ cache thêm nhiều chi tiết kỹ thuật hơn. – rbaleksandar