thay đổi tốc độ truy cập mảng C++ 2d dựa trên thứ tự [a] [b]?

Question

thể trùng lặp:
Why is my program slow when looping over exactly 8192 elements?

tôi đã mày mò xung quanh với một chương trình mà tôi đang sử dụng chỉ đơn giản là tổng hợp các yếu tố của một mảng 2ngày. Một lỗi đánh máy dẫn đến những gì dường như với tôi ít nhất, một số kết quả rất lạ.

Khi giao dịch với mảng, ma trận [SIZE] [SIZE]:

for(int row = 0; row < SIZE; ++row) 
    for(int col = 0; col < SIZE; ++col) 
     sum1 += matrix[row][col]; 

Chạy rất nhanh chóng, tuy nhiên là dòng trên sum1 ... được sửa đổi:

sum2 += matrix[col][row] 

Như tôi đã làm một lần bị tai nạn mà không nhận ra nó, tôi nhận thấy rằng thời gian chạy của tôi tăng đáng kể. Tại sao điều này?

Answer 1

Điều này là do hành vi lưu vào bộ nhớ cache của chương trình của bạn.

Mảng chỉ là khối liên tiếp của bộ nhớ, vì vậy khi bạn truy cập [hàng] [cột] bạn đang truy cập bộ nhớ theo trình tự. Điều này có nghĩa là trang dữ liệu bạn đang truy cập nằm trên cùng một trang, do đó truy cập nhanh hơn nhiều.

Khi bạn làm [cột] [hàng], bạn sẽ không truy cập bộ nhớ đó liên tiếp nữa, vì vậy bạn sẽ bị mất nhiều bộ nhớ cache hơn, do đó chương trình của bạn chạy chậm hơn nhiều.

Answer 2

Đó là vì trong trường hợp nhanh hơn, tìm nạp trước bộ nhớ của CPU thực sự hữu ích khi bạn đang lặp lại theo kiểu tuyến tính. Trong trường hợp chậm bạn đang nhảy xung quanh bộ nhớ và vì vậy việc tìm nạp trước có ít ảnh hưởng vì dữ liệu không có khả năng nằm trong bộ nhớ cache.

Answer 3

Phụ thuộc vào cách ma trận được đặt hàng. Bạn đang truy cập vào mảng trong hàng chính hoặc cột lớn. Tùy thuộc vào cách nó được lưu trữ trong bộ nhớ, tốc độ sẽ khác nhau giữa hai

Answer 4

Vị trí bộ nhớ của matrix[row][col] và matrix[row][col + 1] là liền kề.

Vị trí bộ nhớ của matrix[row][col] và matrix[row + 1][col] được phân tách bằng SIZE số lượng mặt hàng.

Computers như truy cập vào bộ nhớ tuần tự không ngẫu nhiên, do đó việc tiếp cận liền kề là nhanh hơn. Đối với một suy nghĩ tương tự hiệu suất ổ đĩa cứng, tuần tự đọc/ghi luôn luôn là tốt hơn so với ngẫu nhiên đọc/ghi. Điều này đã làm với cách CPU của bạn lưu trữ bộ nhớ và cố gắng dự đoán những gì bạn sẽ cần tiếp theo.

Answer 5

mảng 2d chỉ là con trỏ đến con trỏ. Vì vậy, nó trông giống như

[*p][*p][*p] 
    | | | 
    v v v 
[d] [d] [d] 
|a| |a| |a| 
|t| |t| |t| 
[a] [a] [a] 

Vì vậy, khi bạn gọi dữ liệu trên mảng không chính (những gì con trỏ này chỉ ra) hệ điều hành của bạn đặt nó vào bộ nhớ cache CPU.