Kodėl mano programa vyksta lėčiau, jei kartojate per tiksliai 8192 elementus?

Čia yra ištrauka iš atitinkamos programos. img[][] matrica yra SIZE × SIZE ir inicijuota adresu:

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

Tada sukuriate res[][] matricą, o kiekvienas laukas yra 9 laukų vidurkis aplink jį img matricoje. Siekiant paprastumo, riba paliekama 0.

 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; } 

Kas yra viskas programoje. Dėl išsamumo čia yra tai, kas buvo anksčiau. Po to kodas nerodomas. Kaip matote, tai tik inicijavimas.

 #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; 

Iš esmės ši programa yra lėta, kai SIZE yra, pavyzdžiui, 2048 m. laikas:

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

Kompiliatorius yra GCC. Iš to, ką žinau, tai yra dėl atminties valdymo, bet aš tikrai nežinau per daug apie šį dalyką, todėl klausiu čia.

Be to, kaip tai pataisyti, būtų malonu, bet jei kas nors galėtų paaiškinti šiuos laikus, jau būčiau laimingas.

Aš jau žinau „malloc“ / „free“, bet problema yra ne panaudotos atminties kiekis, o tiesiog veikimo laikas, todėl nežinau, kaip tai galėtų padėti.

678
04 сент. nustatytas anon , 04 sep. 2012-09-04 16:51 '12 at 16:51 PM 2012-09-04 16:51
@ 3 atsakymai

Skirtumą sukelia tas pats super lygiavertiškumas, susijęs su šiais susijusiais klausimais:

Bet tai yra tik todėl, kad yra dar viena problema su kodu.

Nuo pradinio ciklo:

 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; } 

Pirmiausia atkreipkite dėmesį, kad dvi vidinės kilpos yra nereikšmingos. Jie gali būti išplėsti taip:

 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; } } 

Taigi, mes paliekame dvi išorines kilpas, kurios mus domina.

Dabar matome, kad ši problema yra tokia pati: kodėl ciklų eiliškumas daro įtaką našumui, kai jis kartojamas dvimatėje matricoje?

Perkeliate per stulpelius stulpeliais, o ne eilėmis.


Norėdami išspręsti šią problemą, turite keistis dviem kilpomis.

 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; } } 

Tai visiškai pašalina bet kokią nenuoseklią prieigą, kad nebegalėtumėte atsitiktinai sulėtinti didelės galios.


Core i7 920 @ 3,5 GHz

Šaltinio kodas:

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

Atstatytos išorinės kilpos:

 8191: 0.376 seconds 8192: 0.357 seconds 8193: 0.351 seconds 
858
04 сент. atsakymas pateikiamas Mysticial 04 sept. 2012-09-04 17:43 '12, 17:43, 2012-09-04 17:43

Šie testai buvo atlikti naudojant „Visual C ++“ kompiliatorių, nes jis naudojamas pagal numatytąjį „Qt Creator“ diegimą (manau, be optimizavimo vėliavos). Naudojant GCC, nėra daug skirtumų tarp mistinės versijos ir mano „optimizuoto“ kodo. Taigi daroma išvada, kad kompiliatoriaus optimizavimas yra labiau susijęs su mikroprocesoriumi nei žmonės (aš pagaliau). Aš palieku likusią mano atsakymo dalį.


Tokiu būdu vaizdų apdorojimas yra neveiksmingas. Geriau naudoti vieno matmens masyvus. Visi pikseliai apdorojami vienu ciklu. Atsitiktinę prieigą prie taškų galima atlikti naudojant:

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

Šiuo konkrečiu atveju geriau apskaičiuoti ir talpinti grupių trijų taškų sumą horizontaliai, nes jie naudojami tris kartus.

Aš atlikiau keletą bandymų ir manau, kad tai verta. Kiekvienas rezultatas yra penkių testų vidurkis.

Originalus vartotojo kodas 1615209:

 8193: 4392 ms 8192: 9570 ms 

Mistinė versija:

 8193: 2393 ms 8192: 2190 ms 

Du eigos, naudojant 1D masyvą: pirmasis leidimas horizontaliosioms sumoms, antrasis - vertikalios sumos ir vidutinis. Dviejų leidimų adresavimas tik su trimis rodikliais ir žingsniais:

 imgPointer1 =  imgPointer2 =  imgPointer3 =  for(i=SIZE;i<totalSize-SIZE;i++){ resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9; } 8193: 938 ms 8192: 974 ms 

Du eigos naudojant 1D masyvą ir adresuojami taip:

 for(i=SIZE;i<totalSize-SIZE;i++){ resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9; } 8193: 932 ms 8192: 925 ms 

Viena horizontaliosios talpyklos talpa yra tik viena eilutė į priekį, todėl jie lieka talpykloje:

 // 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 

Išvada:

  • Neįmanoma naudoti kelių rodyklių ir tiesiog priartinti (maniau, kad tai greičiau)
  • Horizontaliosios talpyklos yra geresnės nei kelis kartus.
  • Du leidimai yra ne tris kartus greičiau, bet du kartus.
  • Pasiekite 3,6 karto greičiau, naudodami vieną leidimą ir tarpinį rezultatą.

Esu tikras, kad tai galima padaryti daug geriau.

Pastaba Atkreipkite dėmesį, kad parašiau šį atsakymą, kad išsprendžčiau bendrąsias našumo problemas, o ne „Mystical Excellent Answer“ aprašytą talpyklos problemą. Iš pradžių tai buvo tik pseudokodas. Man buvo paprašyta atlikti bandymus komentaruose ... Čia yra visiškai atnaujinta versija su bandymais.

52
04 сент. Atsakymas pateikiamas bokanui 04. 2012-09-04 20:00 „12, 8 val. 2012-09-04 20:00

Prieigos prie elemento, kuris jį prižiūrėjo, eilės tvarka vis dar lieka mažai kabančių vaisių. Sukaupimas gali būti atliekamas taip, kad iteruojant į dešinę tik 3 naujos vertės turi būti atkurtos iš atminties ir sukauptos. Apgaulė yra žinoti, kaip pašalinti kairę stulpelį; pridedant naują stulpelį, prisiminkite jo vertę, kol ji išeina iš mėginio >

Kaina iki: 9 skaitymo, 9 papildymai, 1 skyrius Išlaidos po: 3 rodmenys, 3 papildymai, 1 skyrius

Pagalvokite apie mėginio >

Skirstymas yra didelės latencijos komanda, todėl gali būti naudinga slėpti vėlavimą, tačiau prieš pereinant ten, kompiliatoriaus išvestis turėtų būti patikrinta, jei atšaukimas pagal konstantą yra atšauktas, o jei kilpos išplečiama (kompiliatoriaus) jau daro tam tikrą vėlavimo kompensaciją.

Tačiau po drastiškiausio teisingo talpyklos naudojimo optimizavimo tai yra labai nedideli dalykai.

-1
11 окт. atsakymas duotas t0rakka 11 okt. 2017-10-11 15:08 '17, 15:08 2017-10-11 15:08

Peržiūrėkite kitus klausimus, susijusius su žymėmis, arba Užduokite klausimą