[Spike] perform static cyclic dependency detection before each graph run

[aparajit-pratap]

Purpose

This adds the capability to perform a static cyclic dependency detection at the Dynamo graph level before each graph run (delta execution). If a cycle is detected, other than reporting node warnings on the nodes that are participating in the cycle, it prevents the graph from executing in the first place and getting into a warning state thus saving on some execution cycles (pun unintended).

Pros

• Potential performance improvement as we save on unnecessary graph execution

Cons

• If there is a sub-graph (disconnected graph) that is not involved in a cycle, even then it will skip execution, which is a regression in current behavior. This can be improved by still running that portion of the graph selectively. I've added this point to the list of ToDo's.

Note: We cannot remove the existing cyclic dependency checks from codegen as they are still required to detect cycles in DS code in CBNs. In the absence of this check, CBN code cycles if present will not be reported to users. An example of such a code is the following where there is a clear cycle in the code. This cannot be detected by the graph level check implemented in this spike.

Profiling Results:

Note: The profiling assumes we can do away with the codegen check for cyclic dependency but as mentioned, we cannot do so yet.

Profiling was carried out on a D4R/GD graph for graph execution only. It uses the following packages.

Before: Notice that just the cyclic dependency check at codegen takes nearly 1800ms or about 11.3% of the total time. This is saved after this new approach.

After: Savings of about 1300 ms or about 8% improvement overall.

TODO:

• [x] Check if cyclic dep checks can be removed from codegen - as described above, this cannot be done yet as the graph level cyclic dep check is insufficient to detect cycles in CBN DS code.
• [x] Check if fixes made in PR #11896 are still necessary - these would still be necessary to clear those errors that are detected by the codegen check.
• [x] Profile existing compile-time cyclic dep checks (+ execution) in engine vs. checks in this PR
• [ ] Code/tech debt removal if the above are found to be true - DYN-3925
• [ ] Check if we can run only those portions of the graph that are unaffected by a cycle - selective execution in other words (DYN-3926)
• [x] Fix regressions/update tests - some tests need to be updated as this PR follows a different code path when it comes to dealing with cyclic dependencies; the biggest change being that the graph execution is skipped altogether.
• [ ] There is one unresolved regression: Dynamo.Tests.DelayedGraphExecutionTests.DelayedExecutionNodeToCodeTest. It is still a mystery as no circular dependency is found on running the test graph in Dynamo, however, there is one found when running the test. This needs to be investigated further.
• [ ] Investigate a way to perform the cyclic dependency check in codegen only for ASTs corresponding to CBNs in a graph thereby making it possible to still leverage the perf benefits and simplicity of the graph-based analysis in this PR for the rest of the dynamo graph - https://jira.autodesk.com/browse/DYN-3954

Declarations

Check these if you believe they are true

• [x] The codebase is in a better state after this PR
• [ ] Is documented according to the standards
• [ ] The level of testing this PR includes is appropriate
• [ ] User facing strings, if any, are extracted into *.resx files
• [ ] All tests pass using the self-service CI.
• [ ] Snapshot of UI changes, if any.
• [ ] Changes to the API follow Semantic Versioning and are documented in the API Changes document.
• [ ] This PR modifies some build requirements and the readme is updated

FYIs

@saintentropy

[pinzart90]

@aparajit-pratap can we run the codegen cycle detection only for cbns ? The static cycle dep could then still be a benefit (assuming it cannot parse ds code at that time)

[aparajit-pratap]

@aparajit-pratap can we run the codegen cycle detection only for cbns ? The static cycle dep could then still be a benefit (assuming it cannot parse ds code at that time)

@pinzart90 codegen is performed on the entire AST that is compiled for the entire graph. At the moment I don't think there is a way to detect which AST's correspond to CBNs vs. those that don't although that might be something that is possible to implement. I can make this a follow-up task if we wish to proceed with this spike at some stage. Thanks for the suggestion.