optimize GetCommonSubClassForArray (#13079)

aparajit-pratap · web-flow · commit 050a4baf3cae · 2022-07-01T15:59:47.000-04:00
diff --git a/src/Engine/ProtoCore/Lang/FunctionEndPoint.cs b/src/Engine/ProtoCore/Lang/FunctionEndPoint.cs
@@ -63,7 +63,7 @@ public bool DoesTypeDeepMatch(List<StackValue> formalParameters, RuntimeCore run
                     }
                     else if (arrayTypes.Count > 1)
                     {
-                        ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArray(formalParameters[i], runtimeCore);
+                        ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArrayInternal(arrayTypes, runtimeCore);
 
                         if (commonBaseType == null)
                             throw new ProtoCore.Exceptions.ReplicationCaseNotCurrentlySupported(
diff --git a/src/Engine/ProtoCore/Lang/FunctionGroup.cs b/src/Engine/ProtoCore/Lang/FunctionGroup.cs
@@ -262,7 +262,7 @@ public static bool CheckInvalidArrayCoersion(FunctionEndPoint fep, List<StackVal
                 }
                 else if (arrayTypes.Count > 1)
                 {
-                    ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArray(reducedSVs[i], runtimeCore);
+                    ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArrayInternal(arrayTypes, runtimeCore);
 
                     if (commonBaseType == null)
                         throw new ProtoCore.Exceptions.ReplicationCaseNotCurrentlySupported(
diff --git a/src/Engine/ProtoCore/Utils/ArrayUtils.cs b/src/Engine/ProtoCore/Utils/ArrayUtils.cs
@@ -11,18 +11,8 @@ public static class ArrayUtils
     {
         private static int RECURSION_LIMIT = 1024;
 
-        /// <summary>
-        /// If an empty array is passed, the result will be null
-        /// if there are instances, but they share no common supertype the result will be var
-        /// </summary>
-        public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, RuntimeCore runtimeCore)
+        internal static ClassNode GetGreatestCommonSubclassForArrayInternal(Dictionary<ClassNode, int> typeStats, RuntimeCore runtimeCore)
         {
-            if (!array.IsArray)
-                throw new ArgumentException("The stack value provided was not an array");
-
-            Dictionary<ClassNode, int> typeStats = GetTypeStatisticsForArray(array, runtimeCore);
-
-
             //@PERF: This could be improved with a 
             List<List<int>> chains = new List<List<int>>();
             HashSet<int> commonTypeIDs = new HashSet<int>();
@@ -42,16 +32,13 @@ public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, Runt
                 foreach (int nodeId in chain)
                     commonTypeIDs.Add(nodeId);
 
- 
-
             }
 
             //Remove nulls if they exist
             {
- 
-            if (commonTypeIDs.Contains(
-                (int)PrimitiveType.Null))
-                commonTypeIDs.Remove((int)PrimitiveType.Null);
+
+                if (commonTypeIDs.Contains((int)PrimitiveType.Null))
+                    commonTypeIDs.Remove((int)PrimitiveType.Null);
 
                 List<List<int>> nonNullChains = new List<List<int>>();
 
@@ -63,9 +50,8 @@ public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, Runt
                     if (chain.Count > 0)
                         nonNullChains.Add(chain);
                 }
-
                 chains = nonNullChains;
-                    
+
             }
 
 
@@ -75,8 +61,6 @@ public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, Runt
                 foreach (List<int> chain in chains)
                 {
                     commonTypeIDs.IntersectWith(chain);
-                    
-
                 }
             }
 
@@ -90,7 +74,7 @@ public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, Runt
 
             List<int> lookupChain = chains[0];
 
-            
+
             //Insertion sort the IDs, we may only have a partial ordering on them.
             List<int> orderedTypes = new List<int>();
 
@@ -117,6 +101,21 @@ public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, Runt
             return runtimeCore.DSExecutable.classTable.ClassNodes[orderedTypes.First()];
         }
 
+        /// <summary>
+        /// If an empty array is passed, the result will be null
+        /// if there are instances, but they share no common supertype the result will be var
+        /// </summary>
+        public static ClassNode GetGreatestCommonSubclassForArray(StackValue array, RuntimeCore runtimeCore)
+        {
+            if (!array.IsArray)
+                throw new ArgumentException("The stack value provided was not an array");
+
+            Dictionary<ClassNode, int> typeStats = GetTypeStatisticsForArray(array, runtimeCore);
+
+            return GetGreatestCommonSubclassForArrayInternal(typeStats, runtimeCore);
+            
+        }
+
         /// <summary>
         /// This method returns the distinct(by metadata type) reduced params for all the elements inside the
         /// paramStackValue, if it is an array. If it is not an array, it just returns the paramStackValue.
@@ -224,7 +223,7 @@ public static Dictionary<ClassNode, int> GetTypeStatisticsForLayer(StackValue ar
         /// </summary>
         /// <param name="array"></param>
         /// <param name="core"></param>
-        /// <returns></returns>
+        /// <returns>usage frequency by type</returns>
         public static Dictionary<ClassNode, int> GetTypeStatisticsForArray(StackValue array, RuntimeCore runtimeCore)
         {
             if (!array.IsArray)
@@ -260,7 +259,7 @@ public static Dictionary<ClassNode, int> GetTypeStatisticsForArray(StackValue ar
                     if (!usageFreq.ContainsKey(cn))
                         usageFreq.Add(cn, 0);
 
-                    usageFreq[cn] = usageFreq[cn] + 1;
+                    usageFreq[cn] += 1;
                 }
             }
 

Original file line number	Diff line number	Diff line change
`@@ -63,7 +63,7 @@ public bool DoesTypeDeepMatch(List<StackValue> formalParameters, RuntimeCore run`
`63`	`63`	`}`
`64`	`64`	`else if (arrayTypes.Count > 1)`
`65`	`65`	`{`
`66`		`- ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArray(formalParameters[i], runtimeCore);`
	`66`	`+ ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArrayInternal(arrayTypes, runtimeCore);`
`67`	`67`
`68`	`68`	`if (commonBaseType == null)`
`69`	`69`	`throw new ProtoCore.Exceptions.ReplicationCaseNotCurrentlySupported(`
Original file line number	Diff line number	Diff line change
`@@ -262,7 +262,7 @@ public static bool CheckInvalidArrayCoersion(FunctionEndPoint fep, List<StackVal`
`262`	`262`	`}`
`263`	`263`	`else if (arrayTypes.Count > 1)`
`264`	`264`	`{`
`265`		`- ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArray(reducedSVs[i], runtimeCore);`
	`265`	`+ ClassNode commonBaseType = ArrayUtils.GetGreatestCommonSubclassForArrayInternal(arrayTypes, runtimeCore);`
`266`	`266`
`267`	`267`	`if (commonBaseType == null)`
`268`	`268`	`throw new ProtoCore.Exceptions.ReplicationCaseNotCurrentlySupported(`