Imprimă pagina - parcurgere pe coloane

Titlul: parcurgere pe coloane
Scris de: Nicolae Titus din Decembrie 14, 2008, 16:54:02

programul ... face o parcurgere pe coloane, dureaza 0.21s. Daca inversez sa fie N 1000000 si M 10 dureaza 0.36s. de unde vine diferenta, nu face la fel de multe salturi si pentru matricea transpusa?

Cod:

#define M 1000000
#define N 10
int a[N][M];
int main ()
{long i,j;
 for (i=0;i<M;i++)
 {for (j=0;j<N;j++)
  {a[j][i]=1;
  }
 }
 return 0;
}

Titlul: RÄƒspuns: parcurgere pe coloane
Scris de: Flaviu Pepelea din Decembrie 14, 2008, 17:30:55

e bine sa pui totdeauna limita mai mica in fata ptr ca altfel spargi limita de cache foarte mult si costa timp

Titlul: RÄƒspuns: parcurgere pe coloane
Scris de: Florian Marcu din Decembrie 14, 2008, 19:36:09

Uita-te pe pontul #3 de aici (http://infoarena.ro/12-ponturi-pentru-programatorii-cc). :)

Titlul: RÄƒspuns: parcurgere pe coloane
Scris de: Nicolae Titus din Decembrie 14, 2008, 21:04:32

In primul caz matricea are 10 linii si 10^6 coloane, cand face parcurgere pe coloane cred ca sare din 10^6 in 10^6 locatii de memorie, iar in al doilea caz are 10^6 linii, 10 coloane si sare din 10 in 10 locatii de memorie.
Nu stiu cum functioneaza linia de cache, dar m-as astepta sa se strice la fel de rau in ambele cazuri, sau atunci cand sare din 10 in 10 sa mearga mai repede daca face prefetch la mai multe locatii secventiale.
Am observat ca parcurgerea pe linii(pt ambele matrici, normala si transpusa) dureaza aproximativ la fel de mult ca si cea pe coloane cand matricea are 10 linii si 10^6 coloane.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Nicolae Titus din Decembrie 14, 2008, 16:54:02