When should I use `tempvar` instead of `local`?

📜 Development Proposals Starknet Technical Development
1

According to the documentation, tempvar references depend on the ap register and can be revoked..

On the other and, local variables only depend on the fp register and cannot be revoked. The only downside is that we have to manually increment the ap register before any memory allocation using alloc_locals (adding 1 cairo step).

From this perspective, it seems always better to use local instead of tempvar.

Can anyone provide code samples where using tempvar is better than using local (beside this one extra instruction ap += SIZEOF_LOCALS)?

Thx, I hope this thread will help other Cairo devs to better understand the language.

40 Likes
2

This is a great question. I’m not experienced enough to answer, but I have been trying different scenarios in Cairo Playground and cannot come up with a situation where using tempvar is better. But I would like to hear an experienced Cairo dev’s thoughts.

This comparison of tempvar to local seems similar to comparing let x = 5 (x can be reassigned) to const x = 5 (x cannot be reassigned), but without the ap and fp registers. Sometimes it may be helpful to reassign.

But again, I don’t know! Just thinking.

Adding a few more thoughts…

Here is an example similar to one I found here under Declaring Variables:

func main{}():
  # required to use local variables
  alloc_locals
  # creating alias by value
  let a = 5
  let b = 3
  # creating alias by reference. x value is 5
  let x = a
  # constant, can not be re assigned
  const nine = 9
  # res is 15 here, 5 * 3
  tempvar res = a * b
  # local varible. c is 14
  local c = nine + a
  # re-assign aliased variable
  let b = 2
  # re-assign tempvar. res is 10 here, 5 * 2
  tempvar res = a * b
  return ()
end

Not sure practically why you would want to reassign b and res, but maybe there’s a use case for something like this.

20 Likes
3

As far as I understand it, besides lacking the alloc_locals step, tempvar is mainly useful for exactly what it says: temporary variables. Think counters in a loop, or accumulators. These variables not only change during the same function call, but they change a number of times that is not statically known, prohibiting us from just using alloc_locals to allocate space relative to fp.

Take the following loop as an example. We’re leveraging that, unlike fp, we can advance ap during a call, and give names to things at a specific offset from ap, so that while memory is immutable, we can still change what “the value 2 cells before where ap is pointing” is by advancing ap and specifying that value.

func sum_tempvar(arr_len : felt, arr : felt*) -> (res : felt):
    tempvar acc = 0
    tempvar arr = arr
    tempvar arr_len = arr_len 
    loop:
    if arr_len == 0:
        return (acc)
    end
    tempvar acc = acc + [arr]
    tempvar arr = arr + 1
    tempvar arr_len = arr_len - 1
    jmp loop
end

The alternative without tempvar would be to use recursion, e.g.

func sum(arr_len : felt, arr : felt*) -> (res : felt):
    let (res) = sum_rec(arr_len, arr, 0)
    return (res)
end

func sum_rec(arr_len : felt, arr : felt*, acc : felt) -> (res : felt):
    if arr_len == 0:
        return (acc)
    end
    return sum_rec(arr_len - 1, arr + 1, acc + [arr])
end

This does the same sort of thing but instead by advancing fp using a function call, it comes with overhead though from setting up the call, proportional to the number of iterations, and if there were any constants (w.r.t to the recursive calls) that were not statically known (e.g. parameters in some model), I believe you would have to pay an additional cost for either copying them, or pointing to some struct/tuple of said constants. Whether or not this matters depends on context.

19 Likes
4

One instance where you need to use tempvar is with the new operator. Otherwise you’ll get a “The use of ‘new’ in reference expressions is not allowed.” error (cairo v0.9.0).

18 Likes
5

Very helpful, thanks! This led me to think of an example where replacing locals with tempvars decreases the memory usage by a LOT.

The first part is based on the Starklings Recursion01 exercise (but I changed the variable names) to calculate the nth Fibonacci number. Each recursion needs 2 local variables, and the number of recursions increases dramatically as n gets larger, so it uses a lot of memory. If n=10, this takes 1531 steps:

# Calculates nth fibonacci number, using recursion
%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc

func fibonacci(n : felt) -> (fib_n : felt):
    alloc_locals  # locals needed to store fibn_1 and fibn_2 for each recursion

    if n == 0:
        return (fib_n=0)
    end

    if n == 1:
        return (fib_n=1)
    end

    # otherwise call `fibonacci` recursively to compute fibn_1 and fibn_2
    let (local fibn_1) = fibonacci(n=n - 1)
    let (local fibn_2) = fibonacci(n=n - 2)
    return (fib_n=fibn_1 + fibn_2)
end

func main{output_ptr : felt*}():
    let n = 10
    let (fib_n) = fibonacci(n)  # find nth fibonacci number
    serialize_word(fib_n)
    return ()
end

Then I followed your idea of using a loop and a tempvar as a counter. It uses an array to store fibonacci(0) up to fibonacci(n), each as it is calculated. (I got this idea from memoization in Python.) This eliminates the repetitive/inefficient calculations of the above recursions. This takes only 153 steps to find fibonacci(10):

# Calculates nth Fibonacci number, using fib array to store 0th to nth fibonacci numbers
%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc

func fibonacci{}(n : felt, fib : felt*) -> (fib_n : felt):
    if n == 0:
        return (fib_n=fib[0])
    end

    if n == 1:
        return (fib_n=fib[1])
    end

    # otherwise use loop to find fib[2] up to fib[n]
    tempvar fib_ctr = 2  # initialize fib member counter
    loop:
        # when fib_ctr > n, all fib values have been filled, return fib[n]
        if fib_ctr == n + 1:
            return (fib_n=fib[n])
        end

        # for fib_ctr >=2, fill fib array up to fib[n]
        assert fib[fib_ctr] = fib[fib_ctr - 1] + fib[fib_ctr - 2]

        tempvar fib_ctr = fib_ctr + 1  # advance to next fib member

    jmp loop
end

func main{output_ptr : felt*}():
    let n = 10
    let (fib : felt*) = alloc()  # set fib pointer to begin storing fib[n] values

    # fill first two values of fib array
    assert fib[0] = 0  # note some define fib[0] = 1 instead; changes results
    assert fib[1] = 1

    let (fib_n) = fibonacci(n, fib)  # find nth fibonacci number
    serialize_word(fib_n)

    return ()
end

The code in the recursive version definitely looks simpler than that in the loop version, and actually is more efficent for n<=3. But for n>=4, the loop version saves on memory, and saves a lot of memory if n is large.

15 Likes