Cairo’s Continuous Memory Exercise I

Run the following program:

func main():
  [ap] = 100
  [ap + 2] = 200
  ret
end

Explain why the execution of this program creates a memory gap, and therefore an inefficiency (given what you’ve just read in the above section). Add one instruction at the end of the function (just before ret) so that there won’t be a memory gap.

Solution

Cairo expects that a program makes use of memory in sequence. That means that if we store data in ap, the next data should be stored in ap+1, the next one in ap+2 and so forth. This is however not a hard requirement as the exercise code would still compile even though the memory address ap+1 is never used.

The result of the execution of the exercise with a memory debugger is shown below. In there you can see that the memory address 9 (ap+1) is skipped and no value is stored in that location.

$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json \
--print_memory --print_info --relocate_prints
>>>

Addr  Value
-----------
⋮
1     4613515612218425344
2     100
3     4613515612218425346
4     200
5     2345108766317314046
6     11
7     11
8     100
⋮
10    200

Number of steps: 3 (originally, 3)
Used memory cells: 9
Register values after execution:
pc = 11
ap = 8
fp = 11

The Prover (SHARP) however, when executing the compiled code to generate the cryptographic proof that attest to the integrity of the computation, will fill the memory gaps with random values. This means that a program with memory gaps as the exercise will take more resources than needed from the Prover.

In the exercise we are required to “add one instruction at the end of the function (just before ret) so that there won’t be a memory gap” so we can put any value on the memory address ap+1 that was skipped.

func main():
  [ap] = 100
  [ap + 2] = 200
  [ap + 1] = 150
  ret
end

The result of executing this new code is shown below.

Addr  Value
-----------
⋮
1     4613515612218425344
2     100
3     4613515612218425346
4     200
5     4613515612218425345
6     150
7     2345108766317314046
8     13
9     13
10    100
11    150
12    200

Number of steps: 4 (originally, 4)
Used memory cells: 12
Register values after execution:
pc = 13
ap = 10
fp = 13

Now there are no gaps in the memory usage of our code.

Reference

The exercise in this article can be found in this section of the Cairo docs.