何时在开罗智能合约中使用尾部调用优化-解网

问：

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

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

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

尾递归 Starknet 开罗朗

正如你所提到的，由于内存不可变，重用堆栈的通常尾部调用优化在开罗并不相关。在开罗，尾部调用递归的优点是，当被调用的函数返回时，你不需要对返回值做任何事情。这意味着在尾调用递归中，从内部调用返回只是一系列指令。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 个步骤：递归调用前 3 步（， push ，），2 步后（计算总和，）。“优化”的尾部调用版本也将花费每次迭代 5 个步骤：前 4 步和后 1 步。ifi-1call sumret

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

上一个：从 Next.js 加载着色器

下一个：使用 aiohttp（服务器）处理大文件上传的最佳方法是什么

何时在开罗智能合约中使用尾部调用优化

when to use tail call optimization in a cairo smartcontract

评论