linkPerformance

To obtain a proper analysis of RxDeep's performance (and generally complexity of the problem it tries to solve), we need to establish a few definitions first. Assume we have a state tree looking like this:

1link{                                 // --> root of the state-tree

2link  name: 'Cool Team',              // --> a leaf node

3link  people: [                       // --> a middle node

4link    {                             // --> a middle node

5link      name: 'Jerome',             // --> a leaf node

6link      age: 42,                    // --> a leaf node

7link      address: {                  // --> a middle node

8link        city: 'Jersey',           // --> a leaf node

9link        country: 'Jibuti'         // --> a leaf node

10link      },

11link    },

12link    {                             // --> a middle node

13link      name: 'Jacqueline',         // --> a leaf node

14link      age: 27,                    // --> a leaf node

15link      address: {                  // --> a middle node

16link        city: 'Jakarta',          // --> a leaf node

17link        country: 'Jamaica'        // --> a leaf node

18link      }

19link    }

20link  ]

21link}

Two parameters of this tree are particularly important to analyzing complexity of the reactive change propagation problem:

• Number of leaf nodes, in this case 9 (name of the team, name and age of each person, and the city and country of their address). We denote this number by letter $n$.

• Depth of the tree, in this case 4 (you need 4 property resolutions to get from the root of the object to the deepest leaf node). We denote this number by letter $d$.

We will express complexity and performance of algorithms using the Big O notation, which is displayed with $\Omicron(f(n, d))$ syntax, since the complexity is always expressed as a function of $n$ and $d$.

Parameters $n$ and $d$ are independent. State-tree can be an array with a thousand strings, where we would have $n$ = 1000, $d$ = 1, or it can be a single string nested in 1000 arrays ([[[...['x']...]]]), where we would have $n$ = 1, $d$ = 1000. We say a state-tree is typical, if $d$ is in the order of $\log(n)$, i.e.

In practice, most of the time you have lower bounds and upper bounds on average number of childs each node of the state-tree has, which would mean that in practice most state-trees are typical.

linkChange in Leaf Nodes

For changes in a single leaf node, the node itself should emit a change, its parent should emit a change, the parent of its parent should emit a change, and all the path from the node to the root state should emit changes:

1linkconst root = state([{address: { city: 'Jakarta' }}]);

2linkconst mid1 = root.sub(0);

3linkconst mid2 = mid1.sub('address');

4linkconst leaf = mid2.sub('city');

5link

6linkleaf.value = 'Jacksonville';

7link

8link// Now leaf, mid2, mid1 and root must emit changes.

This means that each change in a leaf node must result in at least $\Omicron(d)$ operations, independent of the underlying algorithm. For a typical state-tree, that would be $\Omicron(\log(n))$ operations.

For each such change, RxDeep performs one assignment by reference (to update local state's value) without emission, and constructs a trace object, passing the change with the trace object to the upstream. This would result in $\Omicron(d)$ operations until the change reaches the root of the state-tree (alongside $\Omicron(d)$ trace objects).

The root state then typically bounces the change back. Each recepient state will emit the new value, and perform equality checks between all of its generated sub-keys and head of received trace. On match, it will extract the downstream trace and pass down the resulting change to the matching sub-key. Assuming an average number of $k$ sub-states per state, this yields $\Omicron(kd)$ equality checks and $\Omicron(d)$ emissions until the change is fully propagated across the state-tree.

Since $k$ is a constant, this overall yields $\Omicron(d)$ operations to fully propagate each change across the state-tree, $\Omicron(\log(n))$ for typical state-trees, matching the lower complexity bound for any solution.

linkChange in Arbitrary Nodes

Change in an arbitrary node might result in a change in all of the nodes of a state-tree, which subsequently should result in $\Omicron(nd)$ change emissions ($\Omicron(n \log(n))$ for a typical state-tree).

More specifically, if a change is issued at a node at depth $\delta$, with a sub-tree of $n_{\delta}$ nodes, then nodes on the path from the changed node up to the root should emit a change ($\Omicron(\delta)$ emissions), and possibly the whole sub-tree under the changed node should also emit ($\Omicron((d - \delta)n_{\delta})$ emissions). Overall this would amount to $\Omicron(\delta + (d - \delta)n_{\delta})$ operations. Assuming a typical tree, we would have:

Which would give the minimum number of operations for change at depth $\delta$ at:

Maximized on $\delta = 0$ or $n_{\delta} = n$, i.e. on the root state, and minimized on $\delta = d$ or $n_{\delta} = 1$, i.e. a leaf state.

1linkconst root = state([{address: { city: 'Jakarta', country: 'Indonesia' }}]);

2linkconst mid1 = root.sub(0);

3linkconst mid2 = mid1.sub('address');

4linkconst leaf1 = mid2.sub('city');

5linkconst leaf2 = mid2.sub('country');

6link

7linkmid2.value = { city: 'Jambi', country: 'Indonesia' };

8link

9link// due to this change, mid2 itself, mid1, root and leaf1 should re-emit.

10link// however the value for leaf2 hasn't changed and it shall not re-emit.

From the changed state upwards (towards the root), RxDeep behaves as before as it can fully track changes, resulting in $\Omicron(\delta)$ or $\Omicron(\log(n) - \log(n_{\delta}))$ operations (the latter holding for a typical state-tree).

For downward propagation, the state conducts a sweep of its sub-tree and complete the trace. This is called post-tracing, and in worst-case scenario it requires $\Omicron(n_{\delta}\log(n_{\delta}))$ operations. After that changes can be down-propagated precisely, and since in worst-case all of the sub-tree nodes would need to emit due to changes, adding another $\Omicron(n_{\delta}\log(n_{\delta}))$ emissions.

This means in total the change propagation mechanism requires $\Omicron(\log(n) + (2n_{\delta} - 1)\log(n_{\delta}))$ operations, which is of the same order at the minimum calculated above, i.e.

linkKeyed States

A Keyed State will track changes based on mapping of objects of it content array to particular keys using a given key function instead of using indexes. While doing so, it also produces detailed ListChange objects outlining exactly how the array has changed in terms of additions, deletions and items being moved from a particular index to another.

For doing so, KeyedState conducts $\Omicron(n)$ operations, also maintaining a key map of $\Omicron(n)$ size holding quick-access references by keys to elements producing those keys for the previous value. Here, $n$ denotes not the number of leafs of the whole state-tree but the number of elements of the array assigned to a particular KeyedState.

For each change to the array, all elements are mapped once to their corresponding keys using the provided key function. The key function is supposed to be extremely light in nature, fetching a particular parameter of each element or doing a simple and fast computation:

1link// a key function should be something in lines of these:

2linkp => p.id;

3linkn => n % 17;

If the key function does not have complexity of $\Omicron(1)$, say $\Omicron(\lambda)$ for some non-constant $\lambda$, then upon each change the KeyedState would be conducting $\Omicron(\lambda n)$ operations.

When indexed items in the array are moved around, the KeyedState also conducts partial retracing to generate a change trace invariant to its keys. This does not involve invoking the key function, but worst-case can add $\Omicron(n\log(n))$ operations to change propagation process.

This worst case only occurs when all of the items of the array are shifted and their corresponding values are also mutated all the way to the leafs. In a typical case when the items of the array are moved without being modified themselves, then this lowers to $\Omicron(n)$ operations.