I had been suspecting for some time that pathfinding was slow due to, among other reasons, having to do heavyweight full-Star-object comparison. This PR chases down that rabbit hole.
The obvious solution was to assign a unique, integral, star ID (or index, as I called it) to each Star object as it's created. There were some minor snags that came up along the way and had to be fixed, but they were tedious and annoying, not problematic.
I could then further tweak the pathfinding to better suit integers as nodes - dropping the counter object (used to ensure tiebreaking in the status quo) was a nice gain.
I also took the opportunity to speed up the route-generation process (in TradeCalculation, at least) that using indexes enabled.
On the imperial-sectors list, pathfinding previously took 4 h 39 min 3 s (16,743 s), and my last test run took 3h 43 min 52 s (13,432 s) - a 19.8% reduction. I suspect that's evenly split between the direct effects of using indexes, and the pathfinding simplifications that allows.
Further efforts dropped pathfinding time to 2 h 6 min 42 s (7,602 s).
Thanks to @tjoneslo for his suggestion to unify the old stars and the new stars_shadow graphs - it simplified TradeCalculation notably.
The resulting blast damage touched the XRouteCalculation and CommCalculation classes, which had rotted to the extent of typoed variable names and language structures that are no longer valid in Python 3.6+. To reduce the chances of future silent breakage, I added some basic regression tests around those two classes. I can't claim my work around those two classes is comprehensive - I was more aiming at constraining where undetected breakage could happen.
I had been suspecting for some time that pathfinding was slow due to, among other reasons, having to do heavyweight full-Star-object comparison. This PR chases down that rabbit hole.
The obvious solution was to assign a unique, integral, star ID (or index, as I called it) to each Star object as it's created. There were some minor snags that came up along the way and had to be fixed, but they were tedious and annoying, not problematic.
I could then further tweak the pathfinding to better suit integers as nodes - dropping the counter object (used to ensure tiebreaking in the status quo) was a nice gain.
I also took the opportunity to speed up the route-generation process (in TradeCalculation, at least) that using indexes enabled.
On the imperial-sectors list, pathfinding previously took 4 h 39 min 3 s (16,743 s), and my last test run took 3h 43 min 52 s (13,432 s) - a 19.8% reduction. I suspect that's evenly split between the direct effects of using indexes, and the pathfinding simplifications that allows.
Further efforts dropped pathfinding time to 2 h 6 min 42 s (7,602 s).
Thanks to @tjoneslo for his suggestion to unify the old stars and the new stars_shadow graphs - it simplified TradeCalculation notably.
The resulting blast damage touched the XRouteCalculation and CommCalculation classes, which had rotted to the extent of typoed variable names and language structures that are no longer valid in Python 3.6+. To reduce the chances of future silent breakage, I added some basic regression tests around those two classes. I can't claim my work around those two classes is comprehensive - I was more aiming at constraining where undetected breakage could happen.