Changeset 6849 for trunk/sources

Timestamp:

09/29/11 13:27:46 (13 years ago)

Author:

gkronber

Message:

#1480 experimental change to potentially improve performance of interpreters.

Location:

trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• SymbolicDataAnalysisExpressionTreeILEmittingInterpreter.cs (modified) (11 diffs)
• SymbolicDataAnalysisExpressionTreeInterpreter.cs (modified) (6 diffs)

trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeILEmittingInterpreter.cs

@@ -50 +50 @@
     #region private classes
     private class InterpreterState {
-      private double[] argumentStack;
-      private int argumentStackPointer;
       private Instruction[] code;
       private int pc;
+
       public int ProgramCounter {
         get { return pc; }
         set { pc = value; }
       }
-      internal InterpreterState(Instruction[] code, int argumentStackSize) {
+
+      private bool inLaggedContext;
+      public bool InLaggedContext {
+        get { return inLaggedContext; }
+        set { inLaggedContext = value; }
+      }
+      internal InterpreterState(Instruction[] code) {
+        this.inLaggedContext = false;
         this.code = code;
         this.pc = 0;
-        if (argumentStackSize > 0) {
-          this.argumentStack = new double[argumentStackSize];
-        }
-        this.argumentStackPointer = 0;
-      }
-
-      internal void Reset() {
-        this.pc = 0;
-        this.argumentStackPointer = 0;
       }
 
       internal Instruction NextInstruction() {
         return code[pc++];
-      }
-      private void Push(double val) {
-        argumentStack[argumentStackPointer++] = val;
-      }
-      private double Pop() {
-        return argumentStack[--argumentStackPointer];
-      }
-
-      internal void CreateStackFrame(double[] argValues) {
-        // push in reverse order to make indexing easier
-        for (int i = argValues.Length - 1; i >= 0; i--) {
-          argumentStack[argumentStackPointer++] = argValues[i];
-        }
-        Push(argValues.Length);
-      }
-
-      internal void RemoveStackFrame() {
-        int size = (int)Pop();
-        argumentStackPointer -= size;
-      }
-
-      internal double GetStackFrameValue(ushort index) {
-        // layout of stack:
-        // [0]   <- argumentStackPointer
-        // [StackFrameSize = N + 1]
-        // [Arg0] <- argumentStackPointer - 2 - 0
-        // [Arg1] <- argumentStackPointer - 2 - 1
-        // [...]
-        // [ArgN] <- argumentStackPointer - 2 - N
-        // <Begin of stack frame>
-        return argumentStack[argumentStackPointer - index - 2];
       }
     }
@@ -241 +207 @@
         }
       }
-      var state = new InterpreterState(code, necessaryArgStackSize);
+      var state = new InterpreterState(code);
 
       Type[] methodArgs = { typeof(int), typeof(IList<double>[]) };
@@ -465 +431 @@
             il.Emit(System.Reflection.Emit.OpCodes.Add);
             il.Emit(System.Reflection.Emit.OpCodes.Starg, 0);
+            var prevLaggedContext = state.InLaggedContext;
+            state.InLaggedContext = true;
             CompileInstructions(il, state, ds);
             il.Emit(System.Reflection.Emit.OpCodes.Ldarg_0); // row += lag
@@ -470 +438 @@
             il.Emit(System.Reflection.Emit.OpCodes.Sub);
             il.Emit(System.Reflection.Emit.OpCodes.Starg, 0);
+            state.InLaggedContext = prevLaggedContext;
             return;
           }
@@ -479 +448 @@
             il.Emit(System.Reflection.Emit.OpCodes.Add);
             il.Emit(System.Reflection.Emit.OpCodes.Starg, 0);
+            var prevLaggedContext = state.InLaggedContext;
+            state.InLaggedContext = true;
             CompileInstructions(il, state, ds);
             for (int l = laggedTreeNode.Lag; l < 0; l++) {
@@ -489 +460 @@
               il.Emit(System.Reflection.Emit.OpCodes.Add);
             }
+            state.InLaggedContext = prevLaggedContext;
             return;
           }
@@ -504 +476 @@
             il.Emit(System.Reflection.Emit.OpCodes.Starg, 0);
             state.ProgramCounter = savedPc;
+            var prevLaggedContext = state.InLaggedContext;
+            state.InLaggedContext = true;
             CompileInstructions(il, state, ds);
             il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 2.0); // f_0 + 2 * f_1
@@ -533 +507 @@
             il.Emit(System.Reflection.Emit.OpCodes.Add);
             il.Emit(System.Reflection.Emit.OpCodes.Starg, 0);
+            state.InLaggedContext = prevLaggedContext;
             return;
           }
