Switch to using rayon exclusively

[ebfull]

Right now we use futures-cpupool for one purpose (work stealing) and crossbeam for another (scoped threads). I can get both of these with rayon, which is also more mature, but in the past when I switched to rayon it was slower.

I think there are tweaks and new features in its API which would allow me to adopt it entirely.

[Pratyush]

PS @ebfull, did you have any notes on why Rayon was slower? In Zexe we switched to using only rayon, and it has made the MSM ~10-15% slower. (Even when the new code is structured almost identically to the old code).

[hdevalence]

I don't know about bellman, but in a very early version of Bulletproofs we tried using Rayon for the parallel parts of the inner product proof and got minimal speedup even for a very parallel task. I don't think we dug super far into it but from perf counters it seemed that it was doing a ton of context switches. Perhaps the work-stealing has more overhead than expected?

[Pratyush]

Hmm how large were those inner product proofs? Perhaps on small instance sizes the overhead is too large? In our case, an MSM over large inputs does noticeably speed up when parallelized, but is still slower than bellman's MSM on the same input size.

Moreover, futures_cpupool also does work-stealing. It would be quite interesting to investigate if, in some cases, futures_cpupool achieves lower overhead for work-stealing than rayon; maybe the lessons learnt could be used to improve rayon as well.

[hdevalence]

I don't remember the size but I believe the timings were in the range of 1-20 ms.

[Pratyush]

OK so I did some investigation, and came up with the following hypothesis: using futures_cpupool in the Groth16 prover gives better performance than using rayon because somehow futures_cpupool::CpuPool schedules tasks for the MSM better than rayon does when there are multiple MSMs happening in quick succession.

To justify this hypothesis, I performed the following test: I modified the multiexp code to create a new CpuPool for each invocation (so CpuPools are not shared by different MSMs). The resulting code has the ~same performance as the rayon-ized version. When used in the Groth16 prover, it results in worse performance than what's currently in master.