Skip to content

perf: lookup blueprint compile time improvement #899

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
gbotrel merged 6 commits into from
Nov 3, 2023
Merged

perf: lookup blueprint compile time improvement #899

gbotrel merged 6 commits into from
Nov 3, 2023

Conversation

@gbotrel
Copy link
Collaborator

@gbotrel gbotrel commented Nov 1, 2023

Partially fixes #898 (compile part).

Essentially, the Blueprint WireWalker(inst Instruction) (w WireWalker, maxLevel int) now returns a maxLevel which, alongside the fact that the callback passed into the walker returns the maxLevel of a wire, allows stateful blueprints like BlueprintLookupHint to cache some info avoiding useless computation by the compiler to figure out the instruction dependency tree.

Added a reference benchmark in logderivlookup:

BenchmarkCompileManyLookup/scs-10      12830216291     480989306     -96.25%
BenchmarkCompileManyLookup/r1cs-10     13002215583     687194500     -94.71%

@gbotrel gbotrel requested review from Tabaie and ivokub November 1, 2023 21:14
ivokub
ivokub approved these changes Nov 1, 2023
View reviewed changes
ivokub
ivokub reviewed Nov 1, 2023
View reviewed changes
@gbotrel
Copy link
Collaborator Author

gbotrel commented Nov 3, 2023

@ivokub did replace the weird WireWalker with double callback pattern with a simpler InstructionTree interface (see constraint/instruction_tree.go) .

Yields further perf improvements (against previoous commit on this branch):

benchmark                              old ns/op     new ns/op     delta
BenchmarkCompileManyLookup/scs-10      480989306     412605000     -14.22%
BenchmarkCompileManyLookup/r1cs-10     687194500     676015438     -1.63%

benchmark                              old allocs     new allocs     delta
BenchmarkCompileManyLookup/scs-10      8603276        5336556        -37.97%
BenchmarkCompileManyLookup/r1cs-10     9624679        8598475        -10.66%

benchmark                              old bytes      new bytes      delta
BenchmarkCompileManyLookup/scs-10      942962434      846228050      -10.26%
BenchmarkCompileManyLookup/r1cs-10     2033656932     2002813188     -1.52%

ivokub
ivokub approved these changes Nov 3, 2023
View reviewed changes
Copy link
Collaborator

@ivokub ivokub left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Now makes much more sense. Looks good! Dunno about having some checks behing debug tag - if these cases happen then it is a bug in gnark anyway, but I think it would be slightly easier to report and debug when having unique identifiers (instead of generic out-of-bounds err)

@gbotrel gbotrel merged commit 8669a6a into master Nov 3, 2023
@gbotrel gbotrel deleted the perf/blueprintlookup branch November 3, 2023 15:24
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@ivokub ivokub ivokub approved these changes

@Tabaie Tabaie Tabaie approved these changes

Assignees

No one assigned

Labels

type: perf

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

perf: lookup tables with many queries are slow to compile and solve

4 participants

@gbotrel @ivokub @Tabaie