recursion - 使用Julia中的元编程优化递归函数

Question

遵循this answer的方法，我试图理解在metaprogramming概念范围内确切发生了什么以及表达式和生成的函数在Julia中的工作方式。

目的是使用表达式和生成的函数优化递归函数（对于具体示例，您可以查看上面提供的链接中回答的问题）。

考虑以下修改后的斐波那契函数，其中我要计算斐波那契数列直到n并将其乘以数字p。

直接，递归的实现将是

function fib(n::Integer, p::Real)
    if n <= 1
        return 1 * p
    else
        return n * fib(n-1, p)
    end
end

第一步，我可以定义一个函数，该函数返回一个表达式而不是计算值

function fib_expr(n::Integer, p::Symbol)
    if n <= 1
        return :(1 * $p)
    else
        return :($n * $(fib_expr(n-1, p)))
    end
end

例如返回类似

julia> ex = fib_expr(3, :myp)
:(3 * (2 * (1myp)))

这样，我得到一个完全展开的表达式，并且取决于分配给符号 myp的值。这样，我再也看不到递归了，基本上我在进行元编程：我创建了一个函数，该函数创建了另一个“函数”（在这种情况下，我们称其为表达式）。
我现在可以设置 myp = 0.5并调用 eval(ex)来计算结果。
但是，这比第一种方法要慢。

我能做的是，通过以下方式生成参数函数

@generated function fib_gen{n}(::Type{Val{n}}, p::Real)
    return fib_expr(n, :p)
end

神奇的是，调用 fib_gen(Val{3}, 0.5)可以完成任务，而且速度非常快。
那么发生了什么？

据我了解，在第一次调用 fib_gen(Val{3}, 0.5)时，参数函数 fib_gen{Val{3}}(...)被编译，其内容是通过 fib_expr(3, :p)获得的完全扩展的表达式，即 3*2*1*p用 p代替了输入值。
那么之所以这么快的原因是，因为 fib_gen基本上只是一系列乘法，而原始的 fib必须在堆栈上分配每个递归调用，这会使它变慢，对吗？

为了给出一些数字，这是我的简短基准 using BenchmarkTools。

julia> @benchmark fib(10, 0.5)
...
mean time: 26.373 ns
...

julia> p = 0.5
0.5

julia> @benchmark eval(fib_expr(10, :p))
...
mean time: 177.906 μs
...

julia> @benchmark fib_gen(Val{10}, 0.5)
...
mean time: 2.046 ns
...

我有很多问题：


为什么第二种情况这么慢？
::Type{Val{n}}的确切含义是什么？ （我从上面链接的答案中复制了该内容）
由于使用了JIT编译器，有时我会迷失在编译时和运行时所发生的事情，就像这里的情况一样。


此外，我尝试根据以下方法在单个函数中组合 fib_expr和 fib_gen

@generated function fib_tot{n}(::Type{Val{n}}, p::Real)
    if n <= 1
        return :(1 * p)
    else
        return :(n * fib_tot(Val{n-1}, p))
    end
end

但是这很慢

julia> @benchmark fib_tot(Val{10}, 0.5)
...
mean time: 4.601 μs
...

我在这里做错了什么？甚至可以在单个函数中组合 fib_expr和 fib_gen吗？

我意识到这更像是一本专着而不是一个问题，但是，尽管我几次阅读了 metaprogramming部分，但我还是很难掌握所有内容，尤其是在诸如此类的应用示例中。

Answer 1

回应的专着：

元编程基础

首先从“普通”宏开始会更容易。我将放松您使用的定义：

function fib_expr(n::Integer, p)
    if n <= 1
        return :(1 * $p)
    else
        return :($n * $(fib_expr(n-1, p)))
    end
end

这不仅允许传递 p的符号，例如整数文字或整个表达式。鉴于此，我们可以为相同的功能定义一个宏：

macro fib_macro(n::Integer, p)
    fib_expr(n, p)
end

现在，如果在代码中的任何地方使用 @fib_macro 45 1，则在编译时会先将其替换为长嵌套表达式

:(45 * (44 * ... * (1 * 1)) ... )

然后正常编译-常量。

