I've never understood why this appeared to work, but I've seen this test fail twice due to SEH exceptions in the past week, so it's better off removed. Nothing should be relying on this working (and LOOT doesn't).
It's a typedef that's std::wstring on Windows and icu::UnicodeString on Linux, to simplify calling CompareFilenames() with cached pre-converted strings.
It's actually significantly faster to just check if the path you're
trying to create has already been cached than to check if it actually
already exists. This improves sorting performance by 15%.
Checking if a path exists is where sorting spends most of its time, and it gets slower the more edges the graph has, so avoid adding an edge between two plugins if there's already a path between them.
This improves sorting performance by 19%.
This doesn't add any additional path checks, as all the specific and hardcoded edges need to be added to ensure their validity (by then checking for cycles), and tie-breaking is more complicated so is worth dealing with separately.
The new logic is conceptually simpler, with fewer special cases to
handle. Unlike the old implementation, the new approach avoids cycles.
It basically does depth-first searches through the group graph, adding
edges from each group's plugins to the plugins in the group's
successors.
This involved reversing the direction of edges in the group graph, as
this switches the logic from trying to find predecessors to trying to
successors: the new direction matches that of plugin graph edges, so
it's less confusing.
I can't think of a situation in which the iteration order of plugins
within a group matters. I tested it manually with my test load order of
~1600 plugins, and saw no difference when the order was randomly
shuffled. I've added a test case but it's a relatively simple scenario
and there may be a more complex scenario where it would matter that I
haven't thought of.
A buffer is used to hold the plugins in the previous groups in the
current path, because that's noticeably faster than just recording the
path and looking up the plugins for each group in the path. It does
duplicate the group vectors, but that's an insignificant amount of
memory used.
The new approach has a negative performance impact, with sorting now 15%
slower than before.
A more efficient solution could be to implement a custom DFS algorithm
that doesn't stop when it reaches a vertex it's already visited (which
would be fine since the graph has already been validated to be acyclic),
as then only the root vertices would need to be searched from.
Pass the groups graph in and derived everything from it. This
duplicates a little work between the two plugin graphs (the group
vertex map and group predecessors map could be shared), but the group
graph is generally small enough that it doesn't seem to be significant.
So that the graph vertices and edges have a consistent order independent of the order that the metadata is defined in.
This is less of a concern than for plugins because the order of the metadata is something that the author controls, but having the metadata order matter could be surprising and doesn't seem useful.
Oliver Hamlet
Oliver HamletandOliver Hamlet