何时在开罗SmartContract中使用尾巴调用优化

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指出的那样，这里的内存是不可变的，因此似乎没有用。但是，他确实说，对于“不浪费中间返回值的记忆单元”可能会很有趣。我不确定要了解一个更详细的解释对我来说非常有帮助。

这是与此相关的开罗文档：

Answer 1

简短的答案：相对于访问存储和使用其他系统调用，其他几个开罗步骤的成本可能可以忽略不计，因此我将从“未优化”版本开始，然后尝试尝试仅当功能使用大量的开罗步骤时，才能优化，并且似乎会显着影响整体成本。

答案越长：

，如您所提到的，由于不变的记忆，在开罗中，对堆栈的常规尾巴呼叫优化无关。
开罗尾声递归的优点是，当调用函数返回时，您无需使用返回值进行任何操作。这意味着在尾声递归中，从内部调用返回只是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递归调用之前（如果，请按）代码> i-1 ，<代码>调用sum ）和2之后（计算总和，ret）。 “优化”尾声版本还将在每次迭代中花费5个步骤：前4个步骤和后1步。

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