Best approach for runtime dispatching inside a hot loop (heterogeneous tree structure)

General Usage Performance
3

Rather than relying on run-time dispatch, this could be an excellent use case for GitHub - yuyichao/FunctionWrappers.jl . Instead of dispatching on the object itself, you can just store a wrapper to the already-dispatched raycast method. For example:

struct Sphere
  r::Float64
end

struct Box
  s::Float64
end

function raycast(sphere::Sphere, point::Float64)
  sphere.r - point
end

function raycast(box::Box, point::Float64)
  box.s + point
end

geometries = [Sphere(1.0), Box(2.0)]

We can make a closure p -> raycast(g, p) for each geometry g and then
store that closure as a function wrapper:

using FunctionWrappers: FunctionWrapper

raycast_handles = [
    FunctionWrapper{Float64, Tuple{Float64}}(p -> raycast(g, p)) 
    for g in geometries
]

Now each element in raycast_handles is of the same type (FunctionWrapper{Float64, Tuple{Float64}}) but is still bound to its particular geometry. Calling the wrapped method should not incur any dynamic dispatch:

(tested in v0.6.2)

julia> function raycast_scene(handles, point)
         sum(h -> h(point), handles)
       end
raycast_scene (generic function with 1 method)

julia> raycast_scene(raycast_handles, 2.0)
3.0

julia> using BenchmarkTools

julia> @btime raycast_scene($raycast_handles, 2.0)
  20.159 ns (0 allocations: 0 bytes)
3.0

In your case, you can just store a function wrapper at each leaf of the tree. You can also store the geometry in an abstract field, since just having that field won’t create any dynamic dispatch unless your code actually uses it (and a little dynamic dispatch outside of the main loop is fine):

struct Leaf
  raycast_handle::FunctionWrapper{Float64, Tuple{Float64}}  # presumably not the actual input/output types you want
  geometry::AbstractGeometry
end

I also have the (unregistered) Interfaces.jl https://github.com/rdeits/Interfaces.jl/blob/master/demo.ipynb which might make this pattern easier.

3 Likes