Julia如何实现多方法？

Question

我一直在阅读http://c2.com/cgi/wiki?ImplementingMultipleDispatch

我一直在寻找关于Julia如何实现多方法的参考.调度的运行时复杂性是什么,它是如何实现的？

Answer 1

Bezanson博士的论文无疑是目前朱莉娅内部描述的最佳来源:

4.3调度系统

Julia的调度系统非常类似于某些面向对象语言中的多方法系统[17,20,110,31,32,33].但是我们更喜欢基于类型的调度,因为我们的系统实际上是通过调度单个元组类型的参数来工作的.差异很微妙,在许多情况下并不明显,但具有重要的概念含义.这意味着方法不一定限于为每个参数"slot"指定一个类型.例如,方法签名可以是Union{Tuple{Any,Int}, Tuple{Int,Any}}匹配调用,其中两个参数中的任一个(但不一定是两个)都是Int.²

本节继续描述类型和方法缓存,按特异性排序,参数调度和模糊.请注意,元组类型是协变的(与所有其他Julian类型不同),以匹配方法调度的协变行为.

这里最大的关键是方法定义按特异性排序,因此它只是一个线性搜索来检查参数元组的类型是否是签名的子类型.那就是O(n),对吗？问题是检查完全通用的子类型(包括Unions和TypeVars等)很难.事实上,很难.比NP完全更糟的是,据估计是Π ^P ₂(见多项式层次) -也就是说,即使P = NP,这个问题仍将采取非多项式时间!它甚至可能是PSPACE或更糟.

当然,它实际工作原理的最佳来源是JuliaLang/julia/src/gf.c(gf =泛函)的实现.那里有一个相当有用的评论:

方法高速缓存分为三个部分:一个用于签名,其中第一个参数是单例类型(Type{Foo}),一个在正常情况下由第一个参数类型的UID索引,以及其他所有内容的回退表.

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

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