Inneficiency from extra frame

[arthurpaulino]

Suppose that rc == 1000 and our computation needed precisely 1000 frames. But our functions that generate frames are adding an extra padding (trivial, terminal -> terminal) frame at the end. Then we end up with 1001 frames.

That extra frame, alone, is making our pipeline generate other 999 similar frames so we can fill the other multiframe up and we end up with 2000 frames in total.

This behavior is being expected as the correct behavior in Prover::expected_total_iterations, which is used in tests.

[porcuquine]

If I read this correctly, you're proposing to address this TODO.

[porcuquine]

If so, please make sure to address the need for care mentioned there. This also suggests we may want to defer any such minor optimization — since it seems plausible that we explicitly drop support for SnarkPack+ (which would simplify making this change safely).

[arthurpaulino]

Thanks a lot for enhancing the context of this issue!

[arthurpaulino]

I'll defer this change. Thanks again 🙏🏼

[johnchandlerburnham]

Would be awesome if we could s/Dangerous/Inefficient/g and reserve "danger" for things which have semantics-breaking implications, which this, afaiu, does not

[porcuquine]

For clarity, it's not even really an inefficiency in the algorithmic sense. Once in rc times, a single extra fold may be required. This isn't significant in any normal use case. This is mainly an issue in the weird edge cases like our ivc sha256 benchmark, where for comparative purposes we're trying to avoid folding.