search

noir-lang / noir

Noir is a domain specific language for zero knowledge proofs
https://noir-lang.org
Apache License 2.0
905 stars 206 forks source link

fix: Don't remove necessary RC instructions in DIE pass #6585

Open jfecher opened 4 days ago

jfecher commented 4 days ago

Description

Problem*

Resolves https://github.com/noir-lang/noir/issues/6583

Summary*

Additional Context

Documentation*

Check one:

PR Checklist*

github-actions[bot] commented 4 days ago

Changes to Brillig bytecode sizes

Generated at commit: b9a5af03d2f6b4e7c3a195c19077238cabfbc4b0, compared to commit: 45eb7568d56b2d254453b85f236d554232aa5df9

🧾 Summary (10% most significant diffs)

Program Brillig opcodes (+/-) %
nested_array_dynamic +378 ❌ +18.98%
nested_array_in_slice +181 ❌ +15.08%
brillig_rc_regression_6123 +24 ❌ +13.41%
nested_dyn_array_regression_5782 +15 ❌ +8.98%
regression_struct_array_conditional +44 ❌ +8.22%
brillig_nested_arrays +11 ❌ +6.43%
Full diff report 👇
| Program | Brillig opcodes (+/-) | % | |:-|-:|-:| | **nested_array_dynamic** | 2,370 (+378) | **+18.98%** | | **nested_array_in_slice** | 1,381 (+181) | **+15.08%** | | **brillig_rc_regression_6123** | 203 (+24) | **+13.41%** | | **nested_dyn_array_regression_5782** | 182 (+15) | **+8.98%** | | **regression_struct_array_conditional** | 579 (+44) | **+8.22%** | | **brillig_nested_arrays** | 182 (+11) | **+6.43%** | | **fold_2_to_17** | 651 (+34) | **+5.51%** | | **bench_2_to_17** | 373 (+17) | **+4.78%** | | **poseidon2** | 380 (+17) | **+4.68%** | | **hashmap** | 21,423 (+898) | **+4.38%** | | **fold_numeric_generic_poseidon** | 828 (+34) | **+4.28%** | | **no_predicates_numeric_generic_poseidon** | 828 (+34) | **+4.28%** | | **array_sort** | 316 (+12) | **+3.95%** | | **array_dynamic_nested_blackbox_input** | 905 (+33) | **+3.78%** | | **brillig_cow** | 392 (+12) | **+3.16%** | | **uhashmap** | 13,909 (+381) | **+2.82%** | | **wildcard_type** | 297 (+7) | **+2.41%** | | **eddsa** | 10,890 (+203) | **+1.90%** | | **bigint** | 2,029 (+33) | **+1.65%** | | **slices** | 2,068 (+31) | **+1.52%** | | **regression_5252** | 4,723 (+69) | **+1.48%** | | **array_to_slice** | 830 (+12) | **+1.47%** | | **to_be_bytes** | 214 (+3) | **+1.42%** | | **6** | 1,145 (+16) | **+1.42%** | | **conditional_regression_short_circuit** | 1,218 (+16) | **+1.33%** | | **poseidon_bn254_hash** | 5,520 (+72) | **+1.32%** | | **poseidon_bn254_hash_width_3** | 5,520 (+72) | **+1.32%** | | **poseidonsponge_x5_254** | 4,323 (+54) | **+1.26%** | | **slice_regex** | 2,187 (+21) | **+0.97%** | | **regression_4449** | 735 (+6) | **+0.82%** | | **sha256** | 2,256 (+18) | **+0.80%** | | **ecdsa_secp256k1** | 909 (+6) | **+0.66%** | | **aes128_encrypt** | 516 (+3) | **+0.58%** | | **array_dynamic_blackbox_input** | 1,033 (+6) | **+0.58%** | | **conditional_1** | 1,200 (+6) | **+0.50%** | | **sha256_var_witness_const_regression** | 1,250 (+6) | **+0.48%** | | **sha2_byte** | 2,826 (+12) | **+0.43%** | | **regression** | 735 (+3) | **+0.41%** | | **sha256_var_size_regression** | 1,723 (+6) | **+0.35%** | | **slice_dynamic_index** | 2,646 (+6) | **+0.23%** | | **sha256_regression** | 6,580 (+12) | **+0.18%** | | **sha256_var_padding_regression** | 4,795 (+2) | **+0.04%** |
github-actions[bot] commented 4 days ago

Changes to number of Brillig opcodes executed

Generated at commit: b9a5af03d2f6b4e7c3a195c19077238cabfbc4b0, compared to commit: 45eb7568d56b2d254453b85f236d554232aa5df9

🧾 Summary (10% most significant diffs)

