CODEWITHSUNDEEP
cperformance
Jainendra
Jainendra

Reputation: 25143

Which piece of code is more efficient?

For initialising all the elements of a 100×100 two-dimensional array, we can do it in two ways:

Method 1:

int a[100][100];
for(i=0; i<100; i++){
    for(j=0; j<100; j++){
        a[i][j] = 10;
    }
}

Method 2:

int a[100][100];
for(j=0; j<100; j++){
    for(i=0; i<100; i++){
        a[i][j] = 10;
    }
}

Now my question is which of the method is more efficient and why?

Upvotes: 0

Views: 159

Answers (5)

pranavk
pranavk

Reputation: 1845

It depends whether the language you are using is a row-major or a column-major. Anything in the memory is laid out always in one dimensional manner, so all the 2D stuff also get converted in 1D way. Now note that there are two ways to do so.

  1. i*(no. of elements in a row) + j where i is the row no. and j is the column no.

  2. i*(no. of elements in a column) + j where i is the column number and j is the row number.

So here first one is a row-major way of converting 2D array into 1D way and second one is a column major way. Languages like C/C++ are row-major so they follow the first way.

Now observe that in the first way, you have point, (0,0) and (1,0) very very far depending upon the number of elements in the row, but (0,0) and (0,1) are adjacent.

So as a final answer, your question depends on programming language whether it is a row-major programming language or column-major. In C/C++ as they are row-major so the first one will be faster.

Upvotes: 0

R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215183

I would suspect both loops to be the same speed, and in fact for the generated code to be identical. Unless the array is volatile, the compiler has the freedom to switch the loops, and it should switch them to whichever order is better for the target machine.

Upvotes: 1

Shahbaz
Shahbaz

Reputation: 47493

The C11 standard, section 6.5.2.1.3 indicates that arrays are stored row-major. This means that the first method is accessing memory sequentially, while the second one not. Depending on your CPU's caching mechanism, RAM access mechanism and the dimensions of the array, either could be faster. Generally though, I would say the first method is faster.

Upvotes: 2

janneb
janneb

Reputation: 37188

The first method, since that will access the array sequentially.

C stores 2-dimensional arrays in row-major order, meaning that a[i][j] will be adjacent to a[i][j+1] but not adjacent to a[i+1][j].

Yet another way to say the same thing (that generalizes to >2 dimensions) is that the rightmost index is adjacent in memory. Or that incrementing an index means that you have to jump past all the dimensions to the right of the index you're incrementing.

Upvotes: 8

Opera
Opera

Reputation: 983

When you declare an array like int a[100][100] its memory is laid out the same that if you declared int a[10000] which means that you can access all you cells successively if you just iterate on a.

The standard indicate that the array are stored by rows, which means your first hundred cells in memory will be a[0][0] to a[0][99] then a[1][0] to a[1][99].

On most CPUs, the first method will be faster since the CPU will be able to load (most of) your array into the CPU cache and therefore accessing it quickly. Note that this may vary between different CPUs.

Upvotes: 1

Related Questions