Experiment with reducing the number of edges added to the plugin graph

[Ortham]

During sorting, as adding many edges between all the plugins in a large load order takes longer than loading the plugins.

Moved from loot/loot#761.

[Ortham]

Elminster recently mentioned on the discord that it takes them over a minute to sort with 237 plugins, so this needs looking at to speed things up, as that's way too slow.

[ElminsterAU]

LOOTDebugLog - slow sort.zip

[Ortham]

Significant times:

[06:47:46.253423] [info]: Beginning sorting operation.
[06:47:46.253638] [trace]: Scanning for plugins in D:\Program Files (x86)\Steam\steamapps\common\Skyrim Special Edition\Data
[06:47:46.884826] [info]: Loading 360 plugins using 6 threads, with up to 60 plugins per thread.
[06:48:23.319488] [info]: Merging masterlist, userlist into plugin list, evaluating conditions and checking for install validity.
[06:48:23.427165] [info]: Sorting groups according to their load after data
[06:48:23.448703] [info]: Fetched existing load order: 
[06:48:23.456337] [info]: Adding edges to plugin graph.
[06:48:23.456354] [debug]: Adding non-overlap edges.
[06:48:24.073319] [trace]: Adding hardcoded plugin edges.
[06:48:24.089595] [trace]: Adding group edges.
[06:48:26.171356] [debug]: Adding overlap edges.
[06:48:30.299561] [debug]: Adding tie-break edges.
[06:48:43.608859] [debug]: Checking to see if the graph is cyclic.
[06:48:43.615590] [debug]: Performing a topological sort.
[06:48:43.623396] [info]: Calculated order: 

The slowest bit is loading plugins to sort, which is in common with #35. There it took 34 seconds to load just plugin headers, here it takes 37 seconds to load the whole plugins, so I expect solving one will solve the other too.

There were 64620 edges added to the plugin graph, and no significantly slower stages of that process. Interestingly, this shows that even a very large number of edges doesn't cause the actual topological sort to be significantly slower, so the issue isn't necessarily the number of edges, but the process of adding them.

[ElminsterAU]

Just a further bit of information, I'm running LOOT from inside MO2.

[ElminsterAU]

Using the new dll from issue #35:

[18:36:45.612749] [info]: Beginning sorting operation.
[18:36:45.612879] [trace]: Scanning for plugins in D:\Program Files (x86)\Steam\steamapps\common\Skyrim Special Edition\Data
[18:36:46.243184] [info]: Loading 374 plugins using 6 threads, with up to 63 plugins per thread.
[18:36:48.792456] [info]: Merging masterlist, userlist into plugin list, evaluating conditions and checking for install validity.
[18:36:48.878598] [info]: Sorting groups according to their load after data
[18:36:48.896600] [info]: Fetched existing load order: 
[18:36:48.901434] [info]: Adding edges to plugin graph.
[18:36:48.901446] [debug]: Adding non-overlap edges.
[18:36:49.457822] [trace]: Adding hardcoded plugin edges.
[18:36:49.470739] [trace]: Adding group edges.
[18:36:50.942437] [debug]: Adding overlap edges.
[18:36:52.243500] [debug]: Adding tie-break edges.
[18:37:06.504596] [debug]: Checking to see if the graph is cyclic.
[18:37:06.509657] [debug]: Performing a topological sort.
[18:37:06.516022] [info]: Calculated order: 

LOOTDebugLog - slowish sort.zip

So that's an improvement from ~57sec to ~21sec.

[Ortham]

With the same plugins (plus a few I already had) and userlist, I get:

[18:19:53.732306] [debug]: Adding non-overlap edges.
[18:19:54.165335] [trace]: Adding hardcoded plugin edges.
[18:19:54.175309] [trace]: Adding group edges.
[18:19:55.793309] [debug]: Adding overlap edges.
[18:19:56.730309] [debug]: Adding tie-break edges.
[18:20:02.280335] [debug]: Checking to see if the graph is cyclic.

So ~ 9 seconds to do the actual sorting vs. your ~ 18 seconds, but the breakdown for the different stages is similar.

[Ortham]

@eFrysTon Try this DLL. I was only able to save a couple of seconds, but it's worth seeing what it does for you.

The plugin graph being very broad and shallow makes doing less in the tie-break edges stage tricky, I tried a bunch of things that didn't have any significant effect. I'm now going to try chucking threads at it, which should do the trick.

Edit: Nope, I significantly underestimated how many edges were being invalidated by those added earlier in the loop.

[ElminsterAU]

[05:19:43.514114] [info]: Beginning sorting operation.
[05:20:10.344114] [info]: Calculated order: 

~27sec

[05:24:19.152719] [info]: Beginning sorting operation.
[05:24:47.129978] [info]: Calculated order: 

~27sec

BUT, I don't have exactly the same load order anymore (maybe 10 additional modules added), so that may account for the time difference

[Ortham]

Well, I wasn't expecting much... I'm done with this for now, I've experimented and have a better understanding of the problem, but I'm out of ideas. I'll revisit it if I come up with anything new.

[ElminsterAU]

Thanks for all your work on this. I'm down to about 45 seconds starting the full loot from inside MO2, clicking sort, apply, and closing it. From originally 3-4 minutes when clicking the sort button in MO2.

So that's a pretty decent result.

[Ortham]

Closing this as I reduced the number of edges added to the plugin graph in v0.14.8, by caching added and found paths between plugin pairs. On my PC, the total number of edges reduced by ~ 2/3, and sorting speed ~ doubled.

There's more room for edge reduction, but it would involve extra graph traversal, so probably wouldn't give a performance improvement, and I don't plan to try it unless I come up with a good idea for how to do it.