Program Brillig opcodes (+/-) %
fold_2_to_17 +465,930 ❌ +40.63%
bench_2_to_17 +244,965 ❌ +39.66%
fold_numeric_generic_poseidon +1,427 ❌ +26.89%
no_predicates_numeric_generic_poseidon +1,427 ❌ +26.89%
poseidon2 +165 ❌ +22.57%
Full diff report 👇
| Program | Brillig opcodes (+/-) | % | |:-|-:|-:| | **fold_2_to_17** | 1,612,665 (+465,930) | **+40.63%** | | **bench_2_to_17** | 862,583 (+244,965) | **+39.66%** | | **fold_numeric_generic_poseidon** | 6,734 (+1,427) | **+26.89%** | | **no_predicates_numeric_generic_poseidon** | 6,734 (+1,427) | **+26.89%** | | **poseidon2** | 896 (+165) | **+22.57%** | | **hashmap** | 65,584 (+8,861) | **+15.62%** | | **uhashmap** | 170,136 (+21,992) | **+14.85%** | | **brillig_rc_regression_6123** | 340 (+40) | **+13.33%** | | **nested_array_in_slice** | 1,711 (+153) | **+9.82%** | | **nested_array_dynamic** | 3,414 (+298) | **+9.56%** | | **nested_dyn_array_regression_5782** | 178 (+15) | **+9.20%** | | **brillig_nested_arrays** | 155 (+9) | **+6.16%** | | **regression_struct_array_conditional** | 1,683 (+94) | **+5.92%** | | **wildcard_type** | 517 (+24) | **+4.87%** | | **array_sort** | 614 (+28) | **+4.78%** | | **slices** | 3,352 (+66) | **+2.01%** | | **slice_dynamic_index** | 4,740 (+59) | **+1.26%** | | **brillig_cow** | 1,159 (+12) | **+1.05%** | | **regression_5252** | 967,014 (+7,884) | **+0.82%** | | **array_dynamic_nested_blackbox_input** | 4,551 (+30) | **+0.66%** | | **array_to_slice** | 1,884 (+12) | **+0.64%** | | **poseidonsponge_x5_254** | 193,700 (+1,230) | **+0.64%** | | **slice_regex** | 3,419 (+21) | **+0.62%** | | **poseidon_bn254_hash** | 171,817 (+864) | **+0.51%** | | **poseidon_bn254_hash_width_3** | 171,817 (+864) | **+0.51%** | | **eddsa** | 741,560 (+2,942) | **+0.40%** | | **6** | 7,115 (+16) | **+0.23%** | | **conditional_regression_short_circuit** | 7,193 (+16) | **+0.22%** | | **regression_4449** | 200,304 (+420) | **+0.21%** | | **sha256** | 13,888 (+18) | **+0.13%** | | **to_be_bytes** | 2,484 (+3) | **+0.12%** | | **regression** | 2,854 (+3) | **+0.11%** | | **conditional_1** | 5,735 (+6) | **+0.10%** | | **sha256_var_witness_const_regression** | 6,758 (+6) | **+0.09%** | | **ecdsa_secp256k1** | 6,787 (+6) | **+0.09%** | | **aes128_encrypt** | 4,486 (+3) | **+0.07%** | | **array_dynamic_blackbox_input** | 18,265 (+12) | **+0.07%** | | **sha256_var_size_regression** | 16,362 (+6) | **+0.04%** | | **sha2_byte** | 49,945 (+9) | **+0.02%** | | **sha256_regression** | 116,216 (+12) | **+0.01%** | | **sha256_var_padding_regression** | 219,745 (+2) | **+0.00%** |
github-actions[bot] commented 4 days ago

Changes to circuit sizes

Generated at commit: b9a5af03d2f6b4e7c3a195c19077238cabfbc4b0, compared to commit: 45eb7568d56b2d254453b85f236d554232aa5df9

🧾 Summary (10% most significant diffs)

Program ACIR opcodes (+/-) % Circuit size (+/-) %
nested_array_dynamic +161 ❌ +4.91% +283 ❌ +2.24%
array_dynamic_nested_blackbox_input +6 ❌ +2.43% +17 ❌ +0.23%
Full diff report 👇
| Program | ACIR opcodes (+/-) | % | Circuit size (+/-) | % | |:-|-:|-:|-:|-:| | **nested_array_dynamic** | 3,442 (+161) | **+4.91%** | 12,933 (+283) | **+2.24%** | | **array_dynamic_nested_blackbox_input** | 253 (+6) | **+2.43%** | 7,326 (+17) | **+0.23%** |
jfecher commented 3 days ago

This PR is ready for review now - I've re-added the mutable array check optimization using array types instead of their values but unfortunately there is still a sizeable performance regression. Unsure how to fix it currently but am opening this PR if anyone wants to tackle it while I'm out next week.