search

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 hint `U256InvModN` to `Cairo1HintProcessor` #1744

Closed fmoletta closed 4 months ago

fmoletta commented 5 months ago

Take hit code from cairo repo + add test

github-actions[bot] commented 5 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 ± σ):     27.291 s ±  0.022 s    [User: 26.461 s, System: 0.828 s]
  Range (min … max):   27.276 s … 27.307 s    2 runs

Benchmark 2: hyper_threading_pr threads: 1
  Time (mean ± σ):     27.445 s ±  0.012 s    [User: 26.555 s, System: 0.888 s]
  Range (min … max):   27.436 s … 27.453 s    2 runs

Summary
  'hyper_threading_main threads: 1' ran
    1.01 ± 0.00 times faster than 'hyper_threading_pr 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 ± σ):     14.690 s ±  0.018 s    [User: 26.993 s, System: 0.879 s]
  Range (min … max):   14.677 s … 14.703 s    2 runs

Benchmark 2: hyper_threading_pr threads: 2
  Time (mean ± σ):     14.742 s ±  0.019 s    [User: 27.148 s, System: 0.860 s]
  Range (min … max):   14.729 s … 14.755 s    2 runs

Summary
  'hyper_threading_main threads: 2' ran
    1.00 ± 0.00 times faster than 'hyper_threading_pr 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 ± σ):     10.655 s ±  0.129 s    [User: 39.109 s, System: 1.060 s]
  Range (min … max):   10.564 s … 10.747 s    2 runs

Benchmark 2: hyper_threading_pr threads: 4
  Time (mean ± σ):     11.182 s ±  0.124 s    [User: 38.814 s, System: 1.061 s]
  Range (min … max):   11.094 s … 11.270 s    2 runs

Summary
  'hyper_threading_main threads: 4' ran
    1.05 ± 0.02 times faster than 'hyper_threading_pr 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.826 s ±  0.030 s    [User: 38.756 s, System: 1.122 s]
  Range (min … max):   10.805 s … 10.847 s    2 runs

Benchmark 2: hyper_threading_pr threads: 6
  Time (mean ± σ):     10.822 s ±  0.063 s    [User: 39.219 s, System: 1.070 s]
  Range (min … max):   10.777 s … 10.867 s    2 runs

Summary
  'hyper_threading_pr threads: 6' ran
    1.00 ± 0.01 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.511 s ±  0.074 s    [User: 39.465 s, System: 1.080 s]
  Range (min … max):   10.459 s … 10.563 s    2 runs

Benchmark 2: hyper_threading_pr threads: 8
  Time (mean ± σ):     10.602 s ±  0.176 s    [User: 39.389 s, System: 1.066 s]
  Range (min … max):   10.477 s … 10.727 s    2 runs

Summary
  'hyper_threading_main threads: 8' ran
    1.01 ± 0.02 times faster than 'hyper_threading_pr 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.608 s ±  0.247 s    [User: 39.696 s, System: 1.196 s]
  Range (min … max):   10.433 s … 10.783 s    2 runs

Benchmark 2: hyper_threading_pr threads: 16
  Time (mean ± σ):     10.634 s ±  0.111 s    [User: 39.711 s, System: 1.121 s]
  Range (min … max):   10.556 s … 10.713 s    2 runs

Summary
  'hyper_threading_main threads: 16' ran
    1.00 ± 0.03 times faster than 'hyper_threading_pr threads: 16'
codecov[bot] commented 5 months ago

Codecov Report

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

Project coverage is 94.76%. Comparing base (bc5a14e) to head (7502b5a).

Files Patch % Lines
...processor/cairo_1_hint_processor/hint_processor.rs 73.03% 24 Missing :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #1744 +/- ## ========================================== - Coverage 94.81% 94.76% -0.05% ========================================== Files 101 101 Lines 38715 38804 +89 ========================================== + Hits 36707 36773 +66 - Misses 2008 2031 +23 ```

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

github-actions[bot] commented 5 months ago

Benchmark Results for unmodified programs :rocket:

