Tại sao tệ hơn khi khởi tạo mảng hai chiều như thế này?

Question

for(int i = 0; i<100; i++) 

    for(int j = 0; j<100; j++) 

     array[j][i] = 0; 
     // array[i][j] = 0; 

Giáo sư của tôi cho rằng việc khởi tạo mảng hai chiều tốn kém hơn rất nhiều so với lần thứ hai. Ai đó có thể giải thích những gì đang xảy ra bên dưới mui xe mà làm cho rằng trường hợp? Hoặc, làm hai phương tiện khởi tạo có hiệu suất như nhau?

Answer 1

Như @dlev đã đề cập, điều này là do locality of reference và phải làm thế nào với phần cứng vật lý trong máy tính hoạt động.

Bên trong máy tính, có nhiều loại bộ nhớ khác nhau. Thông thường, chỉ một số vị trí bộ nhớ nhất định (thanh ghi) có thể thực hiện các hoạt động thực tế trên chúng; phần còn lại của thời gian, nếu bạn đang thực hiện các hoạt động trên dữ liệu, bạn phải tải nó từ bộ nhớ vào một thanh ghi, thực hiện một số tính toán, sau đó ghi nó trở lại.

Bộ nhớ chính (RAM) nhiều, chậm hơn nhiều so với thanh ghi, thường là từ một trăm đến hàng nghìn. Do đó, việc đọc từ bộ nhớ nên tránh nếu có thể. Để giải quyết vấn đề này, hầu hết các máy tính thường có các vùng nhớ đặc biệt được gọi là caches. Công việc của bộ nhớ cache là giữ dữ liệu gần đây đã được truy cập từ bộ nhớ sao cho nếu cùng một vùng bộ nhớ đó được truy cập lần nữa, giá trị có thể được lấy từ bộ nhớ cache (nhanh) thay vì từ bộ nhớ chính (chậm). Thông thường, cache được thiết kế sao cho nếu một giá trị được đọc từ bộ nhớ, giá trị đó, cộng với một bó toàn bộ các giá trị liền kề, được đưa vào bộ nhớ cache. Bằng cách đó, nếu bạn lặp qua một mảng, sau đó sau khi đọc giá trị đầu tiên, phần còn lại của các giá trị từ mảng sẽ được đặt trong bộ đệm và có thể được truy cập hiệu quả hơn.

Lý do mã của bạn chậm hơn mức cần thiết là mã không truy cập vào phần tử mảng tuần tự. Trong C, mảng 2D được trình bày dưới row-major order, có nghĩa là bộ nhớ được bố trí như

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ... 

Do đó, nếu bạn sử dụng điều này cho vòng lặp:

for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
     // Do something with A[i][j] 
    } 
} 

Sau đó, bạn sẽ có được địa phương tuyệt vời, bởi vì bạn sẽ truy cập các phần tử mảng theo thứ tự xuất hiện trong bộ nhớ. Điều này làm cho số lần đọc của bộ nhớ chính rất nhỏ, vì tất cả mọi thứ thường là trong bộ nhớ cache và sẵn sàng để đi.

Tuy nhiên, nếu bạn trao đổi các vòng lặp, như bạn đã làm, truy cập của bạn nhảy xung quanh trong bộ nhớ và không nhất thiết phải liên tiếp. Điều này có nghĩa là bạn sẽ có rất nhiều bộ nhớ cache bỏ lỡ trong đó địa chỉ bộ nhớ bạn đọc tiếp theo không có trong bộ nhớ cache. Điều này làm tăng số lượng tải bộ nhớ cache, có thể làm chậm đáng kể chương trình.

Trình biên dịch bắt đầu đủ thông minh để trao đổi các vòng như thế này một cách tự động, nhưng chúng tôi vẫn còn cách để tránh bỏ qua các chi tiết này. Như một quy tắc chung, khi viết mã C hoặc C++ cho các mảng đa chiều, hãy cố gắng lặp lại theo thứ tự hàng lớn hơn là thứ tự cột lớn. Bạn có thể nhận được tốc độ đáng chú ý trong chương trình của bạn.

