R 中的尾调用优化不会重用堆栈框架

R 中的尾调用优化 (TCO)Tailcall()允许递归函数通过展开调用堆栈并从每次递归调用的全局环境开始来避免堆栈溢出。但是，与其他一些语言中的 TCO 不同，R 的实现不会重用相同的堆栈框架或将递归重写为循环。它仍然会以相同的次数调用递归函数，并且每次调用该函数时都会创建一个新的环境。这意味着虽然可以Tailcall()防止堆栈溢出，但可能不会显著提高性能。事实上，与实现相关的开销Tailcall()意味着它似乎比标准递归函数慢。

基准测试Tailcall()

为了公平起见，我们需要进行深度超过 48 次迭代的递归。让我们用 R 语言编写一个与 JavaScript 中递归求和函数等效的函数，什么

# Without tail recursion
recsum <- function(x) {
    if (x == 0) {
        return(0)
    } else {
        force(x) # to make benchmark fair
        return(x + recsum(x - 1))
    }
}

# With tail recursion
tailrecsum <- function(x, running_total = 0) {
    if (x == 0) {
        return(running_total)
    } else {
        force(running_total) # you have to force evaluation to trigger tail recursion
        Tailcall(tailrecsum, x - 1, running_total + x)
    }
}

让我们比较一下结果。为了增加最大递归深度，这是一个 R 会话，以

options(expressions = 5e5) # increase max recursion depth R option
bench::mark(recsum(4e3), tailrecsum(4e3), relative = TRUE)
#   expression         min median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time
#   <bch:expr>       <dbl>  <dbl>     <dbl>     <dbl>    <dbl> <int> <dbl>   <bch:tm>
# 1 recsum(4000)      1      1         2.11       NaN     1      469    27      427ms
# 2 tailrecsum(4000)  2.20   2.13      1          Inf     1.16   206    29      396ms

即使深度为4001（这大概是最大深度recsum()），TCO 版本的速度仍然大约是后者的两倍。这是怎么回事？关键在帮助页面上：

Tailcall由 traceback 或 sys.calls 生成的 [S]stack 跟踪将仅显示或指定的调用Exec，而不显示堆栈条目已被替换的前一个调用。

（重点是我的。）

该过程大致如下：

该图的关键点在于，虽然堆栈不会随着每次额外的函数调用而增长，但 R 不会对每次调用重复使用相同的堆栈框架。每次调用函数时，它都会展开堆栈并创建一个新环境。为了理解这种差异，让我们看一下 C 中的比较。

TCO如何呢？

我们用tailrecsum()C 语言来写：