Command Mean [s] Min [s] Max [s] Relative
base big_factorial 2.072 ± 0.025 2.051 2.138 1.00
head big_factorial 2.075 ± 0.008 2.061 2.089 1.00 ± 0.01
Command Mean [s] Min [s] Max [s] Relative
base big_fibonacci 2.044 ± 0.068 1.991 2.229 1.01 ± 0.04
head big_fibonacci 2.030 ± 0.022 2.008 2.072 1.00
Command Mean [s] Min [s] Max [s] Relative
base blake2s_integration_benchmark 7.635 ± 0.077 7.513 7.719 1.00 ± 0.02
head blake2s_integration_benchmark 7.614 ± 0.115 7.482 7.860 1.00
Command Mean [s] Min [s] Max [s] Relative
base compare_arrays_200000 2.130 ± 0.017 2.100 2.162 1.00
head compare_arrays_200000 2.167 ± 0.028 2.143 2.243 1.02 ± 0.02
Command Mean [s] Min [s] Max [s] Relative
base dict_integration_benchmark 1.423 ± 0.005 1.418 1.432 1.00
head dict_integration_benchmark 1.427 ± 0.006 1.417 1.437 1.00 ± 0.01
Command Mean [s] Min [s] Max [s] Relative
base field_arithmetic_get_square_benchmark 1.293 ± 0.018 1.275 1.331 1.00
head field_arithmetic_get_square_benchmark 1.305 ± 0.022 1.285 1.363 1.01 ± 0.02
Command Mean [s] Min [s] Max [s] Relative
base integration_builtins 7.734 ± 0.138 7.601 8.009 1.00
head integration_builtins 7.737 ± 0.097 7.652 7.994 1.00 ± 0.02
Command Mean [s] Min [s] Max [s] Relative
base keccak_integration_benchmark 8.182 ± 0.687 7.808 10.043 1.04 ± 0.09
head keccak_integration_benchmark 7.892 ± 0.181 7.744 8.357 1.00
Command Mean [s] Min [s] Max [s] Relative
base linear_search 2.095 ± 0.024 2.062 2.150 1.00
head linear_search 2.105 ± 0.022 2.076 2.142 1.00 ± 0.02
Command Mean [s] Min [s] Max [s] Relative
base math_cmp_and_pow_integration_benchmark 1.700 ± 0.022 1.684 1.758 1.01 ± 0.02
head math_cmp_and_pow_integration_benchmark 1.682 ± 0.013 1.667 1.709 1.00
Command Mean [s] Min [s] Max [s] Relative
base math_integration_benchmark 1.593 ± 0.007 1.583 1.605 1.00
head math_integration_benchmark 1.597 ± 0.007 1.585 1.609 1.00 ± 0.01
Command Mean [s] Min [s] Max [s] Relative
base memory_integration_benchmark 1.205 ± 0.026 1.187 1.278 1.00 ± 0.02
head memory_integration_benchmark 1.199 ± 0.012 1.183 1.221 1.00
Command Mean [s] Min [s] Max [s] Relative
base operations_with_data_structures_benchmarks 1.826 ± 0.017 1.809 1.863 1.00
head operations_with_data_structures_benchmarks 1.831 ± 0.026 1.802 1.891 1.00 ± 0.02
Command Mean [ms] Min [ms] Max [ms] Relative
base pedersen 514.6 ± 2.3 511.1 518.4 1.00
head pedersen 515.2 ± 2.5 512.4 520.0 1.00 ± 0.01
Command Mean [ms] Min [ms] Max [ms] Relative
base poseidon_integration_benchmark 962.9 ± 7.7 953.2 981.6 1.00
head poseidon_integration_benchmark 970.4 ± 4.1 962.4 973.9 1.01 ± 0.01
Command Mean [s] Min [s] Max [s] Relative
base secp_integration_benchmark 1.869 ± 0.011 1.857 1.897 1.00 ± 0.01
head secp_integration_benchmark 1.868 ± 0.014 1.852 1.905 1.00
Command Mean [ms] Min [ms] Max [ms] Relative
base set_integration_benchmark 649.3 ± 6.2 643.9 662.1 1.00 ± 0.01
head set_integration_benchmark 647.1 ± 2.7 643.8 652.9 1.00
Command Mean [s] Min [s] Max [s] Relative
base uint256_integration_benchmark 4.312 ± 0.038 4.252 4.401 1.00 ± 0.02
head uint256_integration_benchmark 4.291 ± 0.074 4.202 4.468 1.00