Optimization: construct_ml_poly, R1CSShape::multiply_vec

[sragss]

https://github.com/a16z/Spartan2/blob/uniform_r1cs_shape/src/spartan/snark.rs#L189-L201

Construction of Multilinear Polynomials is quite slow.

First the poly_uCz_E computation can be parallelized.

Secondly the R1CSShape::multiply_vec function may be suboptimal. https://github.com/a16z/Spartan2/blob/uniform_r1cs_shape/src/r1cs.rs#L137

• Strikes me that the reuse of the z[col] variable means that the A, B, C matrices should be jointly iterated
• I'm uncertain of the representation of the M elements in the A, B, C matrices. It's possible these are sparse or out of order making these iterators more complicated.
• Finally I'd guess that the elements of A, B, C, z have high density of 0 / 1 / small field elements. Likely worth optimizing for these edge-cases.

I will push a span called construct_ml_polynomials which instruments this section.

I believe this one is best done experimentally.

[sragss]

3x from: #12