Ortham
commented
1 year ago I've come up with an approach that I think is conceptually simpler and results in fewer edges being added. The algorithm is:
- Create a graph of the groups, with edges going from groups that load earlier to groups that load later.
- Create a set for storing groups that have already been processed/finished
- For each root vertex, i.e. groups that don't load after any other group, perform a DFS to visit all the groups that load after it:
- Create a stack of buffers for holding plugins at different levels of the DFS
- Create a stack of groups for holding the groups that have been encountered at different levels of the DFS
- On examining a new out edge (a tree edge - before discovering the vertex at the other end):
- Add the target group to the stack.
- Find all the plugins in the target group
- Create a buffer for plugins, but don't add it to the stack
- For each plugin in the last buffer on the stack:
- For each target plugin:
- Add an edge going from the buffered plugin to the target plugin, unless adding the edge would cause a cycle.
- If there are no target plugins or if one or more edges were skipped (due to causing cycles), add the buffered plugin to the new buffer (to carry it forwards to the next target group to be processed if this target group has any successors).
- For each target plugin:
- Find all the plugins in the source group
- For each source plugin:
- Do the same as for the plugins in the last buffer on the stack above.
- Add the new buffer to the stack
- Once a vertex has been finished (i.e. all its out-edges have been processed):
- Pop the last group off the stack.
- Pop the last buffer off the stack.
This approach adds edges only between plugins in groups that are directly connected, unless that's not possible, and then the edge is added between the preceeding group's plugin and the closest successor that an edge can be added to without causing a cycle. If a target group contains no plugins, this effectively propagates all the source's plugins as sources for the target group's targets.
The set for storing groups is simply the DFS colour map, but it's shared between DFSes because if one DFS already added edges going from one group's plugins, there's no point in doing the same if that same group is encountered from a different starting point in another DFS, that won't add anything new.
The group stack is used when adding an edge between two plugins to see if the path between the plugins' groups involves any user metadata, so that the edge type can be set appropriately. The type also takes into account if either plugin is part of its group due to user metadata.
I initially had the logic buffering a plugin when all of its edges to the target group plugins were skipped, but changed that to when any of them were skipped because the former causes successor edges to get skipped incorrectly. For example, if we've got three groups A -> B -> C with plugins A1, A2, B1, B2, C1, C2 and existing edges B1 -> A1 and C1 -> B2, buffering on all skipped causes the path between A1 and C1 to be undefined, while buffering on any skipped causes the edge A1 -> C1 to be added. It does mean there are more redundant edges added, but too many is better than too few.
I've been making a lot of changes to how sorting works in order to speed it up, and so far sorting using the latest
abi-changesbranch build is about 290x faster than sorting using the v0.18.2 release (0.18.3 is about 5x faster). Most of the changes can cause libloot to produce different load orders in ways that shouldn't cause any problems, but I like to avoid doing that often, just in case.Group handling has changed to track whether a group edge involved user metadata or not, and its vertex lookup got optimised, but the general approach it takes hasn't changed, and that's something I want to revisit for two reasons:
Now's a good time to do this, because changes will probably affect the resulting load order, and so it would be good to lump them in with all the others that change the load orders that libloot produces.
Complexity
The current implementation for adding group edges grew organically after originally being implemented as an extension of "load after" metadata handling, and I think the code is pretty hard to understand and overcomplicated.
Also, unlike the new tie-breaking algorithm, which tries to enforce the old load order and otherwise minimally deviate from it, there's no real goal it has that can help explain why it chooses to add edges in the order it does, or skip those that it does, so it's hard to understand why it does what it does.
Performance
Following on from loot/loot#1370, adding edges between overlapping plugins is now usually the slowest part of sorting, but checking for overlaps is relatively fast (I tested separating the checking from the adding of edges: with my test load order, the overlap section takes 11 seconds, < 1 of which is checking for overlaps), the slow bit is checking for paths going in the other direction to avoid cycles.
Checking for paths can be sped up by reducing the number of edges in the graph. That can be done by not adding edges where there's already a path in the same direction, but that involves checking for a path and my testing suggests it doesn't do enough to counter its own performance hit. The other way to reduce edges is to try adding fewer edges to begin with. Edges overwhelmingly come from two sources: overlaps, and groups.
I can't see how to try adding fewer overlap edges, but the way group edges are added at the moment seems obviously non-optimal: each plugin gets an edge added to every plugin in every group that transitively loads before the group the plugin is in. In many of those cases, that's unnecessary, because the plugins it transitively loads after will also have edges to the plugins they load before. If no edges were skipped and all groups had plugins, you'd only need to add edges between a plugin and the plugins in the groups that its group directly loads after.