when to use tail call optimization in a cairo smartcontract

Question

I can often make a terminal recursive version of my functions with a little less elegant code. Should I do it because it could reduce the fees or should I keep the unoptimised version?

For example, here is an "unoptimised" function which sums elements of an array:

@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

and here is the tail call optimization:

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

As you can see it's a little less friendly because it requires an additional argument (which will always be 0). On a normal computer this could be optimized to not fill the call stack but as FeedTheFed pointed out, the memory is immutable here so it doesn't seem to be useful. He did say, however, that it could be interesting for "not wasting memory cells for the intermediate return values". It would be very helpful to me to have a more detailed explanation as I'm not sure to understand.

Here is the cairo doc related to this: https://www.cairo-lang.org/docs/how_cairo_works/functions.html?highlight=tail#tail-recursion

I've edited your tags. The `cairo` tag refers to the [cairo cross-platform graphics library](https://www.cairographics.org/), not the programming language. Please read at least the mouseover text of tags before adding them. — Jared Smith, May 20 '22 at 16:51

score 5 · Accepted Answer · answered Jun 03 '22 at 10:58

The short answer: the cost of a few additional Cairo steps is likely to be negligible relative to accessing storage and using other system calls, so I'd start from the "non-optimized" version and try to optimize only if the function uses a lot of Cairo steps and it seems to affect the overall cost significantly.

The longer answer:

As you mentioned, the usual tail-call optimization of reusing the stack is not relevant in Cairo because of the immutable memory. The advantage of a tail-call recursion in Cairo is that when the called function returns you don't need to do anything with the return value. This means that in a tail-call recursion, returning from the inner calls is just a sequence of ret instructions.

On the other hand, a non-tail-call recursion (like the one in your example) will have instructions that process the return values of the inner call, such as copying the implicit arguments and computing the sum of the current result with the next element.

In some (very simple) cases, it won't be worse than the tail-call version. Consider for example the following function that computes 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

This function costs 5 steps per iteration: 3 before the recursive call (if, push i-1, call sum) and 2 after (compute the sum, ret). The "optimized" tail-call version will also cost 5 steps per iteration: 4 steps before and 1 step after.

But this is a very simple case with no implicit arguments and only one return argument. If we add an implicit argument (even if it's unused in the function), the tail-call version will perform better: only 1 additional step per iteration compared to 2 additional steps in the non-tail-call version. In your example, you have 3 implicit arguments, so the tail-call version will probably be better (although, my guess is that it won't be significant, but this depends on the rest of the code).

when to use tail call optimization in a cairo smartcontract

1 Answers1