Manual dispatch over a constant type set

General Usage Performance
1

I’m trying to run a simulation that has many different thermodynamic methods depending on the substance type (usually phase), and it’s nice to be able to easily choose what method to use. Long story short, I need to be able to call different thermodynamic function options at run-time based on a Substance type (basically a phase). They take the following form:

callfunc(T::DataType, x::ProcessStream)

The first argument that dispatches based on type (kind of like parse(Float64, str)).

I now built a fairly elaborate substance type system that works well with Julia’s dispatch system, but run-time dispatch can be slow, especially if I only need to consider root types or abstract phase classifications. Let’s say I want to write a “manual dispatch” function that runs on a list of stream types that changes once in a blue moon (making recompiling for every new list desirable). I’m considering the following options:

(1) Making a tuple type and dispatching on it. Here, I generate the list of types and create a Tuple with that type. I use that type as a dispatch argument, where the code runs on a for loop.

SUBSTANCE_TYPES = Tuple{root_types(Substance)...}
function stream_dispatch(callfunc::Function, x::ProcessStream, ::Type{typeList}=SUBSTANCE_TYPES) where typeList <: Tuple
    for T in typeList.parameters
        if x.subclass <: T
            return callfunc(T, x)
        end
    end
    #Retrun an error if x.subclass isn't in the SubstanceTypes
    error("Process Stream $(x.id) contains invalid \"class\": $(x.subclass) \n>> Hint: class must be one of [$(join($typeList,", "))]")
end

I’m wondering, is the compiler is smart enough to know that “fieldtypes(typeList)” is a constant at JIT compile time? Does it know that the loop can be unrolled?

(2) Another option would be to make this function a generated function to build the big “if statement” with a call to root_types(Substance) internally at compile time. Obviously this generated function would need to be rebuilt if the Substance type hierarchy changes. One concern is that generated functions must be pure, and this generated function would need a potentially impure function passed as an argument. Is this good practice if the passed function observes a mutable state?

(3) Use ManualDispatch.jl. The only thing I might worry about for this option is that I’m not sure if it compiles for each different tuple value going in, because in this application, that value doesn’t change much, if at all.

I’m trying to strike a balance between performance and maintainability. I know that using generated functions (option 2) has some issues, but is potentially very fast. However, I’m wondering how performance would compare with the type-dispatch function (option 1) that’s pretty simple and comes with much less baggage. I also know ManualDispatch.jl was built to handle this sort of thing, but can it take advantage of the fact that the type set rarely changes?

2

I’m having trouble figuring out exactly what your end goal is, so maybe I can start with a straw-man. If you are trying to apply a particular set of behaviors to your ProcessStream, then the simplest possible implementation would be something like:

julia> function f1(stream)
         println("doing f1 stuff")
       end
f1 (generic function with 1 method)

julia> function f2(stream)
         println("doing f2 stuff")
       end
f2 (generic function with 1 method)

julia> stream = "hello world"
"hello world"

julia> for f in (f1, f2)
         f(stream)
       end
doing f1 stuff
doing f2 stuff

Your approach of defining a type and then implementing callfunc for that type seems overly complicated–it ends up accomplishing nothing more than what you’d get by defining new functions instead of types, and putting the behavior you care about into the bodies of those functions. Of course, it’s possible that your type + callfunc makes sense in context–I just can’t tell from the info so far.

Note that this doesn’t solve the type stability problem: f1 and f2 have different types, so that for loop will be type-unstable. There are a lot of ways to solve that issue, but they depend a bit on how the information comes in. For example, are you expecting a user to pass in a tuple of stream types?

3

Here, a process stream x has a mutable field “subclass” which consists of a DataType which dictates the type of substance that “x” has. For example, let’s say that “callfunc” is “get_density”. There would be a function

function get_density(::Type{T}, x::ProcessStream) where T <: IdealLiquid
    #Liquid density code
end

If I wanted to use Julia’s run-time multiple dispatch I’d use

function get_density(x::ProcessStream)
    return get_density(x.subclass, x)
end

But this is potentially slow because x.subclass isn’t known at compile time which means that it needs to be dynamically dispatched. It would be nice to be able to a quick manual if-checking dispatch on type values for some list of substance classifications (probably about 10) and fill it in with a constant.

function get_density(x::ProcessStream)
    return stream_dispatch(get_density, x) #typeList is supplied set by default to SUBSTANCE_TYPES
end

