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

Nockma compilation: arguments to some operations still get duplicated #3013

Closed
lukaszcz opened this issue Sep 9, 2024 · 1 comment · Fixed by #3070
Closed

Nockma compilation: arguments to some operations still get duplicated #3013

lukaszcz opened this issue Sep 9, 2024 · 1 comment · Fixed by #3070
Assignees
@lukaszcz
Labels
anoma backend:nockma bug priority:high
Milestone
0.6.7

Comments

@lukaszcz
Copy link
Collaborator

lukaszcz commented Sep 9, 2024 •
edited
Loading

For example, the argument of OpArgsNum is duplicated. OpArgsNum is used whenever there is a dynamic closure call (call of unknown closure). The argument to OpArgsNum is copied over twice. This will be then evaluated twice.

This can change the complexity of recursive functions returning closures from linear to exponential.
@lukaszcz lukaszcz added this to the 0.6.7 milestone Sep 9, 2024
@lukaszcz
Copy link
Collaborator Author

lukaszcz commented Sep 9, 2024

We should look through the code carefully and remove all duplication. We cannot duplicate anything -- this is not a constant-factor inefficiency. It can change the asymptotic complexity to exponential!

@lukaszcz lukaszcz changed the title Arguments to some operations still get duplicated Nockma compilation: arguments to some operations still get duplicated Sep 10, 2024
@lukaszcz lukaszcz self-assigned this Sep 13, 2024
@lukaszcz lukaszcz mentioned this issue Sep 27, 2024
Merged
lukaszcz added a commit that referenced this issue Oct 8, 2024
@lukaszcz
Avoid duplication in Nockma code generation (#3070)
a3bfaca 
* Closes #3013 
* Removes all remaining problems with evaluation duplication that could
potentially lead to an exponential blow-up in the running time.
* Adds the capacity to generate saves of temporary values in the Nock
code generation backend.
* Removes the `TempHeight` transformation on JuvixTree. It is no longer
needed.
* Removes the `ComputeCaseANF` transformation on JuvixCore from the
Anoma pipeline. It is no longer necessary.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@lukaszcz lukaszcz

Labels
anoma backend:nockma bug priority:high
Projects
None yet
Milestone
0.6.7
Development

Successfully merging a pull request may close this issue.

Avoid duplication in Nockma code generation anoma/juvix
1 participant
@lukaszcz