Given the following pseudocode: int array[1000, 10000]; for each element array[i

Question

Given the following pseudocode: int array[1000, 10000]; for each element array[i][j] {array[i][j] = array[i][j]*2;} Write two C programs that implement this algorithm; one should access the elements of the array in row-major order, and the other should access them in column-major order. Compare the execution times of the two programs. What does this tell you about the effects of memory layout on cache performance? [If you are a bit uncomfortable with C you can write a Java equivalent. You should be able to draw similar conclusions.] Why might a compiler perform the following optimization?/* Before */for (j =0; j

Explanation / Answer

#include <stdio.h>

int main(void) {
   int a[1000][1000];
   for(int i=0;i<1000;i++)
       for(int j=0;j<1000;j++) {
           a[i][j] = a[i][j]*2; //row-major
           a[j][i] = a[j][i]*2; //column-major
       }
   return 0;
}

In row-major rows are stored contiguously in memory, in column-major columns are stored contiguously in memory.

C arrays are stored in a contiguous by row major order. This means if you ask for element x, then element x+1 is stored in main memory at a location directly following where x is stored. So Row-major gives better performance.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.