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

Fix O(N^2) operation in Material #510

Closed
MicahGale opened this issue Aug 26, 2024 · 2 comments · Fixed by #518
Closed

Fix O(N^2) operation in Material #510

MicahGale opened this issue Aug 26, 2024 · 2 comments · Fixed by #518
Labels
code improvement A feature request that will improve the software and its maintainability, but be invisible to users. performance 🐌 Issues related to speed and memory

Comments

@MicahGale
Copy link
Collaborator

MicahGale commented Aug 26, 2024

          My thoughts so far on the these results.
  1. I realized a very bad implementation detail: In MCNP_Probelm.update_pointers there is a for data_input in self.data_inputs loop effective.
    1. This then calls Material.update_pointers which has: for data_input in data_inputs: loop.
    2. That's right: I wrote an O(N2) operation! 🎉 🎉 I found the worst implementation to do.
    3. This operation is linking M to MT. If we did vice versa MT could use hashing to move to an O(1) operation.
    4. This is an easy fix
  2. Why is Material.__hash__ getting called so much? NumberedObjectCollection is meant to hash on numbers and not objects I thought. There is something weird going on here that needs further investigation.
@MicahGale MicahGale added the code improvement A feature request that will improve the software and its maintainability, but be invisible to users. label Aug 26, 2024
@MicahGale
Copy link
Collaborator Author

See also: #137 (comment)

@MicahGale
Copy link
Collaborator Author

Some new profiling data:

1    0.000    0.000  272.390  272.390 /opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/montepy/input_parser/input_reader.py:6(read_input)
        1    0.026    0.026  272.390  272.390 /opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/montepy/mcnp_problem.py:236(parse_input)
        1    0.002    0.002  253.773  253.773 /opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/montepy/mcnp_problem.py:304(__update_internal_pointers)
     1001    0.363    0.000  252.7[21](https://github.com/idaholab/MontePy/actions/runs/10586963944/job/29336774706?pr=513#step:7:22)    0.252 /opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/montepy/data_inputs/material.py:173(update_pointers)

So this is very very inefficient. I think if this were fixed we could open the benchmark case in ~20 seconds?

MicahGale added a commit that referenced this issue Aug 28, 2024
@MicahGale MicahGale changed the title Fix O(N^2) operation in Material Fix O(N<sup>2</sup>) operation in Material Aug 28, 2024
@MicahGale MicahGale changed the title Fix O(N<sup>2</sup>) operation in Material Fix O(N^2) operation in Material Aug 28, 2024
@tjlaboss tjlaboss added the performance 🐌 Issues related to speed and memory label Aug 28, 2024
MicahGale added a commit that referenced this issue Aug 28, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
code improvement A feature request that will improve the software and its maintainability, but be invisible to users. performance 🐌 Issues related to speed and memory
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants
@MicahGale @tjlaboss and others