Skip to content
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

Optimize Brillig reference count tracking #4522

Closed
jfecher opened this issue Mar 11, 2024 · 0 comments · Fixed by #4525
Closed

Optimize Brillig reference count tracking #4522

jfecher opened this issue Mar 11, 2024 · 0 comments · Fixed by #4525
Labels
enhancement New feature or request

Comments

@jfecher
Copy link
Contributor

jfecher commented Mar 11, 2024

Problem

#4472 caused a regression in reference count tracking in Brillig. increment_rc instructions are issued more often now which caused the size of certain programs to increase quite a bit. Performance can also worsen when these are increased past 1 since this necessitates copies for mutable arrays.

Happy Case

We try to keep reference counts down by:

  • Introducing a decrement_rc instruction called when an array is last used
  • Possibly introducing a reference count removal optimization pass. The classic example of this is removing paired inc/dec instructions where they're unneeded - e.g. the array is not mutated. We could also consider trying to add this without the decrement instruction since it is possible to borrow an array without mutating it. Care just needs to be taken to ensure the borrowed array doesn't live on after the function call.

Project Impact

None

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response
@jfecher jfecher added the enhancement New feature or request label Mar 11, 2024
@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Mar 11, 2024
@jfecher jfecher mentioned this issue Mar 11, 2024
Merged
5 tasks
github-merge-queue bot pushed a commit that referenced this issue Mar 13, 2024
@jfecher @sirasistant
chore: Add Instruction::DecrementRc (#4525)
d8710c4 
# Description

## Problem\*

Resolves #4522

## Summary\*

Experimenting with this to see how much it improves performance of
unconstrained code using arrays.

## Additional Context

Currently the new dec_rc instruction is only issued for function
parameters when a function is finished - assuming the parameters are not
also returned.

CC @sirasistant for visibility

## 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.

---------

Co-authored-by: Álvaro Rodríguez <sirasistant@gmail.com>
@github-project-automation github-project-automation bot moved this from 📋 Backlog to ✅ Done in Noir Mar 13, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request
Projects
Noir
Archived in project
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

chore: Add Instruction::DecrementRc noir-lang/noir
1 participant
@jfecher