Loop vs Recursion performance test - Cairo

[danilowhk]

Comparing Loop vs Recursion: A Benchmark

Introduction

This report compares the gas cost of using a loop against using recursion for performing addition operations in Cairo. The tests were conducted using scarb 0.6.0-alpha.2 and cairo 2.1.0-rc2.

Overview

It seems there is no difference if both loop and recursion are as a function, but if the loop is programmed within the function / test, there are performance gains

Methodology

The benchmarks were conducted under the following configurations:

• Language: Cairo
• Version: scarb 0.6.0-alpha.2, cairo 2.1.0-rc2
• Operations: 20 addition operations were evaluated
• Metrics: Gas consumption

Overall Result

The comparison highlights a difference in gas consumption:

| Approach                | Gas Consumption |
|-------------------------|-----------------|
| Recursion As Function   | 54020           |
| Loop As Function        | 54020           |
| Loop                    | 54020           |

Test with Recursion

Description

This approach uses a recursive function to perform 20 addition operations.

Code

use debug::PrintTrait;
use dict::Felt252DictTrait;
use option::OptionTrait;

fn recursive_add(mut a: felt252, mut counter: felt252) -> felt252 {
    if counter == 20 {
        return a;
    }
    a += 1;
    counter += 1;
    return recursive_add(a, counter);
}

#[test]
#[available_gas(1000000)]
fn test_recursion(){
    let x = testing::get_available_gas();
    gas::withdraw_gas().unwrap();
    let value = recursive_add(0, 0);

    // 54020 gas for 20 addition
    (x - testing::get_available_gas()).print();
}

Result

Gas consumption for this test was 54020.

Test with Loop As Function

Description

This approach uses a separate loop function to perform 20 addition operations.

Code

use debug::PrintTrait;
use dict::Felt252DictTrait;
use option::OptionTrait;

fn loop_add(mut a: felt252, mut counter: felt252) -> felt252 {
    loop {
        if counter == 20 {
            break;
        }
        counter += 1;
        a += 1;
    };
    a
}

#[test]
#[available_gas(1000000)]
fn test_loop_as_function(){
    let x = testing::get_available_gas();
    gas::withdraw_gas().unwrap();
    let value = loop_add(0, 0);

    // 54020 gas for 20 additions
    (x - testing::get_available_gas()).print();
}

Result

Gas consumption for this test was 54020.

Test with Loop

Description

This approach uses a loop inside the function to perform 20 addition operations.

Code

use debug::PrintTrait;
use dict::Felt252DictTrait;
use option::OptionTrait;

#[test]
#[available_gas(1000000)]
fn test_loop_in_function(){
    let x = testing::get_available_gas();
    gas::withdraw_gas().unwrap();
    let mut a : felt252 = 0;
    let mut counter: felt252 = 0;
    loop {
        if counter == 20 {
            break;
        }
        counter += 1;
        a += 1;
    };

    // 54020 gas for 20 additions
    (x - testing::get_available_gas()).print();
}

Result

Gas consumption for this test was 54020.

Conclusion

The tests indicate that all three approaches are equally gas-efficient (54020 gas) for performing 20 addition operations in Cairo. The result highlights the similarity in gas consumption between recursion, loop inside the function, and loop as a function.

Appendix:

Versions used:

scarb 0.6.2 (c07fa6155 2023-08-15)
cairo: 2.1.1 (https://crates.io/crates/cairo-lang-compiler/2.1.1)

[enitrat]

@danilowhk Could you link the Sierra programs to each of these implementations?
to keep it simple, you should replace all uints by felts

fn main() -> felt252{
    let mut counter = 0;
    let mut a = 0;
    loop{
        if counter > 20 {
            break;
        }
        counter +=1;
        a += 1;
    };
    a
}