lambdaclass / cairo-vm

cairo-vm is a Rust implementation of the Cairo VM. Cairo (CPU Algebraic Intermediate Representation) is a programming language for writing provable programs, where one party can prove to another that a certain computation was executed correctly without the need for this party to re-execute the same program.
https://lambdaclass.github.io/cairo-vm
Apache License 2.0
514 stars 144 forks source link

Add `EXCESS_BALANCE` hint #1777

Closed fmoletta closed 4 months ago

fmoletta commented 4 months ago

Implements hint:

%{
            from excess_balance import excess_balance_func

            res = excess_balance_func(ids, memory, __dict_manager)

            ids.check_account_value = res["account_value"]
            ids.check_excess_balance = res["excess_balance"]
            ids.check_margin_requirement_d = res["margin_requirement"]
            ids.check_unrealized_pnl_d = res["unrealized_pnl"]
%}
github-actions[bot] commented 4 months ago
**Hyper Thereading Benchmark results**

hyperfine -r 2 -n "hyper_threading_main threads: 1" 'RAYON_NUM_THREADS=1 ./hyper_threading_main' -n "hyper_threading_pr threads: 1" 'RAYON_NUM_THREADS=1 ./hyper_threading_pr'
Benchmark 1: hyper_threading_main threads: 1
  Time (mean ± σ):     26.971 s ±  0.047 s    [User: 26.136 s, System: 0.834 s]
  Range (min … max):   26.938 s … 27.005 s    2 runs

Benchmark 2: hyper_threading_pr threads: 1
  Time (mean ± σ):     25.208 s ±  0.041 s    [User: 24.474 s, System: 0.732 s]
  Range (min … max):   25.179 s … 25.237 s    2 runs

Summary
  'hyper_threading_pr threads: 1' ran
    1.07 ± 0.00 times faster than 'hyper_threading_main threads: 1'

hyperfine -r 2 -n "hyper_threading_main threads: 2" 'RAYON_NUM_THREADS=2 ./hyper_threading_main' -n "hyper_threading_pr threads: 2" 'RAYON_NUM_THREADS=2 ./hyper_threading_pr'
Benchmark 1: hyper_threading_main threads: 2
  Time (mean ± σ):     15.076 s ±  0.033 s    [User: 26.921 s, System: 0.778 s]
  Range (min … max):   15.052 s … 15.099 s    2 runs

Benchmark 2: hyper_threading_pr threads: 2
  Time (mean ± σ):     14.185 s ±  0.012 s    [User: 25.306 s, System: 0.768 s]
  Range (min … max):   14.176 s … 14.193 s    2 runs

Summary
  'hyper_threading_pr threads: 2' ran
    1.06 ± 0.00 times faster than 'hyper_threading_main threads: 2'

hyperfine -r 2 -n "hyper_threading_main threads: 4" 'RAYON_NUM_THREADS=4 ./hyper_threading_main' -n "hyper_threading_pr threads: 4" 'RAYON_NUM_THREADS=4 ./hyper_threading_pr'
Benchmark 1: hyper_threading_main threads: 4
  Time (mean ± σ):     11.161 s ±  0.169 s    [User: 38.188 s, System: 0.983 s]
  Range (min … max):   11.041 s … 11.280 s    2 runs

Benchmark 2: hyper_threading_pr threads: 4
  Time (mean ± σ):     10.435 s ±  0.288 s    [User: 37.480 s, System: 0.975 s]
  Range (min … max):   10.232 s … 10.639 s    2 runs

Summary
  'hyper_threading_pr threads: 4' ran
    1.07 ± 0.03 times faster than 'hyper_threading_main threads: 4'

hyperfine -r 2 -n "hyper_threading_main threads: 6" 'RAYON_NUM_THREADS=6 ./hyper_threading_main' -n "hyper_threading_pr threads: 6" 'RAYON_NUM_THREADS=6 ./hyper_threading_pr'
Benchmark 1: hyper_threading_main threads: 6
  Time (mean ± σ):     10.581 s ±  0.194 s    [User: 38.179 s, System: 1.079 s]
  Range (min … max):   10.444 s … 10.719 s    2 runs

