fix: honk sumcheck performance

[ludamad]

Parallelizing sumcheck partially_evaluate
Before

After

(note, when we see parallel_for_mutex_pool in the flamegraph it's some parallel_for operation but the details are aggregated in different threads)

[AztecBot]

Benchmark results

Metrics with a significant change:

• note_history_trial_decrypting_time_in_ms (10): 240 (+58%)

Detailed results

All benchmarks are run on txs on the Benchmarking contract on the repository. Each tx consists of a batch call to create_note and increment_balance, which guarantees that each tx has a private call, a nested private call, a public call, and a nested public call, as well as an emitted private note, an unencrypted log, and public storage read and write.

This benchmark source data is available in JSON format on S3 here.

Values are compared against data from master at commit db3fa62e and shown if the difference exceeds 1%.

L2 block published to L1

Each column represents the number of txs on an L2 block published to L1.

Metric	8 txs	32 txs	128 txs
l1_rollup_calldata_size_in_bytes	45,444	179,588	716,132
l1_rollup_calldata_gas	222,972	868,160	3,449,744
l1_rollup_execution_gas	842,059	3,595,268	22,205,113
l2_block_processing_time_in_ms	1,025	3,825 (-2%)	15,198 (-1%)
note_successful_decrypting_time_in_ms	334 (-1%)	1,004 (-4%)	3,912 (-1%)
note_trial_decrypting_time_in_ms	38.0 (-3%)	108	137
l2_block_building_time_in_ms	8,918	35,707	156,601
l2_block_rollup_simulation_time_in_ms	6,605 (+1%)	26,534 (+1%)	104,791
l2_block_public_tx_process_time_in_ms	2,274 (-1%)	9,054 (-3%)	51,158 (-1%)

L2 chain processing

Each column represents the number of blocks on the L2 chain where each block has 16 txs.

Metric	5 blocks	10 blocks
node_history_sync_time_in_ms	11,462 (-6%)	21,710 (-1%)
note_history_successful_decrypting_time_in_ms	2,357 (-8%)	4,624 (-4%)
note_history_trial_decrypting_time_in_ms	123	⚠️ 240 (+58%)
node_database_size_in_bytes	1,662,889	1,201,069
pxe_database_size_in_bytes	27,188	54,187

Circuits stats

Stats on running time and I/O sizes collected for every circuit run across all benchmarks.

Circuit	circuit_simulation_time_in_ms	circuit_input_size_in_bytes	circuit_output_size_in_bytes
private-kernel-init	46.4 (-3%)	61,697	18,841
private-kernel-ordering	23.3 (-3%)	24,233	8,089
base-rollup	850 (-1%)	639,797	811
root-rollup	37.7 (-1%)	4,072	1,097
private-kernel-inner	41.3 (-6%)	81,504	18,841
public-kernel-private-input	47.4 (-1%)	41,455	18,841
public-kernel-non-first-iteration	30.5 (-4%)	41,497	18,841
merge-rollup	0.957 (+18%)	2,592	873

Miscellaneous

Transaction sizes based on how many contracts are deployed in the tx.

Metric	0 deployed contracts	1 deployed contracts
tx_size_in_bytes	8,723	27,508

[codygunton]

Nice, I thought someone already did this, but it seems they didn't.

@ledwards2225 set up some scripts earlier this year to compare benchmarks of feature branches against benchmarks of master. There is also a script to compare UltraHonk vs. UltraPlonk performance for a feature branch. I updated those in the current and pushed commits (note that I had to make some local commits to master to get this to work).

Here are the changes for ultra_honk_bench before and after your change:

Benchmark                                                               Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------
construct_proof_ultra/sha256/10/repeats:1                            -0.5978         -0.6333           707           284           641           235
construct_proof_ultra/keccak/10/repeats:1                            -0.3875         -0.4344          1378           844          1205           681
construct_proof_ultra/ecdsa_verification/10/repeats:1                -0.3625         -0.4520          2566          1636          2315          1269
construct_proof_ultra/merkle_membership/10/repeats:1                 -0.2672         -0.3287           274           201           241           162
OVERALL_GEOMEAN                                                      -0.4176         -0.4744             1             1             1             0

Here is UltraHonk vs UltraPlonk for your branch:

Benchmark                                                               Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------
construct_proof_ultra/sha256/10/repeats:1                            -0.8137         -0.8334          1559           290          1454           242
construct_proof_ultra/keccak/10/repeats:1                            -0.4178         -0.4081          1433           834          1124           665
construct_proof_ultra/ecdsa_verification/10/repeats:1                -0.4736         -0.4704          3049          1605          2322          1230
construct_proof_ultra/merkle_membership/10/repeats:1                 -0.2946         -0.3059           282           199           237           165
OVERALL_GEOMEAN                                                      -0.5520         -0.5636             1             1             1             0

and, for reference, this is UltraHonk vs UltraPlonk in master

Benchmark                                                               Time             CPU      Time Old      Time New       CPU Old       CPU New
----------------------------------------------------------------------------------------------------------------------------------------------------
construct_proof_ultra/sha256/10/repeats:1                            -0.5263         -0.5283          1539           729          1409           665
construct_proof_ultra/keccak/10/repeats:1                            +0.0840         +0.2157          1397          1515          1094          1330
construct_proof_ultra/ecdsa_verification/10/repeats:1                +0.0898         +0.2421          2497          2721          1911          2374
construct_proof_ultra/merkle_membership/10/repeats:1                 +0.0318         +0.0838           278           287           234           254
OVERALL_GEOMEAN                                                      -0.1283         -0.0626             1             1             1             1

[lucasxia01]

and, for reference, this is UltraHonk vs UltraHonk in master

Did you mean UltraHonk vs UltraPlonk in master?