maxval vs any... which is faster

[alexismor]

Hello,

I have an array of integers, and I want to check to see if any elements of this array are non-zero. Which would be faster

1) if (any(A)>0) then ...

2) if (maxval(A)>0) then ...

To find the maxval (or minval) of an array, does the Fortran program search through all of the array to find it? Is there a better way of finding out such a thing without searching through the whole array?

Thanks!

[Steven_L_Intel1]

Surely you mean

if (any(A>0)) then...

right? I would expect this to be faster than using maxval. In both cases, the compiled code has to traverse the array, but the per-element logic for the ANY case is much simpler (especially when the compiler needs to worry about NaNs and Infinities.)

Also, the tests you're proposing tell you if any element is greater than zero, not if any is non-zero.

[emc-nyc]

Just on the face of it, I would think ANY would be faster because -- say your vector looks like this

real,dimension(2**31 - 1) :: vector

vector() = 1.0
vector(1) = 0.0

maxval would have to traverse the entire array, but ANY could stop as soon as it gets to the first element greater than 0

i.e.,

any(vector > 0.0)

would only have to look at, on average, n/2 elements, but

maxval(vector) > 0.0

would have to look at all elements.

[alexismor]

Thanks for the replies.

I just made a dumb little timing test:

program test
integer, parameter :: dim=2**27
integer :: A(dim)
real*8 :: t1,t2
A=0
A(1)=3
call cpu_time(t1)
if (any(A/=0)) print*,'non-zero element!'
call cpu_time(t2)
print*,'time with ANY method is',t2-t1
call cpu_time(t1)
if (maxval(A)/=0) print*,'non-zero element!'
call cpu_time(t2)
print*,'time with MAXVAL method is',t2-t1
stop
end

Oddly enough, the MAXVAL is faster by a factor of ~1/3. I also tried putting the non-zero element at the very end and in the middle. In each case, MAXVAL is still faster...

Steve, I did mean any(A/=0) :). I was wondering why the ANY should search through the whole array. Like emc said, I would of thought that it would stop once the condition was fulfilled.

Alexis

Message Edited by alexismor on 09-07-2005 09:45 AM

Message Edited by alexismor on 09-07-2005 09:52 AM

[Zhanghong_T_]

Oh, it's interesting! I also got the same result. Whatever I check the 'optimization', the results are the same.

[greldak]

Thought there was a chance this may have been to do with paging so repeated the tests after

The ANY case does reduce a bit but still considerably longer than the MAXVAL case.

Also tried the difference between /= and >= and as expected the /= was slightly quicker for the ANY case but no different for the MAXVAL case (only one test for MAXVAL of course as opposed to every element for ANY)

Oh and still 3:2 ratio of times in CVF reduces to about 20% benifit for reals

Is there some hardware acceleration used in the MAXVAL case

[Steven_L_Intel1]

I have a guess. Note that ANY has you create a mask for the result. I think that the compiler does not look to optimize this case and does it the "simple" way, whereas MAXVAL is an operation that the compiler has special-case code for to optimize, since MAX/MIN operations are common.

[jim_dempsey]

There may be another way to speed up the process of making the determination by using the intrinsic function IOR (inclusive or)

do i=1,dim,4

if(ior(a(i), ior(a(i+1), ior(a(i+2), a(i+3)))) .ne. 0) exit

end do

(then test the remainder of the array if any)

In this manner you are not placing a result anywhere and you reduced the number of tests by 1/4. You can extend this to 8 elements per iteration.

Also, depending on your processor you might want to redefine the integer array to integer(8) inside the the subroutine, but keep integer(4) outside if that is what it was. Do more with less.

I will let you cleanup the code.

Jim Dempsey

[jim_dempsey]

Ran a test using IOR method

program Test2
integer, parameter :: dim=2**27
integer :: A(dim), i
real*8 :: t1,t2
A=0
A(1)=3
! test early occurance of non-zero
call cpu_time(t1)
if (any(A/=0)) print*,'non-zero element!'
call cpu_time(t2)
print*,'time with ANY method is',t2-t1
call cpu_time(t1)
if (maxval(A)/=0) print*,'non-zero element!'
call cpu_time(t2)
print*,'time with MAXVAL method is',t2-t1
call cpu_time(t1)
do i=1,dim,4
if(ior(a(i),ior(a(i+1),ior(a(i+2),a(i+3)))) .ne. 0) exit
end do
call cpu_time(t2)
print*,'time with IOR method is',t2-t1, 'i=', i
A(1)=0
A(dim)=3
! test late occurance of non-zero
call cpu_time(t1)
if (any(A/=0)) print*,'non-zero element!'
call cpu_time(t2)
print*,'time with ANY method is',t2-t1
call cpu_time(t1)
if (maxval(A)/=0) print*,'non-zero element!'
call cpu_time(t2)
print*,'time with MAXVAL method is',t2-t1
call cpu_time(t1)
do i=1,dim,4
if(ior(a(i),ior(a(i+1),ior(a(i+2),a(i+3)))) .ne. 0) exit
end do
call cpu_time(t2)
print*,'time with IOR method is',t2-t1, 'step=4, i=', i
call cpu_time(t1)
do i=1,dim,8
if(ior(a(i),ior(a(i+1),ior(a(i+2),ior(a(i+3),ior(a(i+4),ior(a(i+5),ior(a(i+6),a(i+7)))))))) .ne. 0) exit
end do
call cpu_time(t2)
print*,'time with IOR method is',t2-t1, 'step=8, i=', i

stop
end program Test2
---- output for test were non-zero value is at front ----
non-zero element!
time with ANY method is 0.531250000000000
non-zero element!
time with MAXVAL method is 0.187500000000000
time with IOR method is 0.000000000000000E+000 i= 1

--- output for test were non-zero value is at end
non-zero element!
time with ANY method is 0.531250000000000
non-zero element!
time with MAXVAL method is 0.187500000000000
time with IOR method is 0.171875000000000 step=4, i= 134217725
time with IOR method is 0.156250000000000 step=8, i= 134217721

The IOR method is fastest, and considerably faster when the non-zero entry is at the start of the array.

Jim Dempsey

[alexismor]

Hi Jim,

Thanks for the tip! Your IOR method is definitively faster.

Alexis