Topological order update

[ra1028]

Pull Request Type

• [ ] Bug fix
• [x] New feature
• [ ] Refactoring
• [ ] Documentation update
• [ ] Chore

Description

Problem

Currently, the transitive updates of the downstream when atom is updated are done in random order. Also, if an equivalent dependency (atom or subscription) appears multiple times in the dependency graph, it will be updated by that number. This not only causes redundant recalculation of atoms and updates of views but can even cause glitches due to atoms being updated while some of the dependencies are still out of date.

For example, the following case:

graph TD;
    A-->B;
    A-->C;
    B-->D;
    C-->D;
    C-->E;
    D-->E;

In this case, the worst update order would be: A -> B -> D -> E -> C -> D -> E -> E which updates E three times, and D twice, while the first update of D consumes an outdated state of C as C is yet to be updated at the time, and then accordingly E consumes an outdated value of C & D twice. This is a significant issue in the performance of apps that use Atoms for state management.

Solution

Introduce a topological sorting algorithm to give the correct order for transitive updates. In the example given above, the topological sorted order will be: A -> B -> C -> D -> E or A -> C -> B -> D -> E which doesn't contain redundant transitive updates while guaranteeing that all updates of its dependencies are completed before the atom is updated. Since there is no reasonable factor between B and C that determines their update order, which pattern of those it will be is random.

Algorithm

DFS topological sorting [ref].

• DFS: (Depth-first search)
• BFS: (Breadth-first search)
• Vertex: represents a node of a graph such as atom or subscription(view)
• Edge: represents a relation between vertex and vertex, such as atom to atom or atom to subscription

DFS is a better fit to the library's data structure than BFS. Although DFS implementations typically use recursive functions and are vulnerable to stack overflows, Atom's dependencies cannot realistically be that deep. Also, Swift's -O compile should optimize the recursive function to be equivalent to an implementation using while.

Normally, DFS aborts downstream traversal at the point where the vertex has already been traced, but this library doesn't abort and always traverses to the end of the graph while avoiding pushing the redundant edges to the sorted array. This is necessary to re-evaluate redundant edges later. In the case of the above example, the sorted order is A -> B -> C -> D -> E, and let's say that when the state of D is updated, it is revealed that there's no need to update downstream as the new value has not changed from the old value (assuming that D is an atom with changes modifier). Even then, its downstream, E needs to be transitively updated as it depends on C, otherwise E will not reflect the changes of C. To avoid this problem, redundant edges omitted during sorting are collected, and when the above situation occurs, it checks if the recorded edges contain the target vertex to determine whether it still needs updating. The redundant edges in the example are:

• B -> D
• C -> E

Performance

The complexity of the algorithm is O(|V|+|E|) where V = Vertices, E = Edges, which is done in a linear time. It is conceptually a bit slower than the current implementation but the result of the benchmark testing I have done showed that the performance from both clock time and memory perspective is almost the same as before in general cases while ensuring that it prevents additional causes of low performance such as redundant builds of atoms/views that are the most important part of app performance.

• Benchmark test