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

when to use tail call optimization in a cairo smartcontract

我经常可以用不太优雅的代码制作我的函数的终端递归版本。我应该这样做是因为它可以减少费用还是我应该保留未优化的版本?

例如,这是一个对数组元素求和的“未优化”函数:

@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

简短的回答:相对于访问存储和使用其他系统调用,一些额外的开罗步骤的成本可能可以忽略不计,所以我将从“ 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-1call sum)和之后 2 步(计算总和,ret). “优化”tail-call 版本每次迭代也将花费 5 步:前 4 步和后 1 步。

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