QNTM-5137: VM Method resolution performance improvement by aparajit-pratap · Pull Request #8755 · DynamoDS/Dynamo

aparajit-pratap · 2018-04-16T17:36:19Z

Purpose

The purpose of this PR is to add an optimization to the VM related to Method Resolution. Currently the VM determines the FunctionEndPoint for every specific call to the node as determined by the input parameters and replication strategy. This ensures that varied inputs can be dispatched correctly for each specific call. The SelectFinalFep() method (aka select final function endpoint) is relatively fast but is often called repeatedly with the same input parameters. This PR adds a mechanism to validate that the input parameters for the node are of the same type (ie homogeneous) which allows the SelectFinalFep() to be called once and the resulting FunctionEndPoint to be cached. In general most user call Dynamo nodes with homogeneous inputs which allows this optimization to improve throughput of the VM in most user scenarios. In terms of performance optimization, the new method AreParametersHomogeneous() is linearly bound to the number of inputs parameters vs calls to FunctionEndPoint which are linearly bound to the input parameter combinations determined by replication. Additionally, the type comparison methods utilized in AreParametersHomogeneous() are much faster (2 orders of magnitude) then the method resolution logic required in SelectFinalFep() and includes short-curcuit logic in-case input parameters are found to be dissimilar. In my profiling I found that this optimization can improve VM throughput by 12 to 20 percent for graph topologies that have lots of homogenous lists.

QNTM-5137

Declarations

Check these if you believe they are true

The code base 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.

Reviewers

@aparajit-pratap @pboyer

FYIs

@ramramps @mjkkirschner

aparajit-pratap · 2018-04-16T17:38:35Z

src/Engine/ProtoCore/Lang/CallSite.cs

                int cartIndex = ri.CartesianIndex;

+                //We determine if the input paramaters are homogenious to set the final function endpoint once
+                if (cartIndex == 0)


What is this check for?

@aparajit-pratap This is so you only check the homogeneity before you get into the recursive calls of ExecWithRISlowPath(). You could call these at different CartesianIndex values but you start to loose some of the performance improvement with multiple nested calls to AreParametersHomogeneous(). I will double check though... Right now I make the assumption that you only get the benefit of the predetermined finalFunctionEndPoint if you pass AreParametersHomogeneous() with all the parameters.

aparajit-pratap · 2018-04-16T17:40:07Z

src/Engine/ProtoCore/Lang/CallSite.cs

+                            }
+
+                            //Add single sample parameter to pass for evalutation in SelectFinalFep
+                            finalFormalParameters.Add(flatParameters[0]);


should this not be finalFormalParameters.Add(flatParameters[j]);

At this point we don't care about which item we select. The loop before has determined that all the flatParameters are the same so there I select the first item as a sample type

aparajit-pratap · 2018-04-16T17:42:04Z

@saintentropy this looks good. I have a few comments? Have you tried running the tests after your change?

mjkkirschner · 2018-04-16T17:44:34Z

src/Engine/ProtoCore/Lang/CallSite.cs

                        throw new ReplicationCaseNotCurrentlySupported(Resources.AlgorithmNotSupported);
                }

+                //We determine if the input paramaters are homogenious to set the final function endpoint once


spelling(homogeneous)

aparajit-pratap · 2018-04-16T18:00:44Z

src/Engine/ProtoCore/Lang/CallSite.cs

+                    if(homogenious)
+                        finalFuntionEndPoint = SelectFinalFep(c, functionEndPoint, finalFormalParameters, stackFrame, runtimeCore);
+                }
+


Can this block of changes go before:

if (replicationInstructions.Count == 0) { return ExecWithZeroRI(functionEndPoint, c, formalParameters, stackFrame, runtimeCore, previousTraceData, newTraceData, finalFuntionEndPoint); }

Let me look.

I think not for the same reason I mentioned before.... I was assuming that we wanted to validate the function input parameters are the same types (homogeneous) with the initial call of ExecWithRISlowPath() vs at every nested invocation. That leaves some situations where you could have a partial optimization uncovered (ie they drop back to determining the Function endpoint with every call of the replication) but this may be simpler.

pboyer · 2018-04-18T17:17:08Z

src/Engine/ProtoCore/Lang/CallSite.cs

+                if (formalParameter.IsArray)
+                {
+                    DSArray array = runtimeCore.Heap.ToHeapObject<DSArray>(formalParameter);
+                    StackValue[] flatParameters = array.Values.ToArray();


Why not use var? LHS types are simply unnecessary.

pboyer · 2018-04-18T17:17:50Z

src/Engine/ProtoCore/Lang/CallSite.cs

+                                }
+                            }
+
+                            //Add single sample parameter to pass for evalutation in SelectFinalFep


evalutation is spelled wrong twice in this file

mjkkirschner · 2018-05-25T16:58:36Z

Is there a task around validating this performance improvement and merging this at some point?

saintentropy · 2018-08-20T19:03:18Z

@mjkkirschner Any thoughts on what scenarios would be good to validate performance.

Dewb · 2018-08-21T21:05:08Z

