动态多分派就一定很慢么？

[Junars]

经常听到动态多分派性能很差的话语，甚至ValSplit.jl专门把Val类型的分派变为 if else 以提升性能，但我不晓得为什么说动态多分派性能很差，而且我还经常用到动态多分派。
如以下会触发动态多分派的代码：

function f()
    a, b = take_two_types()
    dispatch(a, b)
end

dispatch(::Int, ::Int) = "Int - Int"
dispatch(::Int, ::Float16) = "Int - Float16"
dispatch(::Int, ::Float64) = "Int - Float64"
# ... more

这里面 a 和 b 的类型只有在运行时才能知道，因此用哪个 dispatch 函数得在运行时才能决定，这样性能会很差么？我是否需要改用模式匹配或者if else 以提升性能？

不论是 C++ 的虚函数还是 Rust 的 dyn Trait 都是可应对动态分派的情况，为什么在 Julia 里就要强调动态分派性能很差呢？难道是动态多分派性能很差？

又如社区经常会举的「类型不稳定」的例子：

function test()
    x = rand(Bool) ? 1 : 2.0   # type-unstable!!!
    process(x) 
end

process(::Float64) = "..."
process(::Int) = "..........."

如果这样性能也很差，那在 REPL 做个加减法岂不是性能也非常差？毕竟 REPL 不可能预测我会把什么拿过来做个加法，我可以 +(1, 2) 也可以 +(1.0, 2) 好像也没人说这样子很差呀，所以动态多分派性能差在哪儿呢？

[Rratic]

经常听到动态多分派性能很差的话语

完了完了我没有经常听到

不论是 C++ 的虚函数还是 Rust 的 dyn Trait 都是可应对动态分派

至少我听到C++强调虚函数性能很差

这里主要的问题在于「类型不稳定」吧

[Junars]

淦，不知道ValSplit.jl的做法为啥就性能提升了呢？

[johnnychen94]

soundof(animal::Symbol) = soundof(Val(animal))

这个是类型不稳定的，因为 Val{T} 里的 T 是什么取决于运行时的 animal 的值。类型不稳定的时候使用 if-else 手动派发会更高效。

[Junars]

那使用 function barrrier 的时候写的 kernel 函数情况呢，虽然没 if else 高效，会慢得很多么？这取决于什么呢？

[johnnychen94]

取决于你是否真的需要多重派发带来的可组合性和扩展性？另外，kernel 函数越大（需要的计算时间越多），类型不稳定的开销越不明显，所以也没有必要过于在意这一点。

[Junars]

不需要可组合性，我是图扩展方便。比如一个网页那么多的页面元素，你不知道用户会点击哪个，但是不管是什么元素都有一个响应函数，所以动态多分派很方便，我可不想维护一个大的switch table或者字典之类的。就是不知道动态多分派找到合适函数的时间在什么量级，如果在毫秒ms级的话，我就得必须if else这样手动派发了。

[johnnychen94]

julia> f() = rand() > 0.5 ? 1 : 0.0
f (generic function with 1 method)

julia> @btime sum(i->f(), 1:1000);
  4.977 μs (0 allocations: 0 bytes)

julia> f() = rand() > 0.5 ? 1 : 0
f (generic function with 1 method)

julia> @btime sum(i->f(), 1:1000);
  1.043 μs (0 allocations: 0 bytes)

4ns 这样？

[Junars]

这点时间没啥影响。。。
ValSplit.jl的这个benchmark是啥情况，我主要是被这个库的介绍吓的。。。

A small benchmark is provided here.
With 10 values to branch on, running Julia 1.6.1 on a Windows machine,
the results of the benchmark are as follows:

