Mengapa program saya lambat ketika mengulang elemen 8192?

Berikut adalah kutipan dari program yang dimaksud. Matriks img[][]memiliki ukuran SIZE × SIZE, dan diinisialisasi pada:

img[j][i] = 2 * j + i

Kemudian, Anda membuat matriks res[][], dan setiap bidang di sini dibuat menjadi rata-rata dari 9 bidang di sekitarnya dalam matriks img. Batas dibiarkan pada 0 untuk kesederhanaan.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Itu semua ada untuk program ini. Demi kelengkapan, inilah yang terjadi sebelumnya. Tidak ada kode yang muncul setelahnya. Seperti yang Anda lihat, itu hanya inisialisasi.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

Pada dasarnya, program ini lambat ketika SIZE adalah kelipatan 2048, misalnya waktu eksekusi:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

Kompilernya adalah GCC. Dari apa yang saya tahu, ini karena manajemen memori, tetapi saya tidak terlalu tahu banyak tentang subjek itu, itulah sebabnya saya bertanya di sini.

Juga cara memperbaikinya akan menyenangkan, tetapi jika seseorang dapat menjelaskan waktu eksekusi ini saya sudah cukup senang.

Saya sudah tahu tentang malloc / gratis, tetapi masalahnya bukan jumlah memori yang digunakan, ini hanya waktu eksekusi, jadi saya tidak tahu bagaimana itu akan membantu.

Perbedaan ini disebabkan oleh masalah super-alignment yang sama dari pertanyaan terkait berikut:

• Mengapa transposing matriks 512x512 jauh lebih lambat daripada transposing matriks 513x513?
• Perkalian matriks: Perbedaan kecil dalam ukuran matriks, perbedaan besar dalam pengaturan waktu

Tapi itu hanya karena ada satu masalah lain dengan kode.

Mulai dari loop asli:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Pertama perhatikan bahwa dua loop dalam itu sepele. Mereka dapat dibuka gulungannya sebagai berikut:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Sehingga menyisakan dua loop luar yang kami minati.

Sekarang kita dapat melihat masalahnya adalah sama dalam pertanyaan ini: Mengapa urutan loop mempengaruhi kinerja ketika iterasi melalui array 2D?

Anda iterasi matriks kolom-bijaksana bukan baris-bijaksana.

Untuk mengatasi masalah ini, Anda harus menukar kedua loop.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Ini menghilangkan semua akses non-sekuensial sepenuhnya sehingga Anda tidak lagi mendapatkan perlambatan acak pada kekuatan besar dua.

Core i7 920 @ 3.5 GHz

Kode asli:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Loop Luar Tertukar:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds

Tes-tes berikut telah dilakukan dengan kompiler Visual C ++ seperti yang digunakan oleh instalasi Qt Creator default (saya kira tanpa flag optimasi). Saat menggunakan GCC, tidak ada perbedaan besar antara versi Mystical dan kode saya "dioptimalkan". Jadi kesimpulannya adalah bahwa optimasi kompiler merawat optimasi mikro lebih baik daripada manusia (akhirnya saya). Saya meninggalkan sisa jawaban saya untuk referensi.

Tidak efisien untuk memproses gambar dengan cara ini. Lebih baik menggunakan array dimensi tunggal. Memproses semua piksel dilakukan dalam satu loop. Akses acak ke titik dapat dilakukan dengan menggunakan:

pointer + (x + y*width)*(sizeOfOnePixel)

Dalam kasus khusus ini, lebih baik untuk menghitung dan menyimpan jumlah tiga kelompok piksel secara horizontal karena masing-masing digunakan tiga kali.

Saya telah melakukan beberapa tes dan saya pikir ini layak untuk dibagikan. Setiap hasil adalah rata-rata dari lima tes.

Kode asli oleh user1615209:

8193: 4392 ms
8192: 9570 ms

Versi mistik:

8193: 2393 ms
8192: 2190 ms

Dua lintasan menggunakan larik 1D: lintasan pertama untuk jumlah horizontal, kedua lintasan untuk jumlah vertikal dan rata-rata. Two pass addressing dengan tiga pointer dan hanya penambahan seperti ini:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Dua pass menggunakan array 1D dan menangani seperti ini:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

Satu lulus caching jumlah horisontal hanya satu baris di depan sehingga mereka tetap di cache:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Kesimpulan:

• Tidak ada manfaat menggunakan beberapa petunjuk dan hanya peningkatan (saya pikir akan lebih cepat)
• Caching jumlah horizontal lebih baik daripada menghitungnya beberapa kali.
• Dua operan bukan tiga kali lebih cepat, hanya dua kali.
• Dimungkinkan untuk mencapai 3,6 kali lebih cepat menggunakan pass tunggal dan caching hasil perantara

Saya yakin itu mungkin dilakukan jauh lebih baik.

CATATAN Tolong, perhatikan bahwa saya menulis jawaban ini untuk menargetkan masalah kinerja umum daripada masalah cache yang dijelaskan dalam jawaban Mystical yang sangat baik. Pada awalnya itu hanya kode semu. Saya diminta untuk melakukan tes di komentar ... Ini adalah versi yang sepenuhnya di-refactored dengan tes.