What
Currently, Transition polls component dependencies' active() state whenever it is informed that a node has completed in order to determine if a dependent node can be processed.
This can lead to an issue where, if two nodes with the same parent complete activation or deactivation at the same time, both onNodeFinished calls see that all dependencies are ready. Without the workaround, the same node would be queued twice, which is invalid. A set of nodes added to the queue for the current transition phase (state_.enqueued_set) is maintained to prevent this.
The readiness checks in onNodeFinished are also of quadratic complexity on the number of dependencies which might be possible to improve.
Proposed change
An alternative design would not rely on the components' state to determine the next nodes in the transition. For example, the transition could count how many nodes each node needs to be ready before it can be processed. On each onNodeFinished call, all included dependents counters' would be decremented by 1 and enqueued if the counter reached 0.
While a small amount of extra data is needed to maintain these counters, there would likely be an efficiency gain from this design. At the moment, for each dependent (N), each dependency (N) is checked, giving O(N²) complexity. With the proposed design, each dependency (N) is checked, decremented, and enqueued if ready, giving O(N).
One complexity to this new approach is handling the deactivation of the former run target. The current design iterates through each node in the graph to deactivate nodes that should not be active in the new run target. As well as encountering the issue above, this could also be inefficient for large graphs. An alternative approach would be to store the index of the previously requested run target and only enqueue nodes that are descendants of that node. In code, this is actually quite a small change. For instance, setupDeactivation would traverse the graph instead of iterating and then enqueue nodes that aren't included in the subgraph (already in the code) and have no dependents.
The core idea is that the transition should have no knowledge of live component state and that enqueuing an already active node for activation is not an error (and the same for deactivation). Enqueuing a node twice during a transition is an error because the node may be in an intermediate state between inactivity and activation. From the perspective of the transition resolver, transitions are atomic transactions. It is up to the graph to resolve errors during transition by skipping enqueued jobs and ceasing to request new ones.
Acceptance Criteria (DoD)
transition.hpp makes no use of IComponent::active()state_.enqueued_set is removed- Transition unit tests updated
How
No response
What
Currently,
Transitionpolls component dependencies'active()state whenever it is informed that a node has completed in order to determine if a dependent node can be processed.This can lead to an issue where, if two nodes with the same parent complete activation or deactivation at the same time, both
onNodeFinishedcalls see that all dependencies are ready. Without the workaround, the same node would be queued twice, which is invalid. A set of nodes added to the queue for the current transition phase (state_.enqueued_set) is maintained to prevent this.The readiness checks in
onNodeFinishedare also of quadratic complexity on the number of dependencies which might be possible to improve.Proposed change
An alternative design would not rely on the components' state to determine the next nodes in the transition. For example, the transition could count how many nodes each node needs to be ready before it can be processed. On each
onNodeFinishedcall, all included dependents counters' would be decremented by 1 and enqueued if the counter reached 0.While a small amount of extra data is needed to maintain these counters, there would likely be an efficiency gain from this design. At the moment, for each dependent
(N), each dependency(N)is checked, givingO(N²)complexity. With the proposed design, each dependency(N)is checked, decremented, and enqueued if ready, givingO(N).One complexity to this new approach is handling the deactivation of the former run target. The current design iterates through each node in the graph to deactivate nodes that should not be active in the new run target. As well as encountering the issue above, this could also be inefficient for large graphs. An alternative approach would be to store the index of the previously requested run target and only enqueue nodes that are descendants of that node. In code, this is actually quite a small change. For instance,
setupDeactivationwould traverse the graph instead of iterating and then enqueue nodes that aren't included in the subgraph (already in the code) and have no dependents.The core idea is that the transition should have no knowledge of live component state and that enqueuing an already active node for activation is not an error (and the same for deactivation). Enqueuing a node twice during a transition is an error because the node may be in an intermediate state between inactivity and activation. From the perspective of the transition resolver, transitions are atomic transactions. It is up to the graph to resolve errors during transition by skipping enqueued jobs and ceasing to request new ones.
Acceptance Criteria (DoD)
transition.hppmakes no use ofIComponent::active()state_.enqueued_setis removedHow
No response