Implement more optimal versions of IterateHierarchy and iterateChildren based on nodes graph
#600
Comments
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 4, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 4, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
14 tasks
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 7, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 7, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 7, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
|
Looks really good on live cluster. ~300ms instead of ~4m to get process managed resources for the same application! |
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 16, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 16, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
andrii-korotkov-verkada
added a commit
to andrii-korotkov-verkada/gitops-engine
that referenced
this issue
Jul 16, 2024
…j#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]>
crenshaw-dev
added a commit
that referenced
this issue
Jul 18, 2024
) * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [#600] Closes #600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * improvements to graph building Signed-off-by: Michael Crenshaw <[email protected]> * use old name Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [#600] Closes #600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * finish merge Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [#600] Closes #600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * discard unneeded copies of child resources as we go Signed-off-by: Michael Crenshaw <[email protected]> * remove unnecessary comment Signed-off-by: Michael Crenshaw <[email protected]> * make childrenByUID sparse Signed-off-by: Michael Crenshaw <[email protected]> * eliminate duplicate map Signed-off-by: Michael Crenshaw <[email protected]> * fix comment Signed-off-by: Michael Crenshaw <[email protected]> * add useful comment back Signed-off-by: Michael Crenshaw <[email protected]> * use nsNodes instead of dupe map Signed-off-by: Michael Crenshaw <[email protected]> * remove unused struct Signed-off-by: Michael Crenshaw <[email protected]> * skip invalid APIVersion Signed-off-by: Michael Crenshaw <[email protected]> --------- Signed-off-by: Andrii Korotkov <[email protected]> Signed-off-by: Michael Crenshaw <[email protected]> Co-authored-by: Michael Crenshaw <[email protected]>
mpelekh
pushed a commit
to mpelekh/gitops-engine
that referenced
this issue
Jul 26, 2024
…#600] (argoproj#601) * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * improvements to graph building Signed-off-by: Michael Crenshaw <[email protected]> * use old name Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * finish merge Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * discard unneeded copies of child resources as we go Signed-off-by: Michael Crenshaw <[email protected]> * remove unnecessary comment Signed-off-by: Michael Crenshaw <[email protected]> * make childrenByUID sparse Signed-off-by: Michael Crenshaw <[email protected]> * eliminate duplicate map Signed-off-by: Michael Crenshaw <[email protected]> * fix comment Signed-off-by: Michael Crenshaw <[email protected]> * add useful comment back Signed-off-by: Michael Crenshaw <[email protected]> * use nsNodes instead of dupe map Signed-off-by: Michael Crenshaw <[email protected]> * remove unused struct Signed-off-by: Michael Crenshaw <[email protected]> * skip invalid APIVersion Signed-off-by: Michael Crenshaw <[email protected]> --------- Signed-off-by: Andrii Korotkov <[email protected]> Signed-off-by: Michael Crenshaw <[email protected]> Co-authored-by: Michael Crenshaw <[email protected]>
mpelekh
pushed a commit
to mpelekh/gitops-engine
that referenced
this issue
Aug 1, 2024
…#600] (argoproj#601) * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * improvements to graph building Signed-off-by: Michael Crenshaw <[email protected]> * use old name Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * finish merge Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * discard unneeded copies of child resources as we go Signed-off-by: Michael Crenshaw <[email protected]> * remove unnecessary comment Signed-off-by: Michael Crenshaw <[email protected]> * make childrenByUID sparse Signed-off-by: Michael Crenshaw <[email protected]> * eliminate duplicate map Signed-off-by: Michael Crenshaw <[email protected]> * fix comment Signed-off-by: Michael Crenshaw <[email protected]> * add useful comment back Signed-off-by: Michael Crenshaw <[email protected]> * use nsNodes instead of dupe map Signed-off-by: Michael Crenshaw <[email protected]> * remove unused struct Signed-off-by: Michael Crenshaw <[email protected]> * skip invalid APIVersion Signed-off-by: Michael Crenshaw <[email protected]> --------- Signed-off-by: Andrii Korotkov <[email protected]> Signed-off-by: Michael Crenshaw <[email protected]> Co-authored-by: Michael Crenshaw <[email protected]>
mpelekh
pushed a commit
to mpelekh/gitops-engine
that referenced
this issue
Aug 27, 2024
…#600] (argoproj#601) * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * improvements to graph building Signed-off-by: Michael Crenshaw <[email protected]> * use old name Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * finish merge Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * discard unneeded copies of child resources as we go Signed-off-by: Michael Crenshaw <[email protected]> * remove unnecessary comment Signed-off-by: Michael Crenshaw <[email protected]> * make childrenByUID sparse Signed-off-by: Michael Crenshaw <[email protected]> * eliminate duplicate map Signed-off-by: Michael Crenshaw <[email protected]> * fix comment Signed-off-by: Michael Crenshaw <[email protected]> * add useful comment back Signed-off-by: Michael Crenshaw <[email protected]> * use nsNodes instead of dupe map Signed-off-by: Michael Crenshaw <[email protected]> * remove unused struct Signed-off-by: Michael Crenshaw <[email protected]> * skip invalid APIVersion Signed-off-by: Michael Crenshaw <[email protected]> --------- Signed-off-by: Andrii Korotkov <[email protected]> Signed-off-by: Michael Crenshaw <[email protected]> Co-authored-by: Michael Crenshaw <[email protected]>
mpelekh
pushed a commit
to mpelekh/gitops-engine
that referenced
this issue
Sep 10, 2024
…#600] (argoproj#601) * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * improvements to graph building Signed-off-by: Michael Crenshaw <[email protected]> * use old name Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * finish merge Signed-off-by: Michael Crenshaw <[email protected]> * chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [argoproj#600] Closes argoproj#600 The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues. Signed-off-by: Andrii Korotkov <[email protected]> * discard unneeded copies of child resources as we go Signed-off-by: Michael Crenshaw <[email protected]> * remove unnecessary comment Signed-off-by: Michael Crenshaw <[email protected]> * make childrenByUID sparse Signed-off-by: Michael Crenshaw <[email protected]> * eliminate duplicate map Signed-off-by: Michael Crenshaw <[email protected]> * fix comment Signed-off-by: Michael Crenshaw <[email protected]> * add useful comment back Signed-off-by: Michael Crenshaw <[email protected]> * use nsNodes instead of dupe map Signed-off-by: Michael Crenshaw <[email protected]> * remove unused struct Signed-off-by: Michael Crenshaw <[email protected]> * skip invalid APIVersion Signed-off-by: Michael Crenshaw <[email protected]> --------- Signed-off-by: Andrii Korotkov <[email protected]> Signed-off-by: Michael Crenshaw <[email protected]> Co-authored-by: Michael Crenshaw <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
These should have a linear time complexity instead of up to quadratic. See argoproj/argo-cd#18929 for more details.
The text was updated successfully, but these errors were encountered: