How to dispatch by value?

Very beginner question about using “where” in function declaration.

Is it possible to do something like this?

function p(c::Structure) where c.id == :x   
    do something now I know c.id == :x
end
function p(c::Structure) where c.id == :y 
    do something now I know c.id == :y
end

Of course I did try and no it can’t be done… so basically asking what can be done to emulate multiple dispatch by value.

The following is obvious and trivial BUT I’d like to modularize by putting each function f in its own file, which can’t be done by this monolithic approach.

function p(c::Struct)
    if c.id == :x 
        do something
    elseif c.id == :y
        do something else
    end
end

Defining Structure as abstract, and have subtypes like

StructureX <: Structure
StructureY <: Structure
...

will need a lot of such subtypes in my intended use case.

Parametric types would be one solution:

julia> struct Foo{T} end

julia> f1=Foo{1}()
Foo{1}()

julia> function use_foo(f :: Foo{1}); println("1"); end
use_foo (generic function with 1 method)

julia> function use_foo(f :: Foo{2}); println("2"); end
use_foo (generic function with 2 methods)

julia> use_foo(f1)
1
3 Likes

Probably, the already mentioned solution of parameterizing Structure, so that the symbol goes to the type signature, is “the best” for this case:

p(c::Structure{:x}) = ⟨code for x⟩
p(c::Structure{:y}) = ⟨code for y⟩

But that approach is not recommended unless the options, for the most part, can be resolved at compile time(see https://docs.julialang.org/en/v1/manual/performance-tips/#The-dangers-of-abusing-multiple-dispatch-(aka,-more-on-types-with-values-as-parameters)-1).

If Structure is already defined then this would work too

# using multiple dispatch
function p(::Structure)
  p(Val(c.id))
end

p(::Val{:x}) = "it is :x"

p(::Val{:y}) = "it is :y"

The potential reservation I have is I do not know how performant it is. I heard that sometimes dispatching on Val is “slow”.

1 Like

Thanks for all the replies. May I ask how bad the performance is?

e.g.

struct Expr{id} end

f(c::Expr{:a}) = println("a")

f(c::Expr{:b}) = println("b")
... say 100 of them ...

f(x)

If it f(x) cannot be determined at compile time, the worst is a linear search, no more worse than the monolithic if…elseif… right? Such as

if id == :a 
    do this
elseif id == :b
    do that
... 100 of these ...

It will be much worse in the constant factor. If you have a branch, you should just use a branch. You shouldn’t use dispatch just because you want to use it…

4 Likes

You can use BenchmarkTools.jl

using BenchmarkTools

@benchmark f(c)

Are you referring to extra compile time or is there another reason why using dispatch to branch would be slower?

If the dispatch happens at runtime (which it often will if you’re dispatching on a dynamic value), it can easily be on the order of milliseconds.

Could you give an example of how it could take milliseconds?

There seems to be no overhead with a trivial example:

julia> struct S{T}
       end

julia> f(x::S{1}) = true
f (generic function with 1 method)

julia> f(x::S{2}) = false
f (generic function with 2 methods)

julia> @btime f(S{1}())
  0.020 ns (0 allocations: 0 bytes)
true

julia> @btime f(S{2}())
  0.020 ns (0 allocations: 0 bytes)
false

EDIT:
I guess that’s too trivial. I do see the difference here:

julia> g(x) = x == 1
g (generic function with 1 method)

julia> @btime f(S{rand(1:2)}())
  175.926 ns (0 allocations: 0 bytes)
false

julia> @btime g(rand(1:2))
  7.090 ns (0 allocations: 0 bytes)
true

Not milliseconds, but significant. What’s the cause of the difference?

1 Like

If you instead time it with @btime f(S{rand(Bool) + 1}()), it goes up to 3 microseconds. More complicated (multivariable or more methods) can get exponentially harder.

Is there anyway to see what’s causing the overhead? @code_native doesn’t seem to show the calculations done for type parameters:

julia> @btime f(S{rand(Bool) + 1}())
  169.373 ns (0 allocations: 0 bytes)
false

julia> @code_native f(S{rand(Bool) + 1}())
        .text
; ┌ @ REPL[2]:1 within `f'
        movb    $1, %al
        retq
        nopw    %cs:(%rax,%rax)
; └

What’s causing the overhead is picking which function to run, not running the function itself. The slow part is method ordering stuff way deep in base Julia that is in the worst case exponential in the number of arguments (although there are faster paths).

2 Likes

Thanks. That makes sense. I found some further discussion here:
https://docs.julialang.org/en/v1.6-dev/manual/performance-tips/#The-dangers-of-abusing-multiple-dispatch-(aka,-more-on-types-with-values-as-parameters)-1

EDIT: Should have read the thread more carefully. That link has already been helpfully posted. Sorry for the noise.

Oscar,

Exponential is like 2^n, much worse than say n^3

It doesn’t “feel” like this type of algorithm needs exponential time to achieve. But I am no expert. Just a gut feeling.

If you have K types and N arguments, you have K^N possible type tuples, no?

1 Like

I have a feeling that the discussion is losing track of the original question.

The OP required that the methods that handle each case should be in different files. (Why?) That would seem to rule out the obvious if ... elseif approach.

Figuring out the optimal approach then requires a bit more information.

  • How many distinct values for id are there?
  • Is dispatch performance likely a big deal or not? I.e., does the “do something” part take a long time or not?
  • Should a user be able to extend the set of id values. Or can that be hard-wired in a single function (as in the if ... elseif case)?
  • Is the value of id set in a way that allows the compiler to infer, say, a parametric type? Or is it, say, loaded from a file and therefore dynamic dispatch is inevitable?

I think it will be hard to give useful advice without this information.

The OP dislikes the option of defining concrete sub-types for each id value. I wonder why. Given that a separate method needs to be written for each id, adding one line that defines a StructureX concrete type would seem to add little work.

1 Like

No. It’s perfectly fine to call other functions in the branch.

If you have K types and N arguments, you have K^N possible type tuples, no?

I’d like to start another thread to discuss this. This is very interesting. But Hendri54 was right. This is a sidetrack from original question. I’ll answer Hendri54 next.

Sorry I was very unclear. I was assuming that the files were not available to be simply included when the dispatch function is compiled (either because the set of ids is not known ex ante or because they are in a different module written later). But perhaps I am reading too much between the lines.