Summer training at Goeduhub Technologies-Jaipur
Register for Free Certified Workshop on AI & Machine Learning:: 02-02-2020 ||  Career options for aspiring CS/ITECEEE or EIC or EEE Engineers
0 like 0 dislike
16 views
in Tutorial & Interview questions by (6.7k points)

 Iterating through an array eciently and rowmajor order

1 Answer

0 like 0 dislike
by (6.7k points)
 
Best answer
Arrays in C can be seen as a contiguous chunk of memory. More precisely, the last dimension of the array is the contiguous part. We call this the row-major order. Understanding this and the fact that a cache fault loads a complete cache line into the cache when accessing uncached data to prevent subsequent cache faults, we can see why accessing an array of dimension 10000x10000 with array[0][0] would potentially load array[0][1] in cache, but accessing array[1][0] right after would generate a second cache fault, since it is sizeof(type)*10000 bytes away from array[0][0], and therefore certainly not on the same cache line. Which is why iterating like this is inefficient:

#define ARRLEN 10000

int array[ARRLEN][ARRLEN];

size_t i, j;

for (i = 0; i < ARRLEN; ++i)

{    

for(j = 0; j < ARRLEN; ++j)    

{        

array[j][i] = 0;    

}

}

And iterating like this is more efficient:

#define ARRLEN 10000

int array[ARRLEN][ARRLEN];

size_t i, j;

for (i = 0; i < ARRLEN; ++i)

{    

for(j = 0; j < ARRLEN; ++j)    

{        

array[i][j] = 0;    

}

}

In the same vein, this is why when dealing with an array with one dimension and multiple indexes (let's say 2 dimensions here for simplicity with indexes i and j) it is important to iterate through the array like this:

#define DIM_X 10

#define DIM_Y 20

int array[DIM_X*DIM_Y];

size_t i, j;

for (i = 0; i < DIM_X; ++i)

{    

for(j = 0; j < DIM_Y; ++j)    

{        

array[i*DIM_Y+j] = 0;    

}

}

Or with 3 dimensions and indexes i,j and k:

#define DIM_X 10

#define DIM_Y 20

#define DIM_Z 30

int array[DIM_X*DIM_Y*DIM_Z];

size_t i, j, k;

for (i = 0; i < DIM_X; ++i)

{    

for(j = 0; j < DIM_Y; ++j)    

{        

for (k = 0; k < DIM_Z; ++k)        

{            

array[i*DIM_Y*DIM_Z+j*DIM_Z+k] = 0;        

}    

}

}

Or in a more generic way, when we have an array with N1 x N2 x ... x Nd elements, d dimensions and indices noted as n1,n2,...,nd the offset is calculated like this
 Go to your Branch CSE or IT | ECE | EE, EIC or EEEMECE
 Know About Popular Colleges/Universities  List of IITsList of NITs | RTU-KOTA | Manipal University-Jaipur | JECRC University | Amity University Jaipur | BIT Mesra-Jaipur | MODY UNIVERSITY | LNMIIT-Jaipur | JK Lakshmipat | Banasthali Vidyapith | POORNIMA University
 Exams:   List of Exams After Graduation | List of Engineering Entrance Examinations (UG/PG) | JEE Main | JEE Advanced | GATE | IES | ISROList of PSUs
Placements:  List of companies | Logical Reasoning Questions | Quantitative Aptitude Questions | General English Questions | Technical-MCQ and Interview Questions
 Download Previous Year Papers For:  GATE | IES | RAJASTHAN TECHNICAL UNIVERSITY (RTU-Kota)RPSC Technical Exams | ISRO
 Online Free Training:  Artificial Intelligence(AI) & Machine Learning | Python Programming | Internet of Things-IoT | OpenCV (Open Source Computer Vision Library) | LINUX | Big Data : Hadoop | 
 Goeduhub
About Us | Contact Us   Social::   |  | 
...