Comments (5)
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).
from bellman.
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?
from bellman.
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.
from bellman.
I don't remember the size but I believe the timings were in the range of 1-20 ms.
from bellman.
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.
from bellman.
Related Issues (20)
- Needed in Groth16?
- BLAKE2b support
- Parameters::read() with checked = true is broken
- no_std support in the future? HOT 1
- Option to use constant-time multiscalar multiplication
- why bellman depend on "ff", "group" and "paring" library using local path instead of crates.io or github
- why every input should has a constraints x*0=0, for index offset constraint? HOT 1
- Extract Groth16 implementation into separate crate HOT 1
- `Boolean` XOR HOT 3
- Batch verification: Choose `z` in the range `[1..2^128)`.
- Constraint system with arrays/ error in implementing batch mode HOT 3
- How Can I Create A MPC Trusted Setup With Bellman? HOT 2
- How to read generated files from snarkjs HOT 1
- About the order of a random point
- How `eval_at_tau` works?
- Inaccurate comment about VerifyingComment::ic
- Ask about performance
- Can not build due to missing libgmp on macOS Monterey 12.5.1
- I want some papers or blogs about the principles of "FFT" which used in "https://github.com/zkcrypto/bellman/blob/3c44bfe15358ae686f9e3780aaa4cbef8ec4a472/src/domain.rs#L316-L372 ". HOT 1
- Can't import bellman::pairing HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from bellman.