通过 Julia 中的递归调用减少 JIT 时间

Question

我有一个递归函数，它操作整数二叉树，实现为一对嵌套的对或整数。我的函数创建一棵具有不同结构的新树，并递归调用自身直到满足某些条件。我发现的问题是，第一次运行代码时，需要花费很长时间来 JIT 编译该函数的所有可能的签名；之后运行良好。

这是最小的工作示例：

my_tree = ((((6 => 7) => (6 => 7)) => ((7 => 7) => (0 => 7))) => (((8 => 7) => (7 => 7)) => ((8 => 8) => (8 => 0)))) => ((((2 => 4) => 7) => (6 => (0 => 5))) => (((6 => 8) => (2 => 8)) => ((2 => 1) => (4 => 5))))

function tree_reduce(tree::Pair)
    left, right = tree
    left isa Pair && (left = tree_reduce(left))
    right isa Pair && (right = tree_reduce(right))
    return left + right
end

@show my_tree
@show tree_reduce(my_tree)

using MethodAnalysis
methods = methodinstances(tree_reduce)
@show length(methods)

尽管这个示例在感觉上并不慢，但它仍然生成 9 个方法实例：

tree_reduce(::Pair{Pair{Pair{Int64, Int64}, Pair{Int64, Int64}}, Pair{Pair{Int64, Int64}, Pair{Int64, Int64}}})
tree_reduce(::Pair{Pair{Int64, Int64}, Pair{Int64, Int64}})
tree_reduce(::Pair{Int64, Int64})
tree_reduce(::Pair{Pair{Pair{Pair{Int64, Int64}, Int64}, Pair{Int64, Pair{Int64, Int64}}}, Pair{Pair{Pair{Int64, Int64}, Pair{Int64, Int64}}, Pair{Pair{Int64, Int64}, Pair{Int64, Int64}}}})
etc ...

有没有办法避免这种情况/预编译/加速/编写通用函数/在解释模式下运行特定（部分）函数？我准备让代码的整体性能稍微提高一些，使其在第一次顶级调用时运行得更快tree_reduce。

Answer 1

@nospecialize是一个选项，但我认为在这种情况下，一个单独的数据结构不捕获其类型的整个数据结构是合适的。 Pair实际上是针对强类型的事物，而不是针对大型嵌套结构。

\n

julia> abstract type BiTree{T} end\njulia> struct Branch{T} <: BiTree{T} \n           left::BiTree{T}\n           right::BiTree{T}\n       end\n\njulia> struct Leaf{T} <: BiTree{T}\n           value::T\n       end\n\njulia> Base.foldl(f, b::Branch) = f(foldl(f, b.left), foldl(f, b.right))\n\njulia> Base.foldl(f, l::Leaf) = f(l.value)\n\njulia> (\xe2\x86\x92)(l::Branch, r::Branch) = Branch(l, r) # just for illustration\n\xe2\x86\x92 (generic function with 1 method)\n\njulia> (\xe2\x86\x92)(l, r::Branch) = Branch(Leaf(l), r)\n\xe2\x86\x92 (generic function with 2 methods)\n\njulia> (\xe2\x86\x92)(l::Branch, r) = Branch(l, Leaf(r))\n\xe2\x86\x92 (generic function with 3 methods)\n\njulia> (\xe2\x86\x92)(l, r) = Branch(Leaf(l), Leaf(r))\n\xe2\x86\x92 (generic function with 4 methods)\n\njulia> my_tree = ((((6 \xe2\x86\x92 7) \xe2\x86\x92 (6 \xe2\x86\x92 7)) \xe2\x86\x92 ((7 \xe2\x86\x92 7) \xe2\x86\x92 (0 \xe2\x86\x92 7))) \xe2\x86\x92 (((8 \xe2\x86\x92 7) \xe2\x86\x92 (7 \xe2\x86\x92 7)) \xe2\x86\x92 ((8 \xe2\x86\x92 8) \xe2\x86\x92 (8 \xe2\x86\x92 0)))) \xe2\x86\x92 ((((2 \xe2\x86\x92 4) \xe2\x86\x92 7) \xe2\x86\x92 (6 \xe2\x86\x92 (0 \xe2\x86\x92 5))) \xe2\x86\x92 (((6 \xe2\x86\x92 8) \xe2\x86\x92 (2 \xe2\x86\x92 8)) \xe2\x86\x92 ((2 \xe2\x86\x92 1) \xe2\x86\x92 (4 \xe2\x86\x92 5))));\n\njulia> typeof(my_tree)\nBranch{Int64}\n\njulia> foldl(+, my_tree)\n160\n

\n

这还有一个优点，即您可以在没有破坏任何内容的危险的情况下重载其他方法，例如打印或索引。

\n