Improving LRUD performance v2

adrian-wozniak commented 3 years ago

This PR improves LRUD performance and stability. It's a continuation of https://github.com/bbc/lrud/pull/92.

Description

Application where I'm using LRUD has a quite complex LRUD navigation tree. All in all, LRUD performs well, but on low-spec devices its computations are still noticeable.

It's not only about CPU usage but memory consumption. With every key press, memory pick might be observed. Such memory may be easily collected but that's the point. On low-spec devices, where app has limited memory resources, it matters. GC is triggered more often then and that cause performance drop.

The main goal of all changes here is to create node context. While processing a node we have to know what are its parent, active child, child at given position and overrides. With them we can easily decide which way to go for finding next node to focus. The idea is to have references to those objects at hand so there’s no need to search for them again and again having only its ids. From memory perspective it’s not a problem as it’s only reference to the object.

1. Checking if node is a focusable candidate (`isNodeFocusableCandidate`)

To check if node contains focusable children its subtree was flattened and then searched for focusable nodes. Flattening was making copies of a nodes, which caused not needed memory consumption. This method recursively traverse whole node subtree. To speed up things, flattenNode was removed and if there was a need to traverse node subtree, the pre-order deep first search tree traversal algorithm is used instead. Such algorithm processing is interrupted as fast as possible, when queried condition is met. isNodeFocusableCandidate method is called quite often while searching for next node to focus, so flattenNode method was creating a lot of not needed objects. Methods that use pre-order DFS: doesNodeHaveFocusableChildren, unregisterNode, registerTree.

2. Accessing the nodes (`getNode`)

This method is called many times without a reason. LRUD operates on nodes, but when it comes to calling some other method, it has to pass node id. After that getNode needs to be called again, and so on and so forth. With big trees, accessing nodes object properties became noticeable. To deal with that Node object now contains reference to its parent and activeChild instead of their ids. Moreover, globally stored currentFocusNodeId and rootNodeId were replaced with references to nodes: currentFocusNode and rootNode. Additionally, methods moveNode, unregisterNode, registerOverride, unregisterOverride, setActiveChild, setActiveChildRecursive, unsetActiveChild, assignFocus, isSameOrParentForChild, setNodeFocusable can detect if Node object was passed or node id. Thanks to that getNode method is called only when really needed.

3. Iterating children, finding child with index

Node's children are stored as an object. For most cases LRUD is not interested in child id but in its index, because index matters when it comes to finding next/prev focusable candidate. PR https://github.com/bbc/lrud/pull/85 introduced coherent way of maintaining the index value. Thanks to that, children may be stored as an array instead of an object. With that, finding a node with given index is just getting the needed array element. There's no need to iterate over children properties to find a node that have index value equal to searched one.

4. Finding an override

Similar case as above, but here iteration goes through all overrides whenever LRUD tries to climb up. To speed up things, overrides are stored on node level. Every node keeps its overrides. Here, using map of type { [direction in Direction]?: Node } is more efficient than having an array. We are always interested in one particular override as we don't have to iterate over it. This has one side effect. Such override may point to a node that is unregistered (does not exist). To avoid that and do appropriate overrides clean up while unregistering node, every node has an array overrideSources. Such array keeps overrides that points to that object. Thanks to that, while unregistering a node, all obsolete overrides may be removed without additional overhead.

Because override id is not needed anymore, signatures of registerOverride and unregisterOverride have changed. RegisterOverrideOptions can be passed to the registerOverride method to configure overwriting existing overrides.

5. Other minor changes connected to all above

Introduced NodeConfig type which allows registering nodes and trees. This is mainly to allow setting id of a parent node (as it is right now) and excluding properties that Node object contains for internal LRUD calculation.
All recursive methods execution were replaced with while loop: climbUp, digDown, setActiveChildRecursive. There’s no need to put the same method on the stack.
Introduced prepareNode method to simplify Node object creation from given NodeConfig object.
Type NodeTree was renamed to NodesBag as it describes to type nature more accurately.
Navigation tree creation in tests was compacted a bit for better readability.

Motivation and Context

The main motivation was to make applications using LRUD working smoothly on low-spec devices. On modern laptops, LRUD computation cost is almost not noticeable. Situation is changing dramatically when app is lunched on low-spec set-top boxes. Users are experiencing app freezes because of underlying JavaScript computations and memory GC executions.

How Has This Been Tested?