@@ -542 +517 @@
           }
         case OpCodes.Variable: {
+            VariableTreeNode varNode = (VariableTreeNode)currentInstr.dynamicNode;
+            il.Emit(System.Reflection.Emit.OpCodes.Ldarg_1); // load columns array
+            il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, (int)currentInstr.iArg0);
+            // load correct column of the current variable
+            il.Emit(System.Reflection.Emit.OpCodes.Ldelem_Ref);
+            il.Emit(System.Reflection.Emit.OpCodes.Ldarg_0); // rowIndex
+            if (!state.InLaggedContext) {
+              il.Emit(System.Reflection.Emit.OpCodes.Call, listGetValue);
+              il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, varNode.Weight); // load weight
+              il.Emit(System.Reflection.Emit.OpCodes.Mul);
+            } else {
+              var nanResult = il.DefineLabel();
+              var normalResult = il.DefineLabel();
+              il.Emit(System.Reflection.Emit.OpCodes.Dup);
+              il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4_0);
+              il.Emit(System.Reflection.Emit.OpCodes.Blt, nanResult);
+              il.Emit(System.Reflection.Emit.OpCodes.Dup);
+              il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, ds.Rows);
+              il.Emit(System.Reflection.Emit.OpCodes.Bge, nanResult);
+              il.Emit(System.Reflection.Emit.OpCodes.Call, listGetValue);
+              il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, varNode.Weight); // load weight
+              il.Emit(System.Reflection.Emit.OpCodes.Mul);
+              il.Emit(System.Reflection.Emit.OpCodes.Br, normalResult);
+              il.MarkLabel(nanResult);
+              il.Emit(System.Reflection.Emit.OpCodes.Pop); // rowIndex
+              il.Emit(System.Reflection.Emit.OpCodes.Pop); // column reference
+              il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, double.NaN);
+              il.MarkLabel(normalResult);
+            }
+            return;
+          }
+        case OpCodes.LagVariable: {
             var nanResult = il.DefineLabel();
             var normalResult = il.DefineLabel();
-            VariableTreeNode varNode = (VariableTreeNode)currentInstr.dynamicNode;
+            LaggedVariableTreeNode varNode = (LaggedVariableTreeNode)currentInstr.dynamicNode;
             il.Emit(System.Reflection.Emit.OpCodes.Ldarg_1); // load columns array
             il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, (int)currentInstr.iArg0); // load correct column of the current variable
             il.Emit(System.Reflection.Emit.OpCodes.Ldelem_Ref);
-            il.Emit(System.Reflection.Emit.OpCodes.Ldarg_0); // sampleIndex
+            il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, varNode.Lag); // lag
+            il.Emit(System.Reflection.Emit.OpCodes.Ldarg_0); // rowIndex
+            il.Emit(System.Reflection.Emit.OpCodes.Add); // actualRowIndex = rowIndex + sampleOffset
             il.Emit(System.Reflection.Emit.OpCodes.Dup);
             il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4_0);
@@ -566 +575 @@
             return;
           }
-        case OpCodes.LagVariable: {
-            var nanResult = il.DefineLabel();
-            var normalResult = il.DefineLabel();
-            LaggedVariableTreeNode varNode = (LaggedVariableTreeNode)currentInstr.dynamicNode;
-            il.Emit(System.Reflection.Emit.OpCodes.Ldarg_1); // load columns array
-            il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, (int)currentInstr.iArg0); // load correct column of the current variable
-            il.Emit(System.Reflection.Emit.OpCodes.Ldelem_Ref);
-            il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, varNode.Lag); // lag
-            il.Emit(System.Reflection.Emit.OpCodes.Ldarg_0); // sampleIndex
-            il.Emit(System.Reflection.Emit.OpCodes.Add); // row = sampleIndex + sampleOffset
-            il.Emit(System.Reflection.Emit.OpCodes.Dup);
-            il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4_0);
-            il.Emit(System.Reflection.Emit.OpCodes.Blt, nanResult);
-            il.Emit(System.Reflection.Emit.OpCodes.Dup);
-            il.Emit(System.Reflection.Emit.OpCodes.Ldc_I4, ds.Rows);
-            il.Emit(System.Reflection.Emit.OpCodes.Bge, nanResult);
-            il.Emit(System.Reflection.Emit.OpCodes.Call, listGetValue);
-            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, varNode.Weight); // load weight
-            il.Emit(System.Reflection.Emit.OpCodes.Mul);
-            il.Emit(System.Reflection.Emit.OpCodes.Br, normalResult);
-            il.MarkLabel(nanResult);
-            il.Emit(System.Reflection.Emit.OpCodes.Pop); // sample index
-            il.Emit(System.Reflection.Emit.OpCodes.Pop); // column reference
-            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, double.NaN);
-            il.MarkLabel(normalResult);
-            return;
-          }
         case OpCodes.Constant: {
             ConstantTreeNode constNode = (ConstantTreeNode)currentInstr.dynamicNode;
@@ -614 +596 @@
         throw new NotSupportedException("Symbol: " + treeNode.Symbol);
     }
