Can you spot an inefficiency in the following code? Hint: take a look here. Fix the inefficiency in two ways (implement each of the following fixes separately):
- Move the instruction alloc_locals.
- Use tempvar instead of local.
func pow4(n) -> (m : felt):
alloc_locals
local x
jmp body if n != 0
[ap] = 0; ap++
ret
body:
x = n * n
[ap] = x * x; ap++
ret
end
func main():
pow4(n=5)
ret
end
Solution
The hint given in the exercise makes me believe that the optimization they are looking for is about not leaving memory gaps to prevent a Prover to be forced to fill the gaps with random data consuming more resources than needed.
To find memory gaps we need to do a memory profiling of our code execution:
$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json --print_memory --relocate_prints
>>>
Addr Value
-----------
⋮
1 290341444919459839
2 1
3 146226256843603965
4 5
5 5189976364521848832
6 0
7 2345108766317314046
8 4632937368431460352
9 5209116658643271680
10 2345108766317314046
11 5189976364521848832
12 5
13 1226245742482522112
14 -12
15 2345108766317314046
16 23
17 23
18 5
19 18
20 15
21 25
22 625
No memory gaps so far but we have to take into account that our function has two branches and we are only executing one, when n is different than 0. Let’s modify our code to force the other branch and see what happens.
func pow4(n) -> (m : felt):
# same as before
end
func main():
pow4(n=0)
ret
end
Compiling and executing this version of the code we get:
Addr Value
-----------
⋮
1 290341444919459839
2 1
3 146226256843603965
4 5
5 5189976364521848832
6 0
7 2345108766317314046
8 4632937368431460352
9 5209116658643271680
10 2345108766317314046
11 5189976364521848832
12 0
13 1226245742482522112
14 -12
15 2345108766317314046
16 23
17 23
18 0
19 18
20 15
⋮
22 0
And there you have it, cell 21 was skipped creating a memory gap, but why? The problem lies in that, in this scenario where n = 0, the local value x is never used, but the compiler is moving the ap pointer forward one cell to leave space for it anyway creating the memory gap.
One solution would be to move the alloc_locals instruction to the branch where the local value is used so the ap pointer is moved only when is actually needed.
func pow4(n) -> (m : felt):
jmp body if n != 0
[ap] = 0; ap++
ret
body:
alloc_locals
local x = n * n
[ap] = x * x; ap++
ret
end
func main():
pow4(n=0)
ret
end
Executing this new version of the code we can see that the memory gap is gone.
Addr Value
-----------
⋮
1 146226256843603965
2 5
3 5189976364521848832
4 0
5 2345108766317314046
6 290341444919459839
7 1
8 4632937368431460352
9 5209116658643271680
10 2345108766317314046
11 5189976364521848832
12 0
13 1226245742482522112
14 -12
15 2345108766317314046
16 22
17 22
18 0
19 18
20 15
21 0
At this point you might be wondering, why aren’t we calculating the return value of the function in a single expression like in the example code below?
func pow4(n) -> (m : felt):
jmp body if n != 0
[ap] = 0; ap++
ret
body:
alloc_locals
local x = n * n * n * n
ret
end
func main():
pow4(n=5)
ret
end
The output of executing this program is shown below:
Addr Value
-----------
⋮
1 146226256843603965
2 5
3 5189976364521848832
4 0
5 2345108766317314046
6 290341444919459839
7 1
8 5209116645758173184
9 5208553695804882944
10 4632374418478170112
11 2345108766317314046
12 5189976364521848832
13 5
14 1226245742482522112
15 -13
16 2345108766317314046
17 25
18 25
19 5
20 19
21 16
22 625
23 25
24 125
Although this exercise is introduced before the “functions” section I’m going to go on a limb, based on the original code of the exercise, and assume that the return value of a function is the last value referenced by the ap pointer which in our case is the number 125 instead of the correct number 625.
A different solution to the inefficiency problem that would allow us the ergonomics of calculating the x^4 in a single expression is by using tempvar instead of local as the former relies on the ap pointer and the last value of the pointer, the return value of the function, would hold the result of the calculation.
func pow4(n) -> (m : felt):
jmp body if n != 0
[ap] = 0; ap++
ret
body:
tempvar x = n * n * n * n
ret
end
func main():
pow4(n=5)
ret
end
The output of this program is:
Addr Value
-----------
⋮
1 146226256843603965
2 5
3 5189976364521848832
4 0
5 2345108766317314046
6 5209116645758173184
7 5208553695804882944
8 5208553695804882944
9 2345108766317314046
10 5189976364521848832
11 5
12 1226245742482522112
13 -11
14 2345108766317314046
15 23
16 23
17 5
18 17
19 14
20 25
21 125
22 625
Now the correct value 625 is the last value referenced by the ap pointer, making it the correct return value of the function.
Reference
The exercise in this article can be found in this section of the Cairo docs.