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

经常听到动态多分派性能很差的话语,甚至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

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

不论是 C++ 的虚函数还是 Rustdyn 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) 好像也没人说这样子很差呀,所以动态多分派性能差在哪儿呢?

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

完了完了我没有经常听到

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

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

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

:joy: 淦,不知道ValSplit.jl的做法为啥就性能提升了呢? :confused:

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

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

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

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

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

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 这样?

这点时间没啥影响。。。
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

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

2 个赞

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)
1 个赞

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

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

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

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

1 个赞

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

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 的输出值的类型就可以在编译期确定了。

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

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

2 个赞

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

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

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

2 个赞

各有特色呀属于是

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

备案号:京ICP备17009874号-2