-
-    // skips a whole branch
-    private void SkipInstructions(InterpreterState state) {
-      int i = 1;
-      while (i > 0) {
-        i += state.NextInstruction().nArguments;
-        i--;
-      }
-    }
   }
 }

trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeInterpreter.cs

@@ -132 +132 @@
 
       public const byte VariableCondition = 27;
+
+      public const byte UncheckedVariable = 28;
+      public const byte UncheckedVariableCondition = 29;
     }
     #endregion
 
+    private Dictionary<Type, byte> symbolToUncheckedOpcode = new Dictionary<Type, byte>() {
+      { typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Variable), OpCodes.UncheckedVariable },
+      { typeof(VariableCondition),OpCodes.UncheckedVariableCondition}
+    };
     private Dictionary<Type, byte> symbolToOpcode = new Dictionary<Type, byte>() {
       { typeof(Addition), OpCodes.Add },
@@ -206 +213 @@
       for (int i = 0; i < code.Length; i++) {
         Instruction instr = code[i];
-        if (instr.opCode == OpCodes.Variable) {
+        if (instr.opCode == OpCodes.Variable || instr.opCode == OpCodes.UncheckedVariable) {
           var variableTreeNode = instr.dynamicNode as VariableTreeNode;
           instr.iArg0 = dataset.GetReadOnlyDoubleValues(variableTreeNode.VariableName);
@@ -214 +221 @@
           instr.iArg0 = dataset.GetReadOnlyDoubleValues(laggedVariableTreeNode.VariableName);
           code[i] = instr;
-        } else if (instr.opCode == OpCodes.VariableCondition) {
+        } else if (instr.opCode == OpCodes.VariableCondition || instr.opCode == OpCodes.UncheckedVariableCondition) {
           var variableConditionTreeNode = instr.dynamicNode as VariableConditionTreeNode;
           instr.iArg0 = dataset.GetReadOnlyDoubleValues(variableConditionTreeNode.VariableName);
@@ -410 +417 @@
             return ((IList<double>)currentInstr.iArg0)[row] * variableTreeNode.Weight;
           }
+        case OpCodes.UncheckedVariable: {
+            var variableTreeNode = (VariableTreeNode)currentInstr.dynamicNode;
+            return ((IList<double>)currentInstr.iArg0)[row] * variableTreeNode.Weight;
+          }
         case OpCodes.LagVariable: {
             var laggedVariableTreeNode = (LaggedVariableTreeNode)currentInstr.dynamicNode;
@@ -437 +448 @@
             return trueBranch * p + falseBranch * (1 - p);
           }
+        case OpCodes.UncheckedVariableCondition: {
+            var variableConditionTreeNode = (VariableConditionTreeNode)currentInstr.dynamicNode;
+            double variableValue = ((IList<double>)currentInstr.iArg0)[row];
+            double x = variableValue - variableConditionTreeNode.Threshold;
+            double p = 1 / (1 + Math.Exp(-variableConditionTreeNode.Slope * x));
+
+            double trueBranch = Evaluate(dataset, ref row, state);
+            double falseBranch = Evaluate(dataset, ref row, state);
+
+            return trueBranch * p + falseBranch * (1 - p);
+          }
         default: throw new NotSupportedException();
       }
@@ -442 +464 @@
 
     private byte MapSymbolToOpCode(ISymbolicExpressionTreeNode treeNode) {
-      if (symbolToOpcode.ContainsKey(treeNode.Symbol.GetType()))
-        return symbolToOpcode[treeNode.Symbol.GetType()];
-      else
-        throw new NotSupportedException("Symbol: " + treeNode.Symbol);
+      if ((treeNode.Symbol.GetType() == typeof(Variable) || treeNode.Symbol.GetType() == typeof(VariableCondition)) && !InLaggedContext(treeNode)) {
+        return symbolToUncheckedOpcode[treeNode.Symbol.GetType()];
+      } else {
+        if (symbolToOpcode.ContainsKey(treeNode.Symbol.GetType()))
+          return symbolToOpcode[treeNode.Symbol.GetType()];
+        else
+          throw new NotSupportedException("Symbol: " + treeNode.Symbol);
+      }
+    }
+
+    private bool InLaggedContext(ISymbolicExpressionTreeNode treeNode) {
+      if (treeNode.Parent == null) return false;
+      if (treeNode.Parent is ILaggedTreeNode) return true;
+      if (treeNode.Parent.Symbol is Derivative) return true;
+      return InLaggedContext(treeNode.Parent);
     }