我一直在阅读http://c2.com/cgi/wiki?ImplementingMultipleDispatch
我一直在寻找有关 Julia 如何实现多方法的参考资料时遇到了一些麻烦。调度的运行时复杂度是多少，它是如何实现的？
问问题
1544 次
1 回答
21
Bezanson 博士的论文无疑是目前描述 Julia 内部结构的最佳来源：
4.3 调度系统
Julia 的调度系统与某些面向对象语言中的多方法系统非常相似 [17, 40, 110, 31, 32, 33]。然而，我们更喜欢术语基于类型的调度，因为我们的系统实际上是通过调度单个元组类型的参数来工作的。这种差异是微妙的，在许多情况下并不明显，但具有重要的概念意义。这意味着方法不一定限于为每个参数“槽”指定类型。例如，方法签名可以是
Union{Tuple{Any,Int}, Tuple{Int,Any}}，它匹配两个参数中的一个但不一定都是 Int 的调用。2
本节继续描述类型和方法缓存、按特异性排序、参数调度和歧义。请注意，元组类型是协变的（与所有其他 Julian 类型不同）以匹配方法分派的协变行为。
这里最大的关键是方法定义是按特异性排序的，所以它只是一个线性搜索来检查参数元组的类型是否是签名的子类型。所以这只是 O(n)，对吧？问题是检查具有完全通用性的子类型（包括 Unions 和 TypeVars 等）很难。非常难，事实上。比 NP-complete 更糟糕的是，它估计为 Π P 2（参见多项式层次结构）——也就是说，即使 P=NP，这个问题仍然需要非多项式时间！它甚至可能是 PSPACE 或更糟。
当然，它实际工作方式的最佳来源是JuliaLang/julia/src/gf.c中的实现（gf = 通用函数）。那里有一个相当有用的评论：
方法缓存分为三个部分：一个用于签名，其中第一个参数是单例类型 (
Type{Foo})，一个在正常情况下由第一个参数类型的 UID 索引，以及其他所有内容的后备表。
因此，关于方法查找复杂性的问题的答案是：“这取决于。” 第一次使用一组新的参数类型调用方法时，它必须经过线性搜索，寻找子类型匹配。如果它找到一个，它将专门用于特定参数的该方法并将其放入其中一个缓存中。这意味着在开始进行硬子类型搜索之前，Julia 可以对已经看到的方法执行快速相等性检查……并且由于缓存基于第一个参数存储为哈希表，因此需要检查的方法数量进一步减少。
但是，实际上，您的问题是关于调度的运行时复杂性。在这种情况下，答案通常是“什么调度？” ——因为它已经被彻底淘汰了！Julia 将 LLVM 用作几乎提前的编译器，其中方法根据需要按需编译。在高性能 Julia 代码中，类型应该在编译时具体推断，因此调度也可以在编译时执行。这完全消除了运行时调度开销，甚至可能将找到的方法直接内联到调用者的主体（如果它很小）中，以消除所有函数调用开销并允许下游进一步优化。如果没有具体推断出类型，那么还有其他性能缺陷，而且我没有分析过通常在调度中花费了多少时间。有一些方法可以进一步优化这种情况，但可能首先要炸更大的鱼……而且现在通常最简单的方法是首先使热循环类型稳定。
于 2015-08-21T19:38:56.993 回答