lurk-lab / lurk-rs

Lurk is a Turing-complete programming language for recursive zk-SNARKs. It is a statically scoped dialect of Lisp, influenced by Scheme and Common Lisp.
https://lurk-lang.org/
Apache License 2.0
418 stars 54 forks source link

feat: witness caching now operates on a bounded buffer #1215

Closed huitseeker closed 3 months ago

huitseeker commented 3 months ago

What's in this PR?

This removes the assumption that prove_recursively has access to the whole set of multiframes, by :

[!NOTE] This PR is split in commits matching the above bullet points, the Commits view will let you inspect them separatedly.

Next Steps

Transferring the above memory-sparse semantics to prove_from_frames,evaluate_and_prove and other transitive consumers of prove_recursively. In other words, evaluation should, as much as is possible, produce an iterator of frames.

arthurpaulino commented 3 months ago

Also, I think the message direction you implemented is backwards. The main thread - the one doing the folding - should be the one requesting witnesses to be cached upfront

huitseeker commented 3 months ago

Right before folding starts at index i, we send that message via the mpsc API. Then, in the witness caching thread, we simply need to cache the witness of the MultiFrame at index i + 1.

This is already what's happening: as the main thread pulls item i, the witness caching thread starts preparing item (i + channel_capacity).

huitseeker commented 3 months ago

@arthurpaulino Insisting on this:

I wouldn't touch this until we have proper benchmarks for SuperNova folding.

What's the issue for this, describing the gap precisely?

If we have doubts regarding performance optimizations, it would be helpful to have benchmarks that justify those performance optimizations - and until we do, descriptions of what work needs to be accomplished for those benchmarks to exist.

I opened #1219