实际上，这就是宏的全部内容。在编译时替换语法；并且通过递归，这可以是在编译​​和对表达式的函数求值之间任意长的更改。对于本质上是恒定的东西，但要另外写繁琐的事情，这非常有用：bood示例示例是 Base.Math.@evalpoly。

运行时评估？

但这有一个问题，即您无法检查仅在运行时才知道的值：您无法实现 fib(n) = @fib_macro n 1，因为在编译时， n是表示参数的符号，而不是可以分派的数字。

下一个最佳解决方案是使用

fib_eval(n::Integer) = eval(fib_expr(n, 1))

可以，但是每次调用都会重复编译过程-这比原始函数的开销大得多，因为现在在运行时，我们对表达式树执行整个递归，然后对结果调用编译器。不好。

方法分派和编译

因此，我们需要一种混合运行时和编译时间的方法。输入 @generated函数。它们将在运行时按类型分派，然后像定义函数体的宏一样工作。

首先关于类型调度。如果我们有

f(x) = x + 1

并有一个函数调用 f(1)，将发生以下情况：


确定参数的类型（ Int）
参考功能的方法表以找到最佳的匹配方法
方法主体是针对特定的 Int参数类型编译的，如果之前没有做过的话
根据具体参数评估编译后的方法


如果我们随后输入 f(1.0)，则将再次发生相同的情况，将基于相同的函数主体为 Float64编译新的不同的专用方法。

值类型和单例类型

现在，Julia具有独特的功能，您可以将数字用作类型。这意味着上面概述的调度过程也将在以下功能上起作用：

g(::Type{Val{N}}) where N = N + 1

有点棘手。请记住，类型本身就是Julia中的值： Int isa Type。

在这里， Val{N}是每个 N的正好具有一个实例的所谓单例类型，即 Val{N}()-就像 Int是具有许多实例的类型 0， -1， 1 ， -2，...。

Type{T}也是单例类型，其单个实例为 T类型。 Int是 Type{Int}， Val{3}是 Type{Val{3}}-实际上，这两个都是它们类型的唯一值。

因此，对于每个 N，都有一个类型 Val{N}，它是 Type{Val{N}}的单个实例。因此，将为每个 g调度并编译 N。这就是我们可以分配数字作为类型的方式。这已经可以进行优化：

julia> @code_llvm g(Val{1})

define i64 @julia_g_61158(i8**) #0 !dbg !5 {
top:
  ret i64 2
}

julia> @code_llvm f(1)

define i64 @julia_f_61076(i64) #0 !dbg !5 {
top:
  %1 = shl i64 %0, 2
  %2 = or i64 %1, 3
  %3 = mul i64 %2, %0
  %4 = add i64 %3, 2
  ret i64 %4
}

但是请记住，它要求在首次调用时为每个新的 N进行编译。

（如果您在体内不使用 fkt(::T)，则 fkt(x::T)只是 x的缩写。）

集成生成函数和值类型

最后要生成函数。它们是对上述调度模式的略微修改：


确定参数的类型（ Int）
参考功能的方法表以找到最佳的匹配方法
方法主体被视为宏，并以 Int参数类型作为参数进行调用（如果以前没有做过）。结果表达式被编译为方法。
根据具体参数评估编译后的方法


此模式允许更改分派函数的每种类型的实现。

对于我们的具体设置，我们希望分派表示斐波那契数列参数的 Val类型：

@generated function fib_gen{n}(::Type{Val{n}}, p::Real)
    return fib_expr(n, :p)
end

现在，您看到您的解释完全正确：


在第一次调用 fib_gen(Val{3}, 0.5)时，参数函数
fib_gen{Val{3}}(...)被编译，其内容是完整的
通过 fib_expr(3, :p)（即 3*2*1*p）获得的扩展表达式
用 p替换为输入值。


我希望整个故事也能回答您列出的所有三个问题：


使用 eval的实现每次都会复制递归，再加上编译的开销
Val是将数字提升为类型的诀窍，而 Type{T}仅包含 T的单例类型-但我希望这些示例对您有所帮助
由于JIT的原因，编译时间不是在执行之前，而是每次方法第一次被编译时，因为它被调用了。