何时在 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 指出的那样，内存在这里是不可变的，因此它似乎没有用。然而，他确实说过，“不为中间 return 值浪费内存单元”可能会很有趣。如果我不确定是否理解，请提供更详细的解释对我很有帮助。

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

Answer 1

简短的回答：相对于访问存储和使用其他系统调用，一些额外的开罗步骤的成本可能可以忽略不计，所以我将从“ non-optimized" 版本，仅当该函数使用大量开罗步骤时才尝试优化，这似乎会显着影响总体成本。

较长的答案：

正如您所提到的，由于内存不可变，通常的 tail-call 重用堆栈优化在 Cairo 中不适用。在 Cairo 中 tail-call 递归的优点是当调用函数 returns 时你不需要对 return 值做任何事情。这意味着在 tail-call 递归中，来自内部调用的 returning 只是一系列 ret 指令。

另一方面，非tail-call递归（如您示例中的递归）将包含处理内部调用的return值的指令，例如复制隐式参数并计算当前结果与下一个元素的总和。

在某些（非常简单的）情况下，它不会比tail-call版本差。例如，考虑以下计算 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 步：递归调用前 3 步（if、推送 i-1、call sum）和之后 2 步（计算总和，ret). “优化”tail-call 版本每次迭代也将花费 5 步：前 4 步和后 1 步。

但这是一个非常简单的案例，没有隐式参数，只有一个 return 参数。如果我们添加一个隐式参数（即使它未在函数中使用），tail-call 版本的性能会更好：与非 tail-call 版本中的 2 个额外步骤相比，每次迭代仅增加 1 个额外步骤。在您的示例中，您有 3 个隐式参数，因此 tail-call 版本可能会更好（尽管我猜它不会很重要，但这取决于代码的其余部分）。

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

when to use tail call optimization in a cairo smartcontract

tail-recursion

starknet

cairo-lang