Mengapa urutan loop memengaruhi kinerja saat iterasi pada array 2D?

Di bawah ini adalah dua program yang hampir identik kecuali bahwa saya mengaktifkan idan jvariabel sekitar. Keduanya berjalan dalam jumlah waktu yang berbeda. Bisakah seseorang menjelaskan mengapa ini terjadi?

Versi 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Versi 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

Seperti orang lain berkata, masalah ini adalah toko ke lokasi memori dalam array: x[i][j]. Inilah sedikit wawasan mengapa:

Anda memiliki larik 2 dimensi, tetapi memori di komputer pada dasarnya adalah 1 dimensi. Jadi, sementara Anda membayangkan array Anda seperti ini:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Komputer Anda menyimpannya dalam memori sebagai satu baris:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

Pada contoh ke-2, Anda mengakses array dengan mengulangi angka ke-2 terlebih dahulu, yaitu:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Berarti Anda memukul semuanya secara berurutan. Sekarang lihat versi 1. Kamu lakukan:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Karena cara C meletakkan array 2-d dalam memori, Anda memintanya untuk melompat ke semua tempat. Tapi sekarang untuk si penendang: Mengapa ini penting? Semua akses memori sama, kan?

Tidak: karena cache. Data dari memori Anda akan dibawa ke CPU dalam potongan kecil (disebut 'cache lines'), biasanya 64 byte. Jika Anda memiliki bilangan bulat 4-byte, itu artinya Anda mendapatkan 16 bilangan bulat berturut-turut dalam satu bungkusan kecil yang rapi. Sebenarnya cukup lambat untuk mengambil potongan memori ini; CPU Anda dapat melakukan banyak pekerjaan dalam waktu yang dibutuhkan untuk satu baris cache untuk memuat.

Sekarang lihat kembali urutan akses: Contoh kedua adalah (1) mengambil sepotong 16 int, (2) memodifikasi semuanya, (3) ulangi 4000 * 4000/16 kali. Itu bagus dan cepat, dan CPU selalu memiliki sesuatu untuk dikerjakan.

Contoh pertama adalah (1) ambil sepotong 16 int, (2) memodifikasi hanya satu dari mereka, (3) ulangi 4000 * 4000 kali. Itu akan membutuhkan 16 kali jumlah "pengambilan" dari memori. CPU Anda sebenarnya harus menghabiskan waktu duduk-duduk menunggu memori itu muncul, dan sementara itu duduk di sekitar Anda membuang-buang waktu yang berharga.

Catatan penting:

Sekarang setelah Anda memiliki jawabannya, inilah catatan yang menarik: tidak ada alasan yang melekat bahwa contoh kedua Anda haruslah yang cepat. Misalnya, di Fortran, contoh pertama akan cepat dan yang kedua lambat. Itu karena alih-alih memperluas hal-hal menjadi "baris" konseptual seperti C, Fortran memperluas ke "kolom", yaitu:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

Tata letak C disebut 'baris-utama' dan Fortran disebut 'kolom-utama'. Seperti yang Anda lihat, sangat penting untuk mengetahui apakah bahasa pemrograman Anda adalah baris-utama atau kolom-utama! Berikut ini tautan untuk info lebih lanjut: http://en.wikipedia.org/wiki/Row-major_order

Tidak ada hubungannya dengan perakitan. Ini karena kesalahan cache .

Array multidimensi disimpan dengan dimensi terakhir sebagai yang tercepat. Jadi versi pertama akan kehilangan cache di setiap iterasi, sedangkan versi kedua tidak akan. Jadi versi kedua seharusnya jauh lebih cepat.

Lihat juga: http://en.wikipedia.org/wiki/Loop_interchange .

Versi 2 akan berjalan jauh lebih cepat karena menggunakan cache komputer Anda lebih baik daripada versi 1. Jika Anda memikirkannya, array hanyalah area memori yang berdekatan. Saat Anda meminta elemen dalam array, OS Anda mungkin akan memasukkan halaman memori ke dalam cache yang berisi elemen itu. Namun, karena beberapa elemen berikutnya juga ada di halaman itu (karena mereka bersebelahan), akses selanjutnya akan berada dalam cache! Inilah yang dilakukan versi 2 untuk mempercepatnya.

Versi 1, di sisi lain, adalah mengakses elemen kolom dengan bijak, dan bukan baris bijak. Akses semacam ini tidak bersebelahan pada tingkat memori, sehingga program tidak dapat memanfaatkan cache OS sebanyak ini.

Alasannya adalah akses data cache-lokal. Dalam program kedua Anda memindai secara linear melalui memori yang mendapat manfaat dari caching dan prefetching. Pola penggunaan memori program pertama Anda jauh lebih tersebar dan karenanya memiliki perilaku cache yang lebih buruk.

Selain jawaban luar biasa lainnya tentang hit cache, ada juga kemungkinan perbedaan optimasi. Loop kedua Anda kemungkinan akan dioptimalkan oleh kompiler menjadi sesuatu yang setara dengan:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

Ini lebih kecil kemungkinannya untuk loop pertama, karena itu perlu menambah pointer "p" dengan 4000 setiap kali.

EDIT: p++ dan bahkan *p++ = ..dapat dikompilasi ke instruksi CPU tunggal di sebagian besar CPU. *p = ..; p += 4000tidak bisa, jadi ada sedikit manfaat dalam mengoptimalkannya. Ini juga lebih sulit, karena kompiler perlu mengetahui dan menggunakan ukuran array dalam. Dan itu tidak terjadi yang sering di loop dalam dalam kode normal (itu hanya terjadi untuk array multidimensi, di mana indeks terakhir dijaga konstan dalam loop, dan yang kedua ke yang terakhir diinjak), jadi optimisasi kurang menjadi prioritas .

Baris ini pelakunya:

x[j][i]=i+j;

Versi kedua menggunakan memori terus menerus sehingga akan jauh lebih cepat.

Saya mencoba

x[50000][50000];

dan waktu eksekusi adalah 13 untuk versi1 versus 0,6 untuk versi2.

_{Saya mencoba memberikan jawaban umum.}

Karena i[y][x]merupakan singkatan untuk *(i + y*array_width + x)di C (cobalah yang berkelas int P[3]; 0[P] = 0xBEEF;).

Saat Anda mengulanginya y, Anda beralih pada potongan ukuran array_width * sizeof(array_element). Jika Anda memilikinya di lingkaran dalam Anda, maka Anda akan memiliki array_width * array_heightiterasi atas potongan-potongan itu.

Dengan membalik urutan, Anda hanya akan memiliki array_heightiterasi chunk, dan di antara iterasi chunk, Anda hanya akan memiliki array_widthiterasi sizeof(array_element).

Sementara pada x86-CPU yang benar-benar tua, ini tidak terlalu menjadi masalah, saat ini x86 banyak melakukan prefetching dan caching data. Anda mungkin menghasilkan banyak kesalahan cache dalam iterasi-order Anda yang lebih lambat.