Julia 是如何实现多重方法的？
How does Julia implement multimethods?
我读了一些 http://c2.com/cgi/wiki?ImplementingMultipleDispatch
我一直无法找到有关 Julia 如何实现多重方法的参考资料。 dispatch 的运行时复杂度是多少，它是如何实现的？
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.2
该部分继续描述类型和方法缓存、按特异性排序、参数调度和歧义。请注意，元组类型是协变的（与所有其他 Julian 类型不同）以匹配方法分派的协变行为。
这里最大的关键是方法定义是按特异性排序的，所以它只是一个线性搜索来检查参数元组的类型是否是签名的子类型。所以这只是 O(n)，对吧？问题是检查具有完全通用性的子类型（包括 Unions 和 TypeVars 等）很困难。很难，事实上。比 NP-complete 更糟糕的是，它估计是 ΠP2（见 polynomial hierarchy）——也就是说，即使 P= NP，这个问题仍然需要非多项式时间！它甚至可能是 PSPACE 或更糟。
当然，了解其实际工作原理的最佳来源是 JuliaLang/julia/src/gf.c (gf = generic function). There's a 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.
所以关于方法查找的复杂性问题的答案是："it depends."第一次使用一组新的参数类型调用方法时，它必须通过线性搜索，寻找子类型匹配。如果找到一个，它会专门针对特定参数使用该方法并将其放入其中一个缓存中。这意味着在开始硬子类型搜索之前，Julia 可以对已经看到的方法执行快速相等性检查……而且它需要检查的方法数量进一步减少，因为缓存存储为基于第一个参数的哈希表。
但是，实际上，您的问题是关于调度的 运行时 复杂性。在那种情况下，答案通常是 "what dispatch?" — 因为它已被 完全消除 ！ Julia 将 LLVM 用作几乎提前的编译器，其中方法在需要时按需编译。在高性能的 Julia 代码中，类型应该在编译时具体推断，因此分派可以 也 在编译时执行。这完全消除了运行时分派开销，甚至可能将找到的方法直接内联到调用者的主体（如果它很小）以消除所有函数调用开销并允许进一步优化下游。如果没有具体推断出类型，则会存在其他性能缺陷，而且我还没有剖析以查看通常在调度上花费了多少时间。有一些方法可以进一步优化这种情况，但可能有更大的鱼要先煎……现在通常最简单的方法是首先使热循环类型稳定。
我读了一些 http://c2.com/cgi/wiki?ImplementingMultipleDispatch
我一直无法找到有关 Julia 如何实现多重方法的参考资料。 dispatch 的运行时复杂度是多少，它是如何实现的？
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.2
该部分继续描述类型和方法缓存、按特异性排序、参数调度和歧义。请注意，元组类型是协变的（与所有其他 Julian 类型不同）以匹配方法分派的协变行为。
这里最大的关键是方法定义是按特异性排序的，所以它只是一个线性搜索来检查参数元组的类型是否是签名的子类型。所以这只是 O(n)，对吧？问题是检查具有完全通用性的子类型（包括 Unions 和 TypeVars 等）很困难。很难，事实上。比 NP-complete 更糟糕的是，它估计是 ΠP2（见 polynomial hierarchy）——也就是说，即使 P= NP，这个问题仍然需要非多项式时间！它甚至可能是 PSPACE 或更糟。
当然，了解其实际工作原理的最佳来源是 JuliaLang/julia/src/gf.c (gf = generic function). There's a 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.
所以关于方法查找的复杂性问题的答案是："it depends."第一次使用一组新的参数类型调用方法时，它必须通过线性搜索，寻找子类型匹配。如果找到一个，它会专门针对特定参数使用该方法并将其放入其中一个缓存中。这意味着在开始硬子类型搜索之前，Julia 可以对已经看到的方法执行快速相等性检查……而且它需要检查的方法数量进一步减少，因为缓存存储为基于第一个参数的哈希表。
但是，实际上，您的问题是关于调度的 运行时 复杂性。在那种情况下，答案通常是 "what dispatch?" — 因为它已被 完全消除 ！ Julia 将 LLVM 用作几乎提前的编译器，其中方法在需要时按需编译。在高性能的 Julia 代码中，类型应该在编译时具体推断，因此分派可以 也 在编译时执行。这完全消除了运行时分派开销，甚至可能将找到的方法直接内联到调用者的主体（如果它很小）以消除所有函数调用开销并允许进一步优化下游。如果没有具体推断出类型，则会存在其他性能缺陷，而且我还没有剖析以查看通常在调度上花费了多少时间。有一些方法可以进一步优化这种情况，但可能有更大的鱼要先煎……现在通常最简单的方法是首先使热循环类型稳定。