Can this loop be optimized further?

General Usage Performance
1

I have this function to find an element in an array:

function my_findfirst(element,array)
    	for i=1:length(array)
        	if @inbounds (array[i]==element)
			return i
		end
	end
	return nothing
end

I’ve created this function to make it faster than findfirst, and it is already faster for some types:

N=100_000_000
array=zeros(Float64,N)
array[N÷2]=1.0

#first time run to compile
findfirst(isequal(1.0),array)
my_findfirst(1.0,array)

@time findfirst(isequal(1.0),array)
#0.143356 seconds (6 allocations: 192 bytes)

@time my_findfirst(1.0,array)
#0.079413 seconds (5 allocations: 176 bytes)

But for UInt8 is much slower:

N=100_000_000
array=zeros(UInt8,N)
array[N÷2]=UInt8(1)

#first time run to compile
findfirst(isequal(UInt8(1)),array)
my_findfirst(UInt8(1),array)

@time findfirst(isequal(UInt8(1)),array)
#0.008938 seconds (6 allocations: 192 bytes)

@time my_findfirst(UInt8(1),array)
#0.046022 seconds (5 allocations: 176 bytes)

So I see that there is some room to optimize :wink:

Could you help me to make it faster please?

Thanks in advance!

2

Try avoiding global variables in the code you are benchmarking and try to use Benchmarktools for more accurate benchmarks.

1 Like
3

Don’t really think global or not will matter when the length is 100_000_000

Regarding the question, Base has a special implementation for the specific case of finding UInt8:

2 Likes
4

No it probably won’t matter much in this case, but will show misleading allocations. It’s at least good practice to avoid it.

5

Thanks for the advice and the fast response!
The original versión was inside a module and the results are similar.
I Will test with BenchmarkTools also :slight_smile:

6

Interesting… So possibly memchr is doing some clever low level tricks to be as fast…

I Will investigate :wink:

Thanks Kristoffer!

7

There is a global scope in the module as well. The variables have to be either constant or inside functions for you not to pay the prices of global access.

1 Like
8

I missunderstood this point…
Thank you for the clarificarion.

1 Like