idaholab / MontePy

MontePy is the most user friendly Python library (API) to read, edit, and write MCNP input files.
https://www.montepy.org/
MIT License
32 stars 7 forks source link

remove o(n^2) operation from NumberedObjectCollection #563

Closed MicahGale closed 1 month ago

MicahGale commented 1 month ago

Description

As described in #556 there was an O(N^2) operation for appending N items to a NumberedObjectCollection. This was because self.numbers (which is an O(N) generator) was checked every append. This was fixed by:

  1. Moving all number conflict checks to the existing check_number
  2. Trusting __num_cache explicitly iff this problem is linked to a problem.
  3. creating a method: _update_number that updates __num_cache appropriately when a number is changed.
  4. Ensuring all Numbered_MCNPObject instances run _update_number if they are attached a problem. This is why __num_cache is trusted in this case.

This doesn't remove all bottlenecks and get us to O(N) time, but it does make append no longer a bottle neck as can be seen in the profiling results.

Don't review this until #539 is merged because this is built off of that branch.

Fixes #556

Checklist

MicahGale commented 1 month ago

This depends on #539

MicahGale commented 1 month ago

There is still an O(N^2) call to .numbers:

Function                                                                                                                  was called by...
                                                                                                                              ncalls  tottime  cumtime
/home/mgale/mambaforge/envs/data/lib/python3.12/site-packages/montepy/numbered_object_collection.py:75(numbers)           <-   28498    0.018    0.022  /home/mgale/mambaforge/envs/data/lib/python3.12/site-packages/montepy/data_inputs/universe_input.py:157(push_to_cells)
                                                                                                                            25937845   18.944   95.303  /home/mgale/mambaforge/envs/data/lib/python3.12/site-packages/montepy/numbered_object_collection.py:192(append)
MicahGale commented 1 month ago

I can't replicate this O(N^2) behavior. I wonder if the wrong version of MontePy was used in the test.

MicahGale commented 1 month ago

Upon further examination this was a problem with my tests. If you look at the profile results in the CI, numbers doesn't even show up and append is very low on the list. So I think we can say this was solved.

tjlaboss commented 1 month ago

Two small changes to make.

MicahGale commented 1 month ago

No change in memory usage (duh), but went from 27.6 seconds to 26.7 seconds for this improvement. This is a 3% reduction for the "big model". Though this is a low cost O(N^2) operation, and the saving should scale accordingly.