Tested by unit tests and manually in an app using LRUD library where such issue was found.

Screenshots (if appropriate):

No screenshots.

Types of changes

[ ] Bug fix (non-breaking change which fixes an issue)
[ ] New feature (non-breaking change which adds functionality)
[x] Breaking change (fix or feature that would cause existing functionality to change)

Checklist:

[x] My code follows the code style of this project.
[x] My change requires a change to the documentation.
[x] I have updated the documentation accordingly.
[x] I have read the CONTRIBUTING document.
[x] I have added tests to cover my changes.
[x] All new and existing tests passed.

adrian-wozniak commented 3 years ago

Hi @jordanholt, I have another set of performance improvements. Could you take a look on that?

jordanholt commented 3 years ago

Sure! Thanks @adrian-wozniak, will have a look at this today.

jordanholt commented 3 years ago

What're your thoughts on extracting the pre-order DFS algorithm that's used several times in src/index.ts into a higher order function in utils.ts? The call site could then just look like:

const initialStack = [ node ]

depthFirstSearch((stack) => {
  delete this.nodes[traversedNode.id]

  // Unregistering overrides
  this.unregisterOverride(traversedNode)

  // ...

  // push something else onto the stack
  stack.push(traversedNode.children[0])
}, initialStack)

Think the arrow function should have this and other variables that the callers are operating on in lexical scope.

Might seem trivial but it keeps the callers focused on the unique logic they're doing.

jordanholt commented 3 years ago

For the object creation code: https://github.com/bbc/lrud/blob/9199b63e1cbb9896e801b1ccd3b925f53af9b413/src/utils.ts#L257-L316

I understand the goal here.

Would it not be more memory efficient to initialise all objects to the same shape? i.e.

const node: Node = {
    id: nodeId,
    parent: undefined,
    index: undefined,
    children: undefined,
    activeChild: undefined,
    orientation: nodeConfig.orientation,
    indexRange: nodeConfig.indexRange,
    // ... etc
}

that way they all share a common backing HiddenClass, but with a lot of fields potentially being undefined. Or are the transitions lightweight enough that they are preferred to storing a single object shape with lots of undefined fields?

jordanholt commented 3 years ago

Oh, and p.s. massive kudos for your continued contributions to LRUD 🎉

adrian-wozniak commented 3 years ago

What're your thoughts on extracting the pre-order DFS algorithm that's used several times in src/index.ts into a higher order function in utils.ts? The call site could then just look like:
const initialStack = [ node ]

depthFirstSearch((stack) => {
  delete this.nodes[traversedNode.id]

  // Unregistering overrides
  this.unregisterOverride(traversedNode)

  // ...

  // push something else onto the stack
  stack.push(traversedNode.children[0])
}, initialStack)
Think the arrow function should have this and other variables that the callers are operating on in lexical scope.

Might seem trivial but it keeps the callers focused on the unique logic they're doing.

Yes, that's a good idea. Initially, when I started replacing existing behavior with DFS, it wasn't obvious that its pre-order version will fit in every cases we need. To make this method correctly defined in terms of types, I had to introduce new type Tree<Node>.

adrian-wozniak commented 3 years ago

For the object creation code:

https://github.com/bbc/lrud/blob/9199b63e1cbb9896e801b1ccd3b925f53af9b413/src/utils.ts#L257-L316

I understand the goal here.

Would it not be more memory efficient to initialise all objects to the same shape? i.e.
const node: Node = {
    id: nodeId,
    parent: undefined,
    index: undefined,
    children: undefined,
    activeChild: undefined,
    orientation: nodeConfig.orientation,
    indexRange: nodeConfig.indexRange,
    // ... etc
}
that way they all share a common backing HiddenClass, but with a lot of fields potentially being undefined. Or are the transitions lightweight enough that they are preferred to storing a single object shape with lots of undefined fields?

That's exactly what I wanted to do, but I thought that having objects with a lot of undefined properties may frustrate "the eye" :). Because of those "human feeling reasons", I tried to make some compromise and pick only those properties that are heavily used. I'm glad you pointed that out and I'm more than happy to do it. :)

adrian-wozniak commented 3 years ago

I added additional test for setNodeFocusable to keep branch coverage.

jordanholt commented 3 years ago

Thanks, looks good! I'll version this as v8.0.0

adrian-wozniak commented 3 years ago

Perfect! Thank you @jordanholt!

bbc / lrud