I'm still getting up to speed on the VM but this change seems like it has bounded risk and large value, so I'm in favor of prioritizing whatever we need to do to increase our confidence and get it merged.

Things I would like to see:

A new unit test specifically for correct resolution behavior in a variety of homogenous and heterogenous replication scenarios
Performance test suite results before and after this change (I know the Revit test suite has Dynamo performance tests, I'm not clear on whether they're in the Dynamo CI pipeline yet.)

aparajit-pratap · 2018-08-27T18:29:41Z

@Dewb which Dynamo performance tests are you referring to in the Revit test suite?

mjkkirschner · 2018-09-01T02:58:34Z

src/Engine/ProtoCore/Lang/CallSite.cs

+        /// Determine if the formalParameters are homogeneous and initialize a flat list of final formalParameters
+        /// </summary>
+        /// <returns>true if the formalParameters are homogeneous</returns>
+        private static bool AreParametersHomogeneous(List<StackValue> formalParameters, RuntimeCore runtimeCore, List<StackValue> finalFormalParameters)


feels weird to me that this has side effects on a list you need to initialize and pass in to this method... what about just returning a tuple?

mjkkirschner · 2018-09-01T02:59:38Z

src/Engine/ProtoCore/Namespace/SymbolTable.cs

        public Symbol[] TryGetSymbols(string name, Func<Symbol, bool> predicate)
        {
-            string symbolName = name.Split('.').Last();
+            var index = name.LastIndexOf('.');


whats with this change - I might have missed it in the PR description?

Ah sorry... just faster implementation. Split finds all the dots and LastIndexOf moves from the back

mjkkirschner · 2018-09-01T03:01:32Z

src/Engine/ProtoCore/Lang/CallSite.cs

+                if (cartIndex == 0)
+                {
+                    List<StackValue> finalFormalParameters = new List<StackValue>();
+                    var homogeneous = AreParametersHomogeneous(formalParameters, runtimeCore, finalFormalParameters);


this has a worst case cost of 2*n - and I don't know much about the VM - so a question - by the time we are making a function call here - have we already marshaled this data?

aparajit-pratap · 2018-09-13T19:00:01Z

src/DynamoUtilities/PathHelper.cs

            }
            catch(Exception e)
            {
-                Console.WriteLine(e.ToString());


Why is this no longer required?

I guess I should say it is very very annoying now that it pushes the error to the console every single time you open a DYN file (json)

Oh, good point!

@QilongTang are you okay with this being removed - was there a reason we wanted this?

@mjkkirschner It was for diagnosing old corrupted XML, I can see it less useful now. Fine with this change

👍 Thanks

aparajit-pratap · 2018-09-13T19:01:24Z

src/Engine/ProtoCore/Lang/CallSite.cs

            SingleRunTraceData previousTraceData,
-            SingleRunTraceData newTraceData)
+            SingleRunTraceData newTraceData,
+            FunctionEndPoint finalFuntionEndPoint = null)


Typo: should be finalFunctionEndpoint

aparajit-pratap · 2018-09-13T19:16:45Z

test/DynamoCoreTests/HomgeneousListTests.cs

+            return ret;
+        }
+
+        private List<double> TrimRange(IEnumerable<double> values, double stdDev, int multiplyer = 1)


typo: multiplier :)

aparajit-pratap · 2018-09-13T19:25:32Z

@saintentropy just curious what the graphs look like in the tests? Could you share a screenshot?

saintentropy · 2018-09-13T20:55:43Z

@aparajit-pratap Hey this is the graph I am using for performance. This is the graph with homogeneous types (all int). I alter either the first insert or the last insert to a double for the heterogeneous test files

saintentropy · 2018-09-13T21:37:25Z

The perf validation test of homogenous vs heterogeneous is usually like this

Homogeneous average execution: 161.113782608696ms
Heterogeneous first item average execution: 200.779774468085ms
Heterogeneous last item average execution: 195.1759125ms

This is relative to my machine but in general I see homogeneous running in about 80% of the heterogenous times. With the check disabled (ie the previous code) I get ~ 192ms.

mjkkirschner · 2018-09-14T15:55:17Z

src/Engine/ProtoCore/Lang/CallSite.cs

