$O(N^2)$ scaling in NumberedObjectCollection.append_renumber

[MicahGale]

Bug Description

While making model_builder.py for #743 I found this terrible performance. The script uses append_renumber exclusively. I suspect there is an $O(N)$ operation inside of this method, which when called $O(N)$ times leads to an $O(N^2)$ operation.

To Reproduce

I collected some data using the following script using concurrent

import numpy as np
import io
from model_builder import create_problem
import cProfile
import pstats
from pstats import SortKey

def dump_stats(n_cells):
    pr = cProfile.Profile()
    pr.enable()
    create_problem(n_cells)
    pr.disable()
    pr.dump_stats("foo.prof")
    stats = pstats.Stats("foo.prof")
    stats.print_stats("append_renumber", 20)                                                                                                                            

def collect_samples():
    grid = np.geomspace(10, 10_000, 4)
    for n_cells in grid:
        n_cells = int(n_cells)                                                                                                                                                  print(f"****************** {n_cells} ***************")
        dump_stats(n_cells)                                                                                                                                             
collect_samples()

Lazy Data

This then printed the following.

Details

****************** 10 ***************
Thu Jul 17 07:53:14 2025    foo.prof

         572145 function calls (512394 primitive calls) in 0.208 seconds

   Random listing order was used
   List reduced from 806 to 1 due to restriction <'append_renumber'>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
       25    0.000    0.000    0.002    0.000 /home/mgale/miniforge3/lib/python3.12/site-packages/montepy/numbered_object_collection.py:588(append_renumber)


****************** 100 ***************
Thu Jul 17 07:53:16 2025    foo.prof

         5389068 function calls (4785694 primitive calls) in 1.521 seconds

   Random listing order was used
   List reduced from 601 to 1 due to restriction <'append_renumber'>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      218    0.000    0.000    0.046    0.000 /home/mgale/miniforge3/lib/python3.12/site-packages/montepy/numbered_object_collection.py:588(append_renumber)


****************** 1000 ***************
Thu Jul 17 07:53:30 2025    foo.prof

         57065549 function calls (52007331 primitive calls) in 14.020 seconds

   Random listing order was used
   List reduced from 601 to 1 due to restriction <'append_renumber'>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1867    0.004    0.000    2.067    0.001 /home/mgale/miniforge3/lib/python3.12/site-packages/montepy/numbered_object_collection.py:588(append_renumber)


****************** 10000 ***************
Thu Jul 17 07:59:36 2025    foo.prof

         1724541013 function calls (1675885071 primitive calls) in 365.843 seconds

   Random listing order was used
   List reduced from 601 to 1 due to restriction <'append_renumber'>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    18098    0.045    0.000  235.570    0.013 /home/mgale/miniforge3/lib/python3.12/site-packages/montepy/numbered_object_collection.py:588(append_renumber)

The fact that the percall times are not constant mean this is not running in $O(N)$ time.

Version

• Version 1.1.2.dev62+gf21abe82

[digvijay-y]

May I?

[MicahGale]

Of course. Keep in mind this shows up when append_renumber is called $N$ times. So you are looking for an $\mathcal{O}(N)$ operation in append_renumber not necessarily an $\mathcal{O}(N^2)$ operation.