何时在cairo智能契约中使用尾调用优化

Question

我通常可以用一些不那么优雅的代码制作函数的终端递归版本。我应该这样做，因为它可以降低费用，还是我应该保持不优化的版本？

例如，这里有一个“未优化”函数，它对数组的元素进行求和：

@view
func get_convoy_strength{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(
    convoy_id : felt
) -> (strength : felt):
    alloc_locals
    let (convoyables_len : felt, convoyables : felt*) = get_convoyables(convoy_id)
    return _get_convoyables_strength(convoyables_len, convoyables)
end

下面是尾部调用优化：

func _get_convoyables_strength_tc{
    syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr
}(convoyables_len : felt, convoyables : felt*, sum : felt) -> (strength : felt):
    if convoyables_len == 0:
        return (sum)
    else:
        let convoyable_id = [convoyables]
        alloc_locals
        let (convoyable_strength) = _get_strength(convoyable_id)
        return _get_convoyables_strength_tc(
            convoyables_len - 1, convoyables + 1, sum + convoyable_strength
        )
    end
end

正如您所看到的，它不太友好，因为它需要一个额外的参数(始终为0)。在普通计算机上，这可以优化为不填充调用堆栈，但是正如FeedTheFed所指出的，内存在这里是不可变的，因此它似乎没有用。然而，他确实说过，“为了中间返回值而不浪费内存单元”，这可能是很有趣的。对我来说，有一个更详细的解释是很有帮助的，因为我不一定明白。

这里是与此相关的cairo文档：https://www.cairo-lang.org/docs/how_cairo_works/functions.html?highlight=tail#tail-recursion

Answer 1

简单地回答：的简单答案是:相对于访问存储和使用其他系统调用，一些额外的Cairo步骤的成本可能是可以忽略不计的，所以我从“非优化”版本开始，并且只有当函数使用Cairo步骤的时才尝试优化，而且它似乎对总体成本产生了很大的影响。

较长的答案：

正如您所提到的，重用堆栈的通常尾部调用优化与Cairo无关，因为内存是不可变的。Cairo中尾调用递归的优点是，当被调用的函数返回时，您不需要对返回值做任何事情。这意味着在尾调用递归中，从内部调用返回的只是一个ret指令序列。

另一方面，非尾调用递归(如示例中的递归)将具有处理内部调用返回值的指令，例如复制隐式参数和使用下一个元素计算当前结果的总和。

在一些(非常简单的)情况下，它不会比尾叫版本更糟糕。例如，考虑以下计算1 + 2 + ... + i的函数

func sum(i : felt) -> (res : felt):
    if i == 0:
        return (res=0)
    end
    let (partial_sum) = sum(i=i-1)
    return (res=partial_sum + i)
end

这个函数每次迭代要花费5个步骤:在递归调用(if，push i-1，call sum)之前3步，在2步之后(计算和，ret)。“优化”尾叫版本还将花费5个步骤，每次迭代:4步之前和1步后。

但这是一个非常简单的例子，没有隐含的参数，只有一个返回参数。如果我们添加一个隐式参数(即使它在函数中未使用)，尾调用版本的性能将更好:与非尾调用版本中的两个附加步骤相比，每次迭代只需增加一个步骤。在您的示例中，您有3个隐式参数，因此尾叫版本可能会更好(虽然，我猜它不会很重要，但这取决于其余代码)。