@@ -1876,8 +1882,11 @@ private StackValue ExecWithZeroRI(List<FunctionEndPoint> functionEndPoint, Conte
        /// Determine if the formalParameters are homogeneous and initialize a flat list of final formalParameters
        /// </summary>
        /// <returns>true if the formalParameters are homogeneous</returns>


@saintentropy out dated comment now that you return tuples

mjkkirschner · 2018-09-14T15:55:54Z

src/Engine/ProtoCore/Lang/CallSite.cs

-            //@PERF: Todo add a fast path here for the case where we have a homogenious array so we can directly dispatch
-            FunctionEndPoint finalFep = SelectFinalFep(c, functionEndPoint, formalParameters, stackFrame, runtimeCore);
+            if(finalFep == null)
+                finalFep = SelectFinalFep(c, functionEndPoint, formalParameters, stackFrame, runtimeCore);


mind using braces?

mjkkirschner · 2018-09-14T15:57:13Z

test/DynamoCoreTests/HomgeneousListTests.cs

+namespace Dynamo.Tests
+{
+    [TestFixture]
+    class HomogeneousListTests : DynamoModelTestBase


since it was important to use this class can you note it?

mjkkirschner · 2018-09-14T15:57:45Z

test/DynamoCoreTests/HomgeneousListTests.cs

+
+        protected override void GetLibrariesToPreload(List<string> libraries)
+        {
+            libraries.Add("ProtoGeometry.dll");


here as well - if this difference in time required loading some number of libs, lets note them.

mjkkirschner · 2018-09-14T15:59:03Z

test/DynamoCoreTests/HomgeneousListTests.cs

+            return ret;
+        }
+
+        private List<double> TrimRange(IEnumerable<double> values, double stdDev, int multiplier = 1)


comment on what this does?

mjkkirschner · 2018-09-14T16:00:33Z

@saintentropy LGTM - just a few comment issues.

saintentropy · 2018-09-14T17:20:34Z

I will run the Jenkins self service a few more times and then merge

saintentropy · 2018-09-14T21:01:25Z

Ok tests running well on self service CI. Will merge now

saintentropy added 6 commits April 7, 2018 23:37

fix slow String.Split function in marshaler

4dfcfcd

Add check for homogenious input parameters to support direct dispatch

463de16

Update function name

6cd9951

Refactor and Rename homogenious check method

d4b2dfb

Missing else condition

e564f9b

Merge branch 'master' into VMPerfImprovement

0b7c9f5

aparajit-pratap added the DNM Do not merge. For PRs. label Apr 16, 2018

aparajit-pratap commented Apr 16, 2018

View reviewed changes

mjkkirschner reviewed Apr 16, 2018

View reviewed changes

aparajit-pratap commented Apr 16, 2018

View reviewed changes

saintentropy changed the title ~~[DNM] Vm perf improvement~~ [DNM] WIP VMperf improvement Apr 16, 2018

Fix spelling

a1d5b40

saintentropy changed the title ~~[DNM] WIP VMperf improvement~~ [DNM] WIP VM Method Resoultion performance improvement Apr 18, 2018

pboyer changed the title ~~[DNM] WIP VM Method Resoultion performance improvement~~ [DNM] WIP VM Method resolution performance improvement Apr 18, 2018

pboyer reviewed Apr 18, 2018

View reviewed changes

saintentropy added 3 commits April 18, 2018 13:45

spelling errors

de40a8b

update per PR comments re var uses

fe0ae09

Merge branch 'master' into VMPerfImprovement

81ce385

Merge branch 'master' into VMPerfImprovement

895129d

saintentropy changed the title ~~[DNM] WIP VM Method resolution performance improvement~~ [DNM] VM Method resolution performance improvement Aug 20, 2018

saintentropy removed the DNM Do not merge. For PRs. label Aug 21, 2018

saintentropy changed the title ~~[DNM] VM Method resolution performance improvement~~ QNTM-5137: VM Method resolution performance improvement Aug 21, 2018

Merge branch 'master' into VMPerfImprovement

f04d48e

mjkkirschner reviewed Sep 1, 2018

View reviewed changes

saintentropy added 6 commits September 13, 2018 10:35

Update method documentation

dbdfdc7

Modify homgeneous check to return tuple

9c7667c

Add performance validation tests

ea18915

modify test intialization

a38e276

Update comments and methdod descriptions

7745f33

2.1 no longer needs xml failures reported to console

65f7383

aparajit-pratap commented Sep 13, 2018

View reviewed changes

saintentropy added 2 commits September 13, 2018 16:12

Spelling fix

6c2f1fe

More Spelling

18ba4e2

mjkkirschner reviewed Sep 14, 2018

View reviewed changes

saintentropy added 3 commits September 14, 2018 12:27

PR Comments

5f4a7e9

Add comments to test and rename methods for clarity

e097e25

Merge branch 'master' into VMPerfImprovement

60ffd0d

saintentropy merged commit 57a33ae into DynamoDS:master Sep 14, 2018

saintentropy mentioned this pull request Apr 2, 2019

FFIFunctionEndPoint Execute() performance refactor #9619

Merged

5 tasks

Conversation

aparajit-pratap commented Apr 16, 2018 • edited by saintentropy Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Purpose

Declarations

Reviewers

FYIs

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

aparajit-pratap Apr 16, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

aparajit-pratap commented Apr 16, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

saintentropy Apr 18, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mjkkirschner commented May 25, 2018

Uh oh!

saintentropy commented Aug 20, 2018

Uh oh!

Dewb commented Aug 21, 2018

Uh oh!

aparajit-pratap commented Aug 27, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

aparajit-pratap Sep 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

aparajit-pratap commented Sep 13, 2018

Uh oh!

saintentropy commented Sep 13, 2018

Uh oh!

saintentropy commented Sep 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

aparajit-pratap commented Apr 16, 2018 •

edited by saintentropy

Loading

aparajit-pratap Apr 16, 2018 •

edited

Loading

saintentropy Apr 18, 2018 •

edited

Loading

aparajit-pratap Sep 13, 2018 •

edited

Loading

saintentropy commented Sep 13, 2018 •

edited

Loading