CODEWITHSUNDEEP
arraysstridecache-locality
Agapi
Agapi

Reputation: 77

What is the difference in the Code Snippets?

I am a beginner in operating systems, and I am trying to understand some code snippets. Can you please explain to me the difference between these code snippets?? 

int sum_array_rows(int a[M][N])
 {
    int i,j,sum=0;
    for(i=0;i<M;i++)
      for(j=0;j<N;j++)
        sum+=a[i][j];
    return sum;
  }

and

int sum_array_col(int a[M][N])
 {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[i][j];
    return sum;
  }

The different parts are the double For attributes Is one of them supposed to be faster than the other?? If so can you please explain to me why, because I don't understand.

Upvotes: 0

Views: 391

Answers (3)

Achal
Achal

Reputation: 11921

Both the codes works similar only if M and N values are equal otherwise both code blocks are different.

Case-1 :- Look at the below code block

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<M;i++)
      for(j=0;j<N;j++)
        sum+=a[i][j];
    return sum;
}

here a is an array of M rows and N columns & You are doing sum of each row-column element by sum+=a[i][j]. That's a fine code because outer loop rotates equal to number of rows and inner loop rotates equal to number of columns.

Case-2 :- Now Look at the second code block, it causes overflow.

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[i][j];
    return sum;
}

Here also a is an array of M rows and N columns. your first outer for loop rotate from 0 to N but you have only M rows. And when you do sum+=a[i][..] it creates a big problem if M & N are not same.. For e.g M is 2 and N is 5 i.e its like int a[2][5] and outer loop iterates from 0 to 5 and you keep on doing

  • sum+=a[0][j] then

  • sum+=a[1][j] till this its fine(bcz M=2), but when it will do

  • sum+=a[2][j] and sum+=a[3][j] etc then there is a problem as there is no a[2][j] or a[3][j] exits so you are trying to access out of boundary which causes undefined behavior.

So Above two code blocks are same only if M and N are same, otherwise both are different.

First of all second code block is wrong, but you can correct it by doing sum+=a[j][i] instead of sum+=a[i][j] as 

int sum_array_rows(int a[M][N]) {
    int i,j,sum=0;
    for(i=0;i<N;i++)
      for(j=0;j<M;j++)
        sum+=a[j][i];
    return sum;
}

As told by others due to the memory layout of a 2D arrays and the way cache system works, the first version may perform better than the second. On the other hand, the compiler may optimize the two versions to perform equally.

Upvotes: 0

4386427
4386427

Reputation: 44339

In the first example:

i will get the values 0, 1, 2, ..., M-1

j will get the values 0, 1, 2, ..., N-1

So sum is calculated as

sum = a[0][0] + a[0][1] + a[0][2] + ... + a[0][N-1] +
      a[1][0] + a[1][1] + a[1][2] + ... + a[1][N-1] +
      a[2][0] + a[2][1] + a[2][2] + ... + a[2][N-1] +
      ...
      ...
      a[M-1][0] + a[M-1][1] + a[M-1][2] + ... + a[M-1][N-1]

In the second example this has been switched so that

i will get the values 0, 1, 2, ..., N-1

j will get the values 0, 1, 2, ..., M-1

so now

sum = a[0][0] + a[0][1] + a[0][2] + ... + a[0][M-1] +
      a[1][0] + a[1][1] + a[1][2] + ... + a[1][M-1] +
      a[2][0] + a[2][1] + a[2][2] + ... + a[2][M-1] +
      ...
      ...
      a[N-1][0] + a[N-1][1] + a[N-1][2] + ... + a[N-1][M-1]

Notice that the second version is wrong because the argument is int a[M][N], i.e. legal first index is 0..M-1 and legal second index is 0..N-1 In other words, if N and M differs the second version access the array out of bounds.

To make the second example correct. This line sum+=a[i][j]; should be sum+=a[j][i]; so that sum is now:

sum = a[0][0] + a[1][0] + a[2][0] + ... + a[M-1][0] +
      a[0][1] + a[1][1] + a[2][1] + ... + a[M-1][1] +
      a[0][2] + a[1][2] + a[2][2] + ... + a[M-1][2] +
      ...
      ...
      a[0][N-1] + a[1][N-1] + a[2][N-1] + ... + a[M-1][N-1]

With that change the two version are functionally identical, i.e. produce the same result. They only differ in the order that the elements are added.

Due to the memory layout of a 2D arrays and the way cache system works, the first version may perform better than the second. On the other hand, the compiler may optimize the two versions to perform equally.

Upvotes: 1

Paul Humphreys
Paul Humphreys

Reputation: 338

As others have said, the second code snippet can cause an overflow error if the array dimensions are not the same, so this issue would need to be fixed.

However looping over the last array dimension in the inner-most loop can be faster than otherwise, due to how the elements of multidimensional arrays are stored in memory and the caching architectures of modern CPUs.

The terms to search for here are 'cache locality' and 'stride of arrays'

Upvotes: 2

Related Questions