performance - 与字典查找相比，Julia Val{c}() 似乎很慢

Question

我仍在学习 Julia 的多重分派(dispatch)和值作为类型的方法。
实例化 Val{c}() 似乎比字典查找慢 50 倍。
在那之后，调度似乎比字典查找快 6 倍。
这些持续时间是预期的吗？是否可以加快 Val{c}() 的实例化？

using BenchmarkTools

rand_n = rand([4,11], 1_000_000)

simple_dict = Dict(4 => 11, 11 => 4)
call_dict(num) = simple_dict[num]

@benchmark call_dict.($rand_n) # 42.113ms

val_type(::Val{4}) = 11
val_type(::Val{11}) = 4

@benchmark Val.($rand_n) # 2.4s

partial_result = Val.(rand_n)
@benchmark val_type.($partial_result) # 7ms

Answer 1

像这样的技巧可能很棒，但它们也可以带你进入危险的领域。当你只有 2 个 val_type 时，你会得到提升方法;重现你的结果，

julia> rand_n = [4, 11, 4]
3-element Vector{Int64}:
  4
 11
  4

julia> vrand_n = Val.(rand_n)
3-element Vector{Val}:
 Val{4}()
 Val{11}()
 Val{4}()

julia> val_type(::Val{4}) = 11
val_type (generic function with 1 method)

julia> val_type(::Val{11}) = 4
val_type (generic function with 2 methods)

julia> using BenchmarkTools

julia> @btime val_type.($vrand_n);
  28.421 ns (1 allocation: 112 bytes)

但是看看当你有 5 个时会发生什么:

julia> val_type(::Val{2}) = 0
val_type (generic function with 3 methods)

julia> val_type(::Val{3}) = 0
val_type (generic function with 4 methods)

julia> val_type(::Val{7}) = 0
val_type (generic function with 5 methods)

julia> @btime val_type.($vrand_n);
  95.008 ns (1 allocation: 112 bytes)

重要的是，我什至不必创建任何此类对象来观察减速。此外，这比您的 Dict 的固定版本要糟糕得多。基于方法:

julia> const simple_dict = Dict(4 => 11, 11 => 4)
Dict{Int64, Int64} with 2 entries:
  4  => 11
  11 => 4

julia> call_dict(num) = simple_dict[num]
call_dict (generic function with 1 method)

julia> @btime call_dict.($rand_n);
  39.674 ns (1 allocation: 112 bytes)

( const 至关重要，请参阅 https://docs.julialang.org/en/v1/manual/performance-tips/#Avoid-global-variables. )
为什么？关键是查看您正在使用的对象的类型:

julia> eltype(vrand_n)
Val

julia> isconcretetype(eltype(vrand_n))
false

这就解释了为什么它会很慢:当您的迭代提取下一个元素时，Julia 无法预测对象的具体类型。所以它必须使用运行时调度，这本质上是一种美化的字典查找。不幸的是，它的键比较比仅仅查找 Int 复杂得多。 .因此，您会损失很多性能。
当只有两种方法时，为什么速度会这么快？因为 Julia 试图变得非常聪明，它会检查有多少；如果有 3 个或更少的方法，它将生成一些优化的代码来检查简单的 if 中的类型分支而不是调用类型交集的完整机制。您可以阅读更多详情 here .
Julia 的新手——一旦他们了解了特化的奇迹和它带来的巨大运行时性能改进——通常会很兴奋地尝试将类型系统用于所有事情，并且 Val -based dispatch 通常是他们需要的工具。但是可推断性是多分派(dispatch)速度优势的关键组成部分，因此当您使用破坏可推断性的设计时，您会失去优势，以至于它可能比不太“花哨”的方法更糟糕。
底线:对于您正在尝试的演示，如果您坚持 Dict，您会做得更好。 .在某些情况下，基于 Val 的分派(dispatch)很有用:通常，当单个运行时分派(dispatch)为您设置一个完整的后续可推断调用序列时，这可能是一个胜利。但是您应该明智地使用它，并且(就像您所做的那样)始终分析您的结果。