topologically sort changes before applying

[nornagon]

This topologically sorts changes before application.

In the worst case, if the change list was sorted in reverse topological order, applyChanges would traverse the change list O(N^2) times. By first sorting the incoming changes topologically, we reduce that to O(N + E), where E is the number of dependency edges.

[ept]

Hi @nornagon, thank you for this. It's good to speed up applyChanges in the case where the changes are in reverse order. However, I expect that the common case for many applications will be that the changes are already topologically sorted, and in this case we're now doing extra work that we weren't doing before. Though I haven't yet benchmarked this to measure if there is a noticeable performance impact.

Also, is it safe to do the recursive call of visit() for each change? I'm concerned that if we try to apply a large number of changes at once, we might overflow the stack.

[nornagon]

I think this should be still quite fast in the case of sorted changes, the algorithm is O(N + E) with a quite small constant.

The stack size limit is a good call-out though, I'll convert this to use an explicit stack.