Hy vọng điều này sẽ hữu ích!

Answer 2

Nếu bạn nhìn vào các vị trí bộ nhớ được truy cập bởi mỗi kỹ thuật, thứ hai sẽ truy cập các byte liên tiếp, trong khi lần đầu tiên sẽ nhảy xung quanh các bước nhảy 100 byte. Bộ nhớ cache sẽ hoạt động hiệu quả hơn nhiều nếu bạn làm theo cách thứ hai.

Answer 3

tôi có lẽ sẽ nhận được downvoted cho điều này, nhưng nếu bạn đang lập trình C, sau đó là "tốt nhất" rất có thể là:

memset (mảng, 0, sizeof (mảng));

Sau đó, bạn có thể trì hoãn tất cả trách nhiệm tối ưu hóa (điều mà bạn đang lo lắng) về việc thực hiện ghi nhớ. Bất kỳ lợi thế phần cứng cụ thể có thể được thực hiện ở đó.

http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/

http://www.cplusplus.com/reference/clibrary/cstring/memset/

quan sát khác là nếu bạn đang init'ing bằng không, hãy tự hỏi tại sao? Nếu mảng của bạn là tĩnh (mà cho nó lớn nó có thể là?), Sau đó cstartup sẽ khởi tạo bằng không cho bạn. Một lần nữa, điều này có thể sẽ sử dụng cách hiệu quả nhất cho phần cứng của bạn.

Answer 4

Tôi hơi muộn với bữa tiệc và đã có một câu trả lời tuyệt vời. Tuy nhiên, tôi nghĩ tôi có thể đóng góp bằng cách chứng minh cách người ta có thể trả lời câu hỏi này bằng cách sử dụng một công cụ định hình (trên Linux).

Tôi sẽ sử dụng công cụ perf trong gói 10.10 Ubuntu linux-tools-common.

Đây là chương trình C nhỏ tôi đã viết để trả lời câu hỏi này:

// test.c 
#define DIM 1024 

int main() 
{ 
    int v[DIM][DIM]; 
    unsigned i, j; 

    for (i = 0; i < DIM; i++) { 
     for (j = 0; j < DIM; j++) { 
#ifdef ROW_MAJOR_ORDER 
      v[i][j] = 0; 
#else 
      v[j][i] = 0; 
#endif 
     } 
    } 

    return 0; 
} 

Sau đó biên dịch hai phiên bản khác nhau:

$ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj 
$ gcc test.c -O0 -o row-min 

Lưu ý tôi đã vô hiệu hóa tối ưu hóa với -O0 để gcc đã không có cơ hội để sắp xếp lại vòng lặp của chúng tôi để có hiệu quả hơn.

Chúng tôi có thể liệt kê thống kê hiệu suất có sẵn với perf bằng cách thực hiện perf list. Trong trường hợp này, chúng tôi quan tâm đến việc xóa bộ nhớ cache là sự kiện cache-misses.

Bây giờ là đơn giản như chạy mỗi phiên bản của chương trình nhiều lần và lấy trung bình:

$ perf stat -e cache-misses -r 100 ./row-min 

Performance counter stats for './row-min' (100 runs): 

      286468 cache-misses    (+- 0.810%) 

     0.016588860 seconds time elapsed (+- 0.926%) 

$ perf stat -e cache-misses -r 100 ./row-maj 

Performance counter stats for './row-maj' (100 runs): 

       9594 cache-misses    (+- 1.203%) 

     0.006791615 seconds time elapsed (+- 0.840%) 

Và bây giờ chúng tôi đã thực nghiệm xác minh rằng bạn làm trong thực tế thấy hai bậc độ lớn hơn bỏ lỡ bộ nhớ cache với phiên bản "hàng nhỏ".