NEWTON
Asked
8 months ago
24
views
0
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
ㅤ This question was originally posted on Stack Overflow
0
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).
ㅤ This answer was originally posted on Stack Overflow
answered
8 months ago
How to make recursive function in Cairo Lang?
How to use get_fp_and_pc in Cairo Lang?
How can I pass an array of felt to call with Nile in StarkNet?
Are you able to nest mappings in Cairo like you can in Solidity?
Cairo Lang / StarkNet: What are Revoked references? What is alloc_locals?
storage for array
Will it be possible to invoke functions from within the loops in Cairo 1.0?
how to send token
Does anyone know a vim plugin for StarkNet smart contracts?
Is there any other way to do 2**n without using pow.cairo?
Error when deploying Cairo: [WARNING] alpha-goerli is a legacy network name parameter and it won't be supported in future versions
Does Cairo Lang have any logic operators?
Can tempvar be of a different type, say U256?
How do you optimize gas in Cairo with Uint256/felt?