parcurgere pe coloane

[•nicolaetitus12]

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

[•Pepelea_Flaviu]

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

[•Florian]

Uita-te pe pontul #3 de aici. 

[•nicolaetitus12]

    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.