Stream: helpdesk (published)

Topic: Defining skip condition with dispatch


view this post on Zulip Júlio Hoffimann (Jul 23 2023 at 21:51):

Say I have a loop like:

for i in 1:100000
  for j in 1:100000
    i <= j && continue # avoid double counting
    # do some actual work
  end
end

where the condition i <= j is used to skip the inner loop iterations. Is there any performance decrease to define this skip condition with dispatch?

skipfun(::MyType1) = (i, j) -> i <= j
skipfun(::MyType2) = (i, j) -> false

If I replace the literal i <= j in the loop by a call to these lambda functions, should I expect slow down or the compiler is good enough to cleanup the code? How would you investigate it further with existing Julia tools?

view this post on Zulip Mosè Giordano (Jul 24 2023 at 07:54):

Are you capturing i and j from outer scope? That could be a problem

view this post on Zulip Leandro Martínez (Jul 24 2023 at 08:51):

(deleted)

view this post on Zulip Leandro Martínez (Jul 24 2023 at 10:21):

On the other side, why not:

skipfun(::MyType1, i, j) = i <= j
skipfun(::MyType2, i, j) = false

to be used with, within the loop:

skipfun(MyType1(), i, j) && continue

That certainly has no signficant overhead relative to the conditional.

Or, if the conditional is already a problem (in the case it is unnecessary), define one iterator for each type, like:

julia> struct A end

julia> struct B end

julia> iter(::A,n,m) = Iterators.product(1:n,1:m)
iter (generic function with 2 methods)

julia> iter(::B,n,m) = Iterators.filter(pair -> pair[1] < pair[2], Iterators.product(1:n,1:m))
iter (generic function with 2 methods)

julia> for pair in iter(A(), 3, 3)
           @show pair
       end
pair = (1, 1)
pair = (2, 1)
pair = (3, 1)
pair = (1, 2)
pair = (2, 2)
pair = (3, 2)
pair = (1, 3)
pair = (2, 3)
pair = (3, 3)

julia> for pair in iter(B(), 3, 3)
           @show pair
       end
pair = (1, 2)
pair = (1, 3)
pair = (2, 3)

view this post on Zulip Júlio Hoffimann (Jul 24 2023 at 10:56):

Thank you all for the tips. I will proceed with the custom iterator approach, it is the most self-contained :+1:

view this post on Zulip Júlio Hoffimann (Jul 24 2023 at 10:56):

I wonder how I could inspect the actual code generated by the compiler and see that the iterators are compiled away?

view this post on Zulip Leandro Martínez (Jul 24 2023 at 11:09):

I don't think they are compiled away in any sense. The result should be very similar to the actual loops without and with the conditional. It may be more efficient in the case of the conditional to write an iterator that only runs over the upper diagonal elements instead of filtering.

view this post on Zulip Leandro Martínez (Jul 24 2023 at 11:10):

(I wouldn't bet filter is smart enough to do that)

view this post on Zulip Júlio Hoffimann (Jul 24 2023 at 11:50):

In case you want to give it a try, here is the code in question:

https://github.com/JuliaEarth/Variography.jl/blob/b1e401eb8514fad469d9514693412caf6f9cda9c/src/empirical.jl#L73

The skip function is retrieved with dispatch from two different algorithm types.

view this post on Zulip Leandro Martínez (Jul 24 2023 at 16:14):

I commented there. In that situation, first, I would just dispatch to differnet skip mehods depending on the type, without using a closure.


Last updated: Nov 22 2024 at 04:41 UTC