This allows me to use special methods depending on the value of x.subclass. I can’t add a new type parameter to x that contains the subclass, because the subclass can change.

Now, I was thinking that if I had a Tuple type whose type signature matched the types I was looking for, I could use that as an argument into a stream_dispatch function (with the last argument as default)

function stream_dispatch(callfunc::Function, x::ProcessStream, ::Type{typeList}=SUBSTANCE_TYPES) where typeList <: Tuple
    for T in typeList.parameters
        if x.subclass <: T
            return callfunc(T, x)
        end
    end
end

Since typeList.parameters is a constant at compile time, T inside each iteration is also a constant which should allow for constant propagation over get_density(T, x) and bypass dynamic dispatch. But I’m not sure if the compiler would actually do this (and hence the potential need to write generated functions).

4

Ah, ok, that certainly makes things harder. If that weren’t a constraint in your design, you might consider something like the way RigidBodyDynamics.jl represents different types of robot joints with a generic Joint type which has a specialized JointType type parameter: https://github.com/JuliaRobotics/RigidBodyDynamics.jl/blob/0f42d2900174adc3c03911d217fd48a598c69bb8/src/joint.jl#L43-L47

As for your stream_dispatch, I think the idea is workable, but you might be better served by a lisp-y tuple recursion style, rather than a generated function. The basic idea is something like this:

julia> foo(x::Int) = println("got an int")
foo (generic function with 1 method)

julia> foo(x::Float64) = println("got a float")
foo (generic function with 2 methods)

julia> function call_for_each(f, args)
         f(first(args))  # Do something with the first element
         call_for_each(f, Base.tail(args))  # Recurse with the rest
       end
call_for_each (generic function with 1 method)

julia> function call_for_each(f, args::Tuple{})  
         # Base case for our recursion when nothing is left
       end
call_for_each (generic function with 2 methods)

julia> call_for_each(foo, (1, 2.0, 3, 4, 5.0))
got an int
got a float
got an int
got an int
got a float

This kind of approach is type-stable because the compiler is smart enough to figure out the type of the tail of a tuple:

julia> @code_warntype call_for_each(foo, (1, 2.0, 3, 4, 5.0))
Variables
  #self#::Core.Compiler.Const(call_for_each, false)
  f::Core.Compiler.Const(foo, false)
  args::Tuple{Int64,Float64,Int64,Int64,Float64}

Body::Nothing
1 ─ %1 = Main.first(args)::Int64
│        (f)(%1)
│   %3 = Base.tail::Core.Compiler.Const(Base.tail, false)
│   %4 = (%3)(args)::Tuple{Float64,Int64,Int64,Float64}
│   %5 = Main.call_for_each(f, %4)::Core.Compiler.Const(nothing, false)
└──      return %5

Note how the (%3)(args) has been inferred as a Tuple{Float64, Int64, Int64, Float64}, which is the type after the first element has been processed.

In your case, you have a tuple of types, and your foo() would be comparing the .subclass against each of those types, but I think the general idea could still work, and this completely avoids any need to worry about generated functions and the headaches they can create.

By the way, a totally different way to attack this problem would be to store FunctionWrappers from FunctionWrappers.jl. Those are just a slightly nicer wrapper around function pointers, and they can allow you to do something more like virtual methods in C++, although they come with the same set of performance issues that virtual functions in C++ have. I’ve done that in a few cases, although I generally find it not to be worthwhile.

3 Likes
5

Riiiight! I completely forgot about the recursion approach, probably because my background is MATLAB/Python more-so than Lisp. That’s actually quite elegant. I really should make recursion a bigger part of my design pattern toolbox. I can really appreciate how many design patters Julia is capable of.

1 Like
6

I got so curious that I figured I’d build all the solutions. After running some benchmarks over 1 million iterations (on a special case of the get_specific_volume function that returns a constant) I have the following results:

generated function runs at about 27 nanoseconds,
straight-up function call with dynamic dispatch runs at about 58 nanoseconds
recursive method runs at about 110 nanoseconds
for loop over constant svec runs at about 120 nanoseconds,

I’ve heard from other discussions that dynamic dispatch usually takes about 100 nanoseconds. The difference between the generated function (that explicitly writes the code) and the dynamic dispatch method seems to bear this out (but dynamic dispatch is a bit better than expected). Constant propagation doesn’t appear to happen in the for-loop case, it looks like dynamic dispatch is likely still being hit as there is only a performance DROP compared to raw dynamic dispatch. Results from the recursion method are about the same when compared against the for-loop method.