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.

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

Replace BTreeSets used in MergeExpressionsOptimizer with an enum #6560

Open
TomAFrench opened this issue Nov 20, 2024 · 0 comments
Open

Replace BTreeSets used in MergeExpressionsOptimizer with an enum #6560

TomAFrench opened this issue Nov 20, 2024 · 0 comments
Assignees

Comments

@TomAFrench
Copy link
Member

TomAFrench commented Nov 20, 2024

In merge_expression.rs, we currently track all of the opcodes which reference a particular witness index in a

BTreeMap<Witness, BTreeSet<usize>>

As we don't need to track these sets past 2 opcodes referencing a witness, this would be more efficient if we were to instead use

enum ReferencingOpcodes {
    One(usize),
    Two(usize, usize),
    Many,
}

BTreeMap<Witness, ReferencingOpcodes>

This avoids needing to track witnesses other than the ones which can potentially be optimized out in future. This means that even in the case where a million opcodes reference a single witness then we can represent this with the memory equivalent of 2 usizes.

@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Nov 20, 2024
@TomAFrench TomAFrench assigned guipublic and TomAFrench and unassigned guipublic Nov 20, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: 📋 Backlog
Development

No branches or pull requests

2 participants