Manual switch statement:
3.275 μs (0 allocations: 0 bytes)
Global Dict{Symbol,String}:
78.800 μs (0 allocations: 0 bytes)
Global LittleDict{Symbol,String}:
111.600 μs (0 allocations: 0 bytes)
Dynamic dispatch:
2.300 ms (0 allocations: 0 bytes)
Val-splitting with @valsplit:
3.275 μs (0 allocations: 0 bytes

[N5N3]

用@descend看了下，这个例子里在调用add_sum时compiler还是进行了union split的（生成了4个调用）

[N5N3]

ValSplit.jl的benchmark中除去动态调用soundof的开销，还包括了构造Val的开销:

@btime Val($(:animal))
  71.414 ns (0 allocations: 0 bytes)

如果把这部分去除

println("Dynamic dispatch (no Val):")
vanimals = map(Val, animals)
@btime test(soundof, vanimals)
println("Dynamic dispatch:")
@btime test(soundof_dynamic, animals)
println("Val-splitting with @valsplit:")
@btime test(soundof, animals)

结果会好不少：

Dynamic dispatch (no Val):
  674.800 μs (0 allocations: 0 bytes)
Dynamic dispatch:
  1.528 ms (0 allocations: 0 bytes)
Val-splitting with @valsplit:
  3.487 μs (0 allocations: 0 bytes)

[johnnychen94]

确实… 我还在想 4ns 怎么样也有点太低了。实际 overhead 应该是在 50~100ns 左右.

ValSplit.jl 的这个benchmark是啥情况，我主要是被这个库的介绍吓的。。。

• ValSplit 的测试里构造了 10 个类型所以完全不会触发 union-split 优化. 如果改成只有 2 个类型的话性能差异也会小一些，但似乎也不会好到哪去。如果是 100 个类型的话差异也会更大。
• 类型不稳定会传播，所以每一个看起来 trivial 的函数调用都会产生一定的 overhead

但总之如果一定会有类型不稳定的话，尽量把 kernel 函数做的大一些，这样开销就可以忽略了。

[Junars]

话说isnothing不就是典型的动态分派的trivial function么？有专门优化？

[johnnychen94]

isnothing(::Any) = false
isnothing(::Nothing) = true

当我们谈类型稳定的时候，是在谈 “函数的中间结果的类型以及输出的类型是否可以仅根据输入的类型（而非输入的值）来决定”. isnothing 的输出类型一定是 Bool，这件事情无论输入类型是什么都是可以确定的。

---

相比而言，

struct True end
struct False end

f(x) = x ? True() : False()

这个函数的输出值的类型 取决于输入的值: 如果输入的值是 false 那么输出值的类型就是 False，反之为 True.

如果函数改一个方式写

g(::True) = True()
g(::False) = False()

那么 g 的输出值的类型就可以在编译期确定了。

[N5N3]

isnothing 本质上就是检查了一次变量的类型，用它做分支条件可以让Julia对不同代码块里的变量增加一些假设，这个对所有类型都是适用的。一个简单的例子：

f(x) = begin
    a = x[]
    a isa Nothing && return 1
    b = a;
    b isa Missing && return 2
    c = b;
    c isa Float64 && return 3
    d = c;
    return c
end

@code_warntype f(Ref{Union{Nothing,Missing,Int,Float64}}(1))
MethodInstance for f(::Base.RefValue{Union{Missing, Nothing, Float64, Int64}})
  from f(x) in Main at Untitled-1:9
Arguments
  #self#::Core.Const(f)
  x::Base.RefValue{Union{Missing, Nothing, Float64, Int64}}
Locals
  d::Int64
  c::Union{Float64, Int64}
  b::Union{Missing, Float64, Int64}
  a::Union{Missing, Nothing, Float64, Int64}
Body::Int64
1 ─       Core.NewvarNode(:(d))
│         Core.NewvarNode(:(c))
│         Core.NewvarNode(:(b))
│         (a = Base.getindex(x))
│   %5  = (a isa Main.Nothing)::Bool
└──       goto #3 if not %5
2 ─       return 1
3 ─       (b = a::Union{Missing, Float64, Int64})
│   %9  = (b isa Main.Missing)::Bool
└──       goto #5 if not %9
4 ─       return 2
5 ─       (c = b::Union{Float64, Int64})
│   %13 = (c isa Main.Float64)::Bool
└──       goto #7 if not %13
6 ─       return 3
7 ─       (d = c::Int64)
└──       return c::Int64

可以发现你每做一次判断后续变量的类型就更加"精确"。

[johnnychen94]

编译器总是比我想象的更聪明…

[thautwarm]

c++动态分派依靠虚表，一般用在single dispatch上。虚表要求是方法定义是封闭的，也就是在编译期能确定该类型的所有方法。julia多重分派随时添加新方法，不适用。

rust的trait，其机制叫做dictionary passing。该dictionary是一个结构体，里面存放函数指针，也就是一个类型在一个trait下能使用的所有方法。而rust每一个在trait上做抽象的函数，都会在调用点隐式地补全一个或多个dictionary。这个隐式补全叫做instance resolution，需要编译期静态类型检查，就不适用于julia了。

[Junars]

各有特色呀属于是

[N5N3]

@thautwarm

也就是在编译期能确定该类型的所有方法

从这个角度看的化, ValSplit.jl比较像传统静态编译的处理方法。（当有新增新的方法实例时，强制让compiler重新编译一个新的分派函数。）