julia - Julia 是如何实现多方法的？

Question

我读了一些 http://c2.com/cgi/wiki?ImplementingMultipleDispatch

我一直在寻找有关 Julia 如何实现多方法的引用资料时遇到了一些麻烦。调度的运行时复杂度是多少，它是如何实现的？

Answer 1

Dr. Bezanson's thesis无疑是目前描述 Julia 内部结构的最佳来源:

4.3 Dispatch system

Julia’s dispatch system strongly resembles the multimethod systems found in some object-oriented languages [17, 40, 110, 31, 32, 33]. However we prefer the term type-based dispatch, since our system actually works by dispatching a single tuple type of arguments. The difference is subtle and in many cases not noticeable, but has important conceptual implications. It means that methods are not necessarily restricted to specifying a type for each argument “slot”. For example a method signature could be Union{Tuple{Any,Int}, Tuple{Int,Any}}, which matches calls where either, but not necessarily both, of two arguments is an Int.²

本节继续描述类型和方法缓存、按特异性排序、参数调度和歧义。请注意，元组类型是协变的(与所有其他 Julian 类型不同)以匹配方法分派(dispatch)的协变行为。

这里最大的关键是方法定义是按特异性排序的，所以它只是一个线性搜索来检查参数元组的类型是否是签名的子类型。所以这只是 O(n)，对吧？问题是检查具有完全通用性的子类型(包括 Unions 和 TypeVars 等)很难。非常难，事实上。比 NP-complete 更糟糕的是，它估计为 ΠP2(参见 polynomial hierarchy)——也就是说，即使 P=NP，这个问题仍然需要非多项式时间!它甚至可能是 PSPACE 或更糟。

当然，它实际工作原理的最佳来源是 JuliaLang/julia/src/gf.c 中的实现。 (gf = 通用函数)。有一个 rather useful comment那里:

Method caches are divided into three parts: one for signatures where the first argument is a singleton kind (Type{Foo}), one indexed by the UID of the first argument's type in normal cases, and a fallback table of everything else.

因此，关于方法查找复杂性的问题的答案是:“这取决于。”第一次使用一组新的参数类型调用方法时，它必须通过线性搜索，寻找子类型匹配。如果它找到一个，它将专门用于特定参数的该方法并将其放入其中一个缓存中。这意味着在开始进行硬子类型搜索之前，Julia 可以对已经看到的方法执行快速相等性检查……并且由于缓存基于第一个参数存储为哈希表，因此需要检查的方法数量进一步减少。

但是，实际上，您的问题是关于调度的运行时复杂性。在这种情况下，答案通常是“什么调度？” — 因为它一直是 完全消除 ! Julia 将 LLVM 用作几乎提前的编译器，其中方法根据需要按需编译。在高性能 Julia 代码中，类型应该在编译时具体推断，因此也可以在编译时执行分派(dispatch)。这完全消除了运行时调度开销，甚至可能将找到的方法直接内联到调用者的主体(如果它很小)中，以消除所有函数调用开销并允许下游进一步优化。如果没有具体推断出类型，那么还有其他性能缺陷，而且我没有分析过通常在调度中花费了多少时间。有一些方法可以进一步优化这种情况，但可能首先要炸更大的鱼……而且现在通常最简单的方法是首先使热循环类型稳定。