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

Question

我仍在学习 Julia 的多重分派和值即类型方法。实例化 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 无法预测对象的具体类型。所以它必须使用 runtime dispatch，这本质上是一个美化的字典查找。不幸的是，在这种情况下，键的比较比仅仅查找 Int 复杂得多。所以你失去了很多性能。

为什么只有两种方法会快很多？因为 Julia 试图变得非常聪明，它会检查有多少个；如果有 3 个或更少的方法，它将生成一些优化的代码来检查简单 if 分支中的类型，而不是调用类型交集的完整机制。您可以阅读更多详细信息 here.

Julia 的新手——一旦他们了解了专业化的奇迹以及它提供的运行时性能的巨大改进——通常会兴奋地尝试将类型系统用于一切，基于 Val 的调度通常是他们需要的工具。但是可推断性是多重分派速度优势的关键组成部分，因此当您使用破坏可推断性的设计时，您会失去优势，以至于它可能比不那么“花哨”的方法还要糟糕。

底线：对于您正在尝试的演示，如果您坚持 Dict，您的情况会好得多。在某些情况下，基于 Val 的调度很有用：通常，当单个运行时调度为您设置了一系列后续可推断的调用时，这可能是一个胜利。但是您应该明智地使用它，并且（正如您所做的那样）始终分析您的结果。

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

Julia Val{c}() seems slow compared to dictionnary lookup

performance

multiple-dispatch

julia