Feat: switch to logup scheme for lookup argument

[kunxian-xia]

This is a sequel pr of the original #49 by geometry team (https://github.com/geometryresearch).

• [x] fmt
• [x] fix a unit test error
• [x] clippy
• [x] compatiablity with snark-verifier. (done in https://github.com/scroll-tech/snark-verifier/pull/24)
• [x] bench the running time of constructing table_index_value_mapping: BTreeMap<Scalar, usize>.
• [x] remove the need to construct table_index_value_mapping. https://github.com/scroll-tech/halo2/pull/71/commits/d901014b088601b994a427a22ef280f217214b5a
• [x] par_invert the inputs and table log derivatives (fi(X) + beta, t(X) + beta). https://github.com/scroll-tech/halo2/pull/71/commits/ee957d8fe67e1b803481e7cc84813f5c9c949eec

Moreover, we add one more feature logup_skip_inv to allow us to use another algorithm to compute the quotient polynomial of lookup argument which does not need to compute inv_sums.

[kunxian-xia]

From the log that i run in scroll-prover#integrate-mv-lookup, the single-threaded construction of table_index_value_mapping (of type BTreeMap) cost most of time in getting m(X).

Details

``` ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................183.766ms ····Start: m(X) values ····End: m(X) values ...........................................................32.382ms ··End: prepare m(X) (inputs=[1], table=1) ......................................385.115ms ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................124.791ms ····Start: m(X) values ····End: m(X) values ...........................................................39.086ms ··End: prepare m(X) (inputs=[1], table=1) ......................................277.176ms ··Start: prepare m(X) (inputs=[1, 1, 1, 1, 1, 1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................842.687ms ····Start: m(X) values ····End: m(X) values ...........................................................159.388ms ··End: prepare m(X) (inputs=[1, 1, 1, 1, 1, 1], table=1) .......................1.364s ··Start: prepare m(X) (inputs=[1, 1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................819.464ms ····Start: m(X) values ····End: m(X) values ...........................................................58.297ms ··End: prepare m(X) (inputs=[1, 1], table=1) ...................................1.015s ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................209.752ms ····Start: m(X) values ····End: m(X) values ...........................................................31.558ms ··End: prepare m(X) (inputs=[1], table=1) ......................................352.026ms ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................122.706ms ····Start: m(X) values ····End: m(X) values ...........................................................32.563ms ··End: prepare m(X) (inputs=[1], table=1) ......................................306.619ms ```

[kunxian-xia]

After the commit https://github.com/scroll-tech/halo2/pull/71/commits/d901014b088601b994a427a22ef280f217214b5a, the time to get m(X) is reduced from 90.3s to 59.1s (1.52x speedup, the actual speedup is way more larger than 1.52 because the total time includes msm of m(X)).

Details

``` ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................13.899ms ····Start: m(X) values ····End: m(X) values ...........................................................39.055ms ··End: prepare m(X) (inputs=[1], table=1) ......................................235.166ms ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................12.956ms ····Start: m(X) values ····End: m(X) values ...........................................................35.646ms ··End: prepare m(X) (inputs=[1], table=1) ......................................171.269ms ··Start: prepare m(X) (inputs=[1, 1, 1, 1, 1, 1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................28.507ms ····Start: m(X) values ····End: m(X) values ...........................................................156.136ms ··End: prepare m(X) (inputs=[1, 1, 1, 1, 1, 1], table=1) .......................508.344ms ··Start: prepare m(X) (inputs=[1, 1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................31.129ms ····Start: m(X) values ····End: m(X) values ...........................................................58.307ms ··End: prepare m(X) (inputs=[1, 1], table=1) ...................................199.723ms ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................24.431ms ····Start: m(X) values ····End: m(X) values ...........................................................33.412ms ··End: prepare m(X) (inputs=[1], table=1) ......................................179.188ms ··Start: prepare m(X) (inputs=[1], table=1) ····Start: table index value mapping ····End: table index value mapping .............................................16.331ms ····Start: m(X) values ····End: m(X) values ...........................................................31.003ms ··End: prepare m(X) (inputs=[1], table=1) ......................................216.743ms ```

[kunxian-xia]

@huwenqing0606 It will be great to refactor your hackmd doc based on the change (https://github.com/scroll-tech/halo2/pull/71/commits/d901014b088601b994a427a22ef280f217214b5a) of how m(X) is calculated.

For example, if some input element e occurs in 3 different places (with indices idx1, idx2, idx3) in the table t, then m(t[idx1]) = 0, m(t[idx2]) = 0, m(t[idx3]) = 1. After this change, it becomes m(t[idx1]) + m(t[idx2]) + m(t[idx3]) = 1.

[huwenqing0606]

@huwenqing0606 It will be great to refactor your hackmd doc based on the change (d901014) of how m(X) is calculated.

For example, if some input element e occurs in 3 different places (with indices idx1, idx2, idx3) in the table t, then m(t[idx1]) = 0, m(t[idx2]) = 0, m(t[idx3]) = 1. After this change, it becomes m(t[idx1]) + m(t[idx2]) + m(t[idx3]) = 1.

good point. I will revise the doc accordingly.

[lispc]

should user call chunk_lookups himself? if not, this method should better be pub(crate)? If yes, what if he forgets to call this method?

[lispc]

another issue i considered is that, it joining of looked table expressions identifier enough to be "globally uniq". I guess so. Anything may worth being careful when we change codes in the future.