Which of the two programs are faster?

[jlmp]

Hello everyone!

I am trying to solve some exercises and i have this curious! exercise...

Which program is faster:

a)sum=0
do i=1, n
do j=1,m
sum=sum+a(i,j)
enddo
enddo

b) sum=0
do j=1,m
do i=1,n
sum=sum+b(i,j)
enddo
enddo

Does anybody knows this answer? In MHO these programs seem to run equal times but if you know that they do not, could you please explain me why?

Best Regards
jlmp

 

[xwb]

It depends on what sum, a and b are declared as.

If you know Fortran syntax, then you will know that a(i,j) could be either an array or a function call. If one is an array and the other is a function call, then the array would be faster.

The next bit is on array traversal. Arrays are stored as (1,1), (2,1), (3,1)...(1,2), (2,2) etc. In the first case the elements are not accessed sequentially - there is a jump of the array bound on every access. On the second, they are accessed sequentially so the optimizer could do the equivalent of

equivalence (flat(1),a(1,1))
sum = 0
do i = 1, m*n
   sum = sum + flat(i)
end do

If you know your Intel assembler, they could use the LODS and REPNZ array processing commands, which they can't use when the code jumps all over the array.

 

[ArkM]

By the way, with or w/o deep optimization, owing to the Fortran 2D array allocation rule (column-major form - that's a question, "columns then rows" traversal (case b) better (in theory uses memory cash mechanism...

See, for example:

http://www.obliquity.com/computer/fortran/array.html

 

[FJacq]

"columns then rows" traversal (case b) better (in theory uses memory cash mechanism...

Not only in theory : this is a practical issue for large matrices. A recent discussion with demonstrations (measurement) on that forum :

http://www.tek-tips.com/viewthread.cfm?qid=1643770

François Jacq

 

[ArkM]

Well, let's consider low-end CPU with 8-byte (or less) memory bus