Benchmark 2: hyper_threading_pr threads: 6
  Time (mean ± σ):     10.137 s ±  0.164 s    [User: 37.388 s, System: 0.978 s]
  Range (min … max):   10.021 s … 10.253 s    2 runs

Summary
  'hyper_threading_pr threads: 6' ran
    1.04 ± 0.03 times faster than 'hyper_threading_main threads: 6'

hyperfine -r 2 -n "hyper_threading_main threads: 8" 'RAYON_NUM_THREADS=8 ./hyper_threading_main' -n "hyper_threading_pr threads: 8" 'RAYON_NUM_THREADS=8 ./hyper_threading_pr'
Benchmark 1: hyper_threading_main threads: 8
  Time (mean ± σ):     10.612 s ±  0.002 s    [User: 38.541 s, System: 1.091 s]
  Range (min … max):   10.610 s … 10.613 s    2 runs

Benchmark 2: hyper_threading_pr threads: 8
  Time (mean ± σ):     10.274 s ±  0.111 s    [User: 37.469 s, System: 0.985 s]
  Range (min … max):   10.196 s … 10.352 s    2 runs

Summary
  'hyper_threading_pr threads: 8' ran
    1.03 ± 0.01 times faster than 'hyper_threading_main threads: 8'

hyperfine -r 2 -n "hyper_threading_main threads: 16" 'RAYON_NUM_THREADS=16 ./hyper_threading_main' -n "hyper_threading_pr threads: 16" 'RAYON_NUM_THREADS=16 ./hyper_threading_pr'
Benchmark 1: hyper_threading_main threads: 16
  Time (mean ± σ):     10.426 s ±  0.142 s    [User: 38.994 s, System: 1.121 s]
  Range (min … max):   10.325 s … 10.526 s    2 runs

Benchmark 2: hyper_threading_pr threads: 16
  Time (mean ± σ):      9.996 s ±  0.010 s    [User: 37.866 s, System: 1.058 s]
  Range (min … max):    9.989 s … 10.003 s    2 runs

Summary
  'hyper_threading_pr threads: 16' ran
    1.04 ± 0.01 times faster than 'hyper_threading_main threads: 16'
github-actions[bot] commented 4 months ago

Benchmark Results for unmodified programs :rocket:

