В чем неэффективность этого каирского кода с использованием alloc_locals

Question

Следующий код:

      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

объявлен неэффективным в документе из-за прерывистой памяти.

Я запустил его и не увидел ни одной дыры в таблице памяти:

      Addr  Value
-----------
⋮
###
⋮
1:0   2:0
1:1   3:0
1:2   5
1:3   1:2
1:4   0:21
1:5   25
1:6   625

так что я не понимаю, где проблема. Я вижу дыру сn=0хотя:

      Addr  Value
-----------
⋮
###
⋮
1:0   2:0
1:1   3:0
1:2   0
1:3   1:2
1:4   0:21
⋮
1:6   0

что я могу исправить, используя:

          jmp body if n != 0
    x = 0
    ret

но это не то, что предлагается:

• Переместите инструкцию alloc_locals.
• или Используйте tempvar вместо local.

Answer 1

Вы правы, что неэффективность связана с дырой в памяти, и правильно, что она появляется только для n=0. Дыры не вызывают неэффективность просто потому, что они существуют, а скорее их существование обычно означает, что эквивалентный код мог бы выполняться с использованием меньшего количества ячеек памяти (в данном случае 6 вместо 7, в разделе памяти «1:»). Чтобы сделать его более эффективным, нужно стремиться удалить дыру (чтобы части до и после нее стали непрерывными), тогда как предлагаемое вами решение просто заполняет ее (что и так делает прувер). Таким образом, ваше решение по-прежнему будет использовать 7 ячеек памяти в сегменте памяти; и на самом деле также будет использовать 2 дополнительные ячейки в разделе программы (дляcommand), так что на самом деле это менее эффективно, чем оставить дыру пустой: скомпилируйте и проверьте!

Неэффективность исходного кода возникает из-за того, что локальной переменной x назначается ячейка памяти даже в случае n=0, несмотря на то, что она не используется. Чтобы сделать его более эффективным, мы просто не хотели бы объявлять и выделять x в этом случае. Это можно сделать, переместив команду внутрь «тела», чтобы она не выполнялась (и локальные не выделялись) в случае n=0, как в первом предложении: это экономит одну ячейку памяти в n =0 случай и не влияет на случай n!=0. Обратите внимание, что он не обязательно должен стоять в самом начале кода.

Второе предложение - сделать xa tempvar вместо локального (и убрать совсем). Это снова означает, что в случае n =0 локальная переменная не выделяется, поэтому снова будет использоваться только 6 ячеек памяти вместо 7. И на самом деле, поскольку код настолько прост, использование tempvar также более эффективно, чем объявление его как местный, по крайней мере, когда используется как, поскольку он пропускает слияниекоманда (это то, чтоделает в данном случае) скоманду, а не запускать их по отдельности.

Помимо обсуждения теории, следует скомпилировать каждый из этих вариантов и сравнить полученные длины кода и сегментов памяти, и посмотреть, что действительно эффективнее и на сколько: это всегда верно при оптимизации, всегда нужно проверять фактическую производительность.

Answer 2

Итак, следуя ответу @dan-carmon и для полноты картины, вот сводка возможных реализаций и их таблица памяти «1», когда n = 0 и n > 0

      # n = 0      n = 5
1:0   2:0    1:0   2:0
1:1   3:0    1:1   3:0
1:2   0      1:2   5
1:3   1:2    1:3   1:2
1:4   0:14   1:4   0:14
1:5   0      1:5   25
             1:6   625

Однако обратите внимание, что реализация с использованиемtempvarиспользует на 2 слота меньше, чем другие в таблице программ "0".

Протестированные реализации

      func pow4_reuse_slot(n) -> (m : felt):
    alloc_locals
    local x

    jmp body if n != 0
    x = 0
    ret

    body:
    x = n * n
    [ap] = x * x; ap++
    ret
end

func pow4_alloc_in_body(n) -> (m : felt):
    jmp body if n != 0
    [ap] = 0; ap++
    ret

    body:
    alloc_locals
    local x
    x = n * n
    [ap] = x * x; ap++
    ret
end

func pow4_use_tempvar(n) -> (m : felt):
    jmp body if n != 0
    [ap] = 0; ap++
    ret

    body:
    tempvar x = n * n
    [ap] = x * x
    ret
end