Finding a value in an unordered Fortran array

I have been optimizing some Fortran code that involved searching for an integer value in an unordered array (we know the value occurs only once).  Since there is no intrinsic procedure to accomplish this, I thought I’d try a couple of approaches to see which was fastest.  The simple answer is that, in this case, brute force beats elegance, even when the target value is near the end of the array. Download the full example from GitHub

Method 1: Brute force

Algorithm: use a do loop to iterate through the array until you find the target value.  Exit the loop when you find the value.

do i = 1, num_elements
    if (array1(i) .eq. target_value) then
        loc = i
        exit
    endif
end do

Results: CPU time required my PC: 0.048 sec

Method 2: forall

Algorithm: use a forall loop to compute the absolute value of the difference between the target value and each value in the array, and store the result in a temporary array.  Then use the minloc intrinsic procedure to return the index of the minimum value of the temporary array.

forall (i=1:num_elements) array2(i) = abs(array1(i) - target_value)
loc = minloc(array2, 1)

Results: CPU time 0.248 seconds

Method 3: Intrinsic Procedures

Algorithm: use a standard arithmetic operator to compute the difference between each element of the array the the target value, use the abs procedure to compute the absolute value, and use the minloc procedure to find the index of the minimum element.

loc = minloc(abs(array1 - target_value), 1)

Results: CPU time 0.172 seconds

Conclusions

Although the third method appears to be the most elegant, it is quite slow.  A simple for loop is orders of magnitude faster, even when it is “penalized” by searching for a value near the end of the array.  This is very different from Python (especially NumPy arrays), where it is generally much faster to use NumPy functions than to iterate over arrays.

Comments

Comment #1 by Matthew Perkins

Matthew Perkins - Aug 2, 2011

Do you find that using different optimization flags changes the timing much?

Comment #2 by craig

craig - Aug 2, 2011

I didn’t try changing the compiler flags. I am pretty sure the compiler is optimizing the do loop–otherwise, it would run much slower. It might be interesting to disable optimization altogether and see if the results change.

Comment #3 by Lorenzo (Italy)

Lorenzo (Italy) - May 3, 2012

Thank you!

Comment #4 by zmi

zmi - Jul 5, 2013

and what if array doesn’t contain x at all? only the first one gives correct answer if you init loc to some ‘zero’ value.

Comment #5 by Juanlu001

Juanlu001 - Dec 5, 2015

How is this even possible? :O

Comment #6 by Juanlu001

Juanlu001 - Dec 5, 2015

Trying with ifort on Linux, with `-O2` to `-O5` the time is the same, but with `-O1` or `-O0` the brute force loop is the fastest. Interestingly, the `forall` approach doesn’t even change with any optimization and is consistently the slowest.

Comment #7 by Craig

Craig - Dec 6, 2015

I suspect that the built-in function minloc is the limiting factor for the second and third methods. Since this function is pre-built, compiler flags have no effect. Further, since the foreach construction tells the compiler that the loop can be performed in parallel, optimization flags have no effect on foreach. Compilers and processors have become so sophisticated that it can be counter-productive to manually optimize code. It’s best to write the code in a way that makes its purpose clear to the compiler.

Comment #8 by Kyle Brown

Kyle Brown - Feb 2, 2019

Very helpful thanks, is there any difference seen between using the minloc() function and the findloc() function? (using intel fortran) I will be using method 1 anyway if it’s that much faster!