Command Mean [s] Min [s] Max [s] Relative
base big_factorial 2.156 ± 0.082 2.104 2.379 1.08 ± 0.04
head big_factorial 1.998 ± 0.016 1.980 2.025 1.00
Command Mean [s] Min [s] Max [s] Relative
base big_fibonacci 2.055 ± 0.013 2.035 2.073 1.05 ± 0.01
head big_fibonacci 1.958 ± 0.009 1.941 1.969 1.00
Command Mean [s] Min [s] Max [s] Relative
base blake2s_integration_benchmark 7.852 ± 0.156 7.675 8.103 1.06 ± 0.02
head blake2s_integration_benchmark 7.402 ± 0.091 7.302 7.555 1.00
Command Mean [s] Min [s] Max [s] Relative
base compare_arrays_200000 2.193 ± 0.018 2.157 2.211 1.05 ± 0.02
head compare_arrays_200000 2.087 ± 0.044 2.063 2.210 1.00
Command Mean [s] Min [s] Max [s] Relative
base dict_integration_benchmark 1.444 ± 0.016 1.430 1.484 1.04 ± 0.01
head dict_integration_benchmark 1.384 ± 0.009 1.373 1.401 1.00
Command Mean [s] Min [s] Max [s] Relative
base field_arithmetic_get_square_benchmark 1.262 ± 0.051 1.223 1.401 1.05 ± 0.04
head field_arithmetic_get_square_benchmark 1.202 ± 0.015 1.183 1.225 1.00
Command Mean [s] Min [s] Max [s] Relative
base integration_builtins 7.853 ± 0.140 7.655 8.044 1.05 ± 0.02
head integration_builtins 7.446 ± 0.104 7.355 7.677 1.00
Command Mean [s] Min [s] Max [s] Relative
base keccak_integration_benchmark 8.270 ± 0.332 7.951 8.917 1.07 ± 0.04
head keccak_integration_benchmark 7.717 ± 0.090 7.582 7.847 1.00
Command Mean [s] Min [s] Max [s] Relative
base linear_search 2.153 ± 0.014 2.138 2.182 1.06 ± 0.01
head linear_search 2.040 ± 0.015 2.028 2.077 1.00
Command Mean [s] Min [s] Max [s] Relative
base math_cmp_and_pow_integration_benchmark 1.490 ± 0.011 1.474 1.507 1.04 ± 0.02
head math_cmp_and_pow_integration_benchmark 1.436 ± 0.022 1.420 1.498 1.00
Command Mean [s] Min [s] Max [s] Relative
base math_integration_benchmark 1.479 ± 0.016 1.465 1.521 1.03 ± 0.01
head math_integration_benchmark 1.430 ± 0.009 1.413 1.441 1.00
Command Mean [s] Min [s] Max [s] Relative
base memory_integration_benchmark 1.237 ± 0.030 1.217 1.320 1.06 ± 0.03
head memory_integration_benchmark 1.168 ± 0.006 1.158 1.177 1.00
Command Mean [s] Min [s] Max [s] Relative
base operations_with_data_structures_benchmarks 1.567 ± 0.006 1.558 1.576 1.04 ± 0.01
head operations_with_data_structures_benchmarks 1.507 ± 0.008 1.496 1.522 1.00
Command Mean [ms] Min [ms] Max [ms] Relative
base pedersen 524.0 ± 1.8 521.4 527.1 1.02 ± 0.00
head pedersen 511.8 ± 1.4 509.9 514.0 1.00
Command Mean [ms] Min [ms] Max [ms] Relative
base poseidon_integration_benchmark 767.2 ± 7.1 760.3 783.8 1.03 ± 0.01
head poseidon_integration_benchmark 744.4 ± 3.4 740.5 752.5 1.00
Command Mean [s] Min [s] Max [s] Relative
base secp_integration_benchmark 1.845 ± 0.011 1.827 1.862 1.03 ± 0.01
head secp_integration_benchmark 1.788 ± 0.006 1.779 1.797 1.00
Command Mean [ms] Min [ms] Max [ms] Relative
base set_integration_benchmark 682.7 ± 15.1 671.9 714.5 1.04 ± 0.02
head set_integration_benchmark 657.5 ± 2.2 654.6 661.5 1.00
Command Mean [s] Min [s] Max [s] Relative
base uint256_integration_benchmark 4.431 ± 0.123 4.331 4.752 1.07 ± 0.03
head uint256_integration_benchmark 4.155 ± 0.021 4.122 4.185 1.00
codecov[bot] commented 4 months ago

Codecov Report

Attention: Patch coverage is 97.79338% with 22 lines in your changes are missing coverage. Please review.

Project coverage is 94.84%. Comparing base (c745ece) to head (b7af6b5).

Files Patch % Lines
...processor/builtin_hint_processor/excess_balance.rs 98.67% 13 Missing :warning:
...int_processor/builtin_hint_processor_definition.rs 14.28% 6 Missing :warning:
...t_processor/builtin_hint_processor/dict_manager.rs 57.14% 3 Missing :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #1777 +/- ## ========================================== + Coverage 94.77% 94.84% +0.07% ========================================== Files 101 102 +1 Lines 39056 40053 +997 ========================================== + Hits 37015 37990 +975 - Misses 2041 2063 +22 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.