uint64_t tailrecsum(uint64_t x, uint64_t running_total) {
    if (x == 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

如果我们编译它并gcc -O0将递归调用，即：

tailrecsum:
        push    rbp
        ; <some other instructions>
        call    tailrecsum

然而，如果我们使用优化方法进行编译O2，看起来就会有很大不同：

tailrecsum:
    mov     rax, rsi                  ; move 'running_total' into 'rax' (accumulator)
    test    rdi, rdi                  ; test if 'x' == 0
    je      .L5                       ; if 'x' == 0, jump to .L5 (base case)
    lea     rdx, [rdi - 1]            ; calculate x - 1 and store it in rdx for later use.
    test    dil, 1                    ; test if the least significant bit of 'x' is 1 (odd or even)
    je      .L2                       ; if even, jump to label .L2
    add     rax, rdi                  ; rax += x (accumulate the sum)
    mov     rdi, rdx                  ; x = x - 1
    test    rdx, rdx                  ; test if x == 0
    je      .L17                      ; if x == 0, jump to label .L17 to return
    ; Fall through to .L2

.L2:
    lea     rax, [rax - 1 + rdi * 2]  ; rax = rax - 1 + 2 * x
    sub     rdi, 2                    ; x = x - 2
    jne     .L2                       ; if x != 0, jump back to .L2 (loop)
    ; If x == 0, fall through to .L5

.L5:
    ret                               ; return from function

.L17:
    ret                               ; return from function

没有递归调用。编译器已将代码转换为循环。该函数不调用自身，因此仅使用一个堆栈框架。

R 的 TCO 不会将递归函数优化为循环

相反，即使如此Tailcall()，R 每次函数调用都会创建一个新的堆栈框架。我们可以通过编写一个 TCO 函数来计算环境的数量，从而观察到这一点：

tailrecsumenv <- function(x, running_total = 0, env_list) {
    if (x == 0) {
        return(
            list(
                result = running_total,
                n_environments = length(unique(env_list))
            )
        )
    } else {
        force(running_total) # force evaluation to trigger TCO
        force(env_list)
        Tailcall(tailrecsumenv, x - 1, running_total + x, append(env_list, environment()))
    }
}

如果我们运行它，我们可以看到它创建了4001环境：

tailrecsumenv(4e3, env_list = list(environment()))
# $result
# [1] 8002000

# $n_environments
# [1] 4001

Tailcall()那么在 R 中如何工作？

R显示了使用时所做的检查Tailcall()：

Rboolean jump_OK =
(R_GlobalContext->conexit == R_NilValue &&
    R_GlobalContext->callflag & CTXT_FUNCTION &&
    R_GlobalContext->cloenv == rho &&
    TYPEOF(R_GlobalContext->callfun) == CLOSXP &&
    checkTailPosition(call, BODY_EXPR(R_GlobalContext->callfun), rho));

它检查是否存在未决on.exit表达式、当前上下文是否为函数、闭包环境是否匹配、被调用的函数是否为闭包以及调用是否处于尾部位置。这些检查会产生一些开销。如果可以应用 TCO，它会执行以下操作（略微简化并附有我的注释）：

if (jump_OK) {
    // construct the first argument of `Tailcall()` into a function call
    SEXP fun = CAR(expr);
    // ensure function can be properly resolved
    fun = eval(fun, env);

    // package the function into a list containing...
    SEXP val = allocVector(VECSXP, 4);
    SET_VECTOR_ELT(val, 0, R_exec_token); // an execution token
    SET_VECTOR_ELT(val, 1, expr); // the expression to evaluate 
    SET_VECTOR_ELT(val, 2, env); // the environment in which to evaluate it
    SET_VECTOR_ELT(val, 3, fun); // the function to call

    // Jump back to the global environment
    R_jumpctxt(R_GlobalContext, CTXT_FUNCTION, val);
}

关键部分是R_jumpctxt()。这实际上将堆栈展开到全局环境，并用新函数调用替换当前函数调用。这意味着可以在不增加调用堆栈深度的情况下调用另一个函数。但是，与 C 示例中的 TCO 不同，每次递归调用都会Tailcall()导致创建一个新环境。

这相当于在调用递归函数之前从顶层函数返回。它允许深度递归而不会超过最大堆栈大小。但是，您不会获得与 C 代码中相同类型的优化。需要创建一个新环境，这是一个相对昂贵的操作。这些环境消耗堆上的内存，而不是调用堆栈上的内存，但它们不会立即被重用或删除。它们将继续增加内存，并会一直存在，直到垃圾回收。

那么如果Tailcall()速度较慢，意义何在？

公平地说，从来没有声称这Tailcall()更快：

这种尾调用优化的优点是不会增加调用堆栈并允许任意深度的尾递归。

虽然recsum()和在 R 之类的语言中tailrecsum()是一种荒谬的计算方式，但的优点是它确实可以防止深度递归导致的堆栈溢出：sum(1:4e3)Tailcall()

recsum(1e6)
# Error in force(x) : node stack overflow
tailrecsum(1e6)
# [1] 500000500000

Tailcall()是一种优化，因为它允许运行原本无法运行的代码。但它不会产生使用 TCO 的其他语言中看到的效率。R 仍然必须以与递归函数相同的方式创建环境。它还有额外的工作，因为运行Tailcall()需要解析代码以评估 TCO 是否合适，然后在进行下一个递归调用之前展开调用堆栈。因此，虽然Tailcall()可以防止调用堆栈无限增长，但不要指望它比不会导致堆栈溢出的标准递归函数更快。它不会。