[MockProver] Testing is slower after #389

[ChihChengLiang]

Problem

The test speed is slower when #389 is applied.

We use the test of this branch for experiment privacy-scaling-explorations/zkevm-circuits#156

cargo test --release test_rho_gate -p keccak256 -- --nocapture is about 11 sec on old commit 4283713e, but is about 34 sec on 1723fed1, which is 4283713e with git cherry-pick b94aab76a338870fec778d4da3a1c6789bc92bc4.

The hardware is the apple M1 silicon.

Solution

Need investigation

[str4d]

Well that is not the direction we wanted the numbers to go! Suggests that the cost of constructing the BTreeSet is higher than the previous O(n^2) lookup cost.

[daira]

There's a way to fix this by sorting in one pass rather than by inserting into a BTreeSet.

[daira]

I can reproduce this regression (18.15s -> 48.88s on a Core i7-6800K @ 3.40GHz).

[daira]

If I stub out the lookup check as shown, the test takes 18.05s on the same machine. This implies that, at least for this experiment, the O(n²) part of the lookup check was only taking 0.1s overall, and was not the original performance problem. (It probably is a problem for larger tables, just not for the table size in this experiment.) We should probably just revert #389 for now.

diff --git a/src/dev.rs b/src/dev.rs
index e474232..7121e6a 100644
--- a/src/dev.rs
+++ b/src/dev.rs
@@ -713,7 +713,7 @@ impl<F: FieldExt> MockProver<F> {
 
                     // In the real prover, the lookup expressions are never enforced on
                     // unusable rows, due to the (1 - (l_last(X) + l_blind(X))) term.
-                    let table: std::collections::BTreeSet<Vec<_>> = self
+                    let table: Vec<_> = self
                         .usable_rows
                         .clone()
                         .map(|table_row| {
@@ -730,7 +730,7 @@ impl<F: FieldExt> MockProver<F> {
                             .iter()
                             .map(|c| load(c, input_row))
                             .collect();
-                        let lookup_passes = table.contains(&inputs);
+                        let lookup_passes = true;
                         if lookup_passes {
                             None
                         } else {

[daira]

I tried this but it only recovered part of the performance regression (23.96s on the experiment):

diff --git a/src/dev.rs b/src/dev.rs
index e474232..6cf5d0b 100644
--- a/src/dev.rs
+++ b/src/dev.rs
@@ -713,7 +713,7 @@ impl<F: FieldExt> MockProver<F> {
 
                     // In the real prover, the lookup expressions are never enforced on
                     // unusable rows, due to the (1 - (l_last(X) + l_blind(X))) term.
-                    let table: std::collections::BTreeSet<Vec<_>> = self
+                    let mut table: Vec<_> = self
                         .usable_rows
                         .clone()
                         .map(|table_row| {
@@ -724,13 +724,15 @@ impl<F: FieldExt> MockProver<F> {
                                 .collect::<Vec<_>>()
                         })
                         .collect();
+                    table.sort();
+
                     self.usable_rows.clone().filter_map(move |input_row| {
                         let inputs: Vec<_> = lookup
                             .input_expressions
                             .iter()
                             .map(|c| load(c, input_row))
                             .collect();
-                        let lookup_passes = table.contains(&inputs);
+                        let lookup_passes = table.binary_search(&inputs).is_ok();
                         if lookup_passes {
                             None
                         } else {

Merry Christmas!

[daira]

@ChihChengLiang Please verify that this branch, based on your rho-cleanup branch, fixes the regression: https://github.com/daira/halo2/tree/mockprover-regression-appliedzkp

(This code has changed significantly upstream, so I'll have to reapply the change to main for that.)

[ChihChengLiang]

@daira I can verify the regression is fixed. I'm getting 12.00s, 11.45s, 11.40s on the 3 runs on your branch applied. That's very close to the 11.28s on the original branch with no change applied.

Thank you so much for looking into this and the fix.

[daira]

Note that the branch https://github.com/daira/halo2/tree/mockprover-regression-appliedzkp has a bug that causes it to report the wrong row number for lookup failures, but that bug cannot affect performance. It's not present in #445 , but I thought I'd mention it in case you still need the earlier branch.

[ChihChengLiang]

Noted, thanks for the heads up :)