Skip to content

nightly-2024-01-30: feat: multiply first to allow more ACIR gen optimizations (#4201)

Pre-release
Pre-release
Compare
Choose a tag to compare
@github-actions github-actions released this 30 Jan 02:10
· 1668 commits to master since this release
882639d
# Description

## Problem\*

Resolves <!-- Link to GitHub Issue -->

## Summary\*

I noticed that we were getting suboptimal acir generation when using
`.any()` on `BoundedVec` where the `exceededLen` check would get more
expensive the longer the `BoundedVec` was.

The issue turned out to be that because we we would sum before
multiplying when performing the ORs on the length check, we weren't
taking advantage of the fact that multiplication can result in one of
its inputs being replaced with a single witness if the result would have
been degree 3 or more.

This meant that rather than having a simple `a + b - 2ab` for each OR
with `a` and `b` being witnesses , `a` would consist of a quadratic and
2 linear terms. We'd then continue to pick up extra terms for each
element in the `BoundedVec`.

The simple fix is then whenever we are performing operations on two
arguments where one of those operations is a multiplication (or anything
which can result in a simplification) we should do that first in order
to apply those simplifications to the other operations.

## Additional Context



## Documentation\*

Check one:
- [x] No documentation needed.
- [ ] Documentation included in this PR.
- [ ] **[Exceptional Case]** Documentation to be submitted in a separate
PR.

# PR Checklist\*

- [x] I have tested the changes locally.
- [x] I have formatted the changes with [Prettier](https://prettier.io/)
and/or `cargo fmt` on default settings.