когда использовать оптимизацию хвостового вызова в смарт-контракте 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, память здесь неизменяема, поэтому она не кажется полезной. Однако он сказал, что это может быть интересно, чтобы «не тратить ячейки памяти на промежуточные возвращаемые значения». Мне было бы очень полезно получить более подробное объяснение, так как я не уверен, что понимаю.

Вот каирский документ, связанный с этим: https://www.cairo-lang.org/docs/how_cairo_works/functions.html?highlight=tail#tail-recursion

Answer 1

Краткий ответ: стоимость нескольких дополнительных шагов Cairo, вероятно, будет незначительной по сравнению с доступом к хранилищу и использованием других системных вызовов, поэтому я бы начал с «неоптимизированной» версии и попытался бы оптимизировать только в том случае, если функция использует много каирских шагов, и это, кажется, значительно влияет на общую стоимость.

Более длинный ответ:

Как вы упомянули, обычная оптимизация хвостового вызова для повторного использования стека не актуальна в Cairo из-за неизменяемой памяти. Преимущество рекурсии хвостового вызова в Cairo заключается в том, что когда вызываемая функция возвращает значение, вам не нужно ничего делать с возвращаемым значением. Это означает, что в рекурсии хвостового вызова возврат из внутренних вызовов представляет собой просто последовательность инструкций.

С другой стороны, рекурсия без хвостового вызова (например, в вашем примере) будет иметь инструкции, которые обрабатывают возвращаемые значения внутреннего вызова, такие как копирование неявных аргументов и вычисление суммы текущего результата со следующим элемент.

В некоторых (очень простых) случаях это будет не хуже версии с хвостовым вызовом. Рассмотрим, например, следующую функцию, которая вычисляет :

      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 до рекурсивного вызова ( , толкать , ) и 2 после (вычислить сумму, ). «Оптимизированная» версия с хвостовым вызовом также будет стоить 5 шагов за итерацию: 4 шага до и 1 шаг после.

Но это очень простой случай без неявных аргументов и только с одним возвращаемым аргументом. Если мы добавим неявный аргумент (даже если он не используется в функции), версия с хвостовым вызовом будет работать лучше: всего 1 дополнительный шаг на итерацию по сравнению с 2 дополнительными шагами в версии без хвостового вызова. В вашем примере у вас есть 3 неявных аргумента, поэтому версия с хвостовым вызовом, вероятно, будет лучше (хотя я предполагаю, что это не будет значительным, но это зависит от остального кода).