Changeset 14746 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push

Timestamp:

03/11/17 20:07:13 (7 years ago)

Author:

pkimmesw

Message:

#2665 PooledPushProgram reduces memory usage and increases performance

Location:

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push

Files:

• Data/Pool/ManagedPool.cs (deleted)
• Data/Pool/ManagedPoolProvider.cs (added)
• Data/Pool/PoolContainer.cs (deleted)
• Expressions/CodeExpressions.cs (modified) (23 diffs)
• Expressions/ExecExpressions.cs (modified) (2 diffs)
• Expressions/Expression.cs (modified) (1 diff)
• Expressions/ExpressionTable.cs (modified) (3 diffs)
• Expressions/PushProgram.bk.cs (modified) (5 diffs)
• Expressions/PushProgram.cs (modified) (12 diffs)
• Expressions/RandExpressions.cs (modified) (1 diff)
• Expressions/StatefulExpression.cs (modified) (2 diffs)
• Generators/CodeGenerator.cs (modified) (2 diffs)
• Interpreter/IPushInterpreter.cs (modified) (2 diffs)
• Interpreter/PushInterpreter.cs (modified) (4 diffs)
• Problem/PushEncoding.cs (modified) (1 diff)
• Problem/PushProblem.cs (modified) (5 diffs)
• Simplifier/RandomSimplifier.cs (modified) (1 diff)

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/CodeExpressions.cs

@@ -108 +108 @@
       var second = interpreter.CodeStack.Top;
 
-      var isFirstList = first.CanExpand;
-      var isSecondList = second.CanExpand;
-
-      Expression[] result = null;
+      var isFirstList = first.IsProgram;
+      var isSecondList = second.IsProgram;
+
+      PushProgram result;
 
       if (isFirstList) {
-        var expand1 = first as PushProgram;
+        var program1 = first as PushProgram;
 
         if (isSecondList) {
-          var expand2 = second as PushProgram;
-          var size = expand2.State.Length + expand1.State.Length;
+          var program2 = second as PushProgram;
+          var size = program2.Expressions.Count + program1.Expressions.Count;
 
           // if size > maxPointsInProgram this expressions results in a NOOP
           if (size > interpreter.Configuration.MaxPointsInProgram) return false;
 
-          result = new Expression[size];
-
-          Array.Copy(expand2.State, result, expand2.State.Length);
-          Array.Copy(
-              expand1.State,
-              0,
-              result,
-              expand2.State.Length,
-              expand1.State.Length);
+          result = PushProgram.Merge(interpreter.PushProgramPool, program2, program1);
         } else {
-          var size = expand1.State.Length + 1;
+          var size = program1.Expressions.Count + 1;
 
           // if size > maxPointsInProgram this expressions results in a NOOP
           if (size > interpreter.Configuration.MaxPointsInProgram) return false;
 
-          result = new Expression[size];
-          result[0] = second;
-
-          Array.Copy(expand1.State, 0, result, 1, expand1.State.Length);
+          result = PushProgram.Merge(interpreter.PushProgramPool, second, program1);
         }
       } else if (isSecondList) {
-        var expand2 = second as PushProgram;
-
-        var size = expand2.State.Length + 1;
+        var program2 = second as PushProgram;
+        var size = program2.Expressions.Count + 1;
 
         // if size > maxPointsInProgram this expressions results in a NOOP
         if (size > interpreter.Configuration.MaxPointsInProgram) return false;
 
-        result = new Expression[size];
-        result[0] = first;
-
-        Array.Copy(expand2.State as Expression[], 0, result, 1, expand2.State.Length);
+        result = PushProgram.Merge(interpreter.PushProgramPool, first, program2);
       } else {
-        result = new[] { second, first };
+        result = PushProgram.Create(interpreter.PushProgramPool, second, first);
       }
 
-      var expression = new PushProgram(result);
-
-      interpreter.CodeStack.SetTop(expression);
+      interpreter.CodeStack.SetTop(result);
 
       return true;
@@ -177 +160 @@
 
       var expression = interpreter.CodeStack.Pop();
-      var isExpandExpression = expression.CanExpand;
+      var isExpandExpression = expression.IsProgram;
 
       interpreter.BooleanStack.Push(!isExpandExpression);
@@ -199 +182 @@
 
       if (expand.IsEmpty) return false;
-      var first = expand.State[expand.State.Length - 1];
+      var first = expand.Expressions[expand.Expressions.Count - 1];
 
       interpreter.CodeStack.SetTop(first);
@@ -217 +200 @@
       if (interpreter.CodeStack.Count == 0) return false;
 
-      PushProgram expandExpression;
+      PushProgram result;
       var top = interpreter.CodeStack.Top;
 
-      if (top.CanExpand) {
-        var expand = (PushProgram)top;
-
-        if (expand.IsEmpty) return false;
-        var length = expand.State.Length - 1;
-        var newExpressions = new Expression[length];
-
-        Array.Copy((Expression[])expand.State, 0, newExpressions, 0, length);
-
-        expandExpression = new PushProgram(newExpressions);
+      if (top.IsProgram) {
+        var program = (PushProgram)top;
+
+        if (program.IsEmpty) return false;
+
+        result = program.Copy(interpreter.PushProgramPool, 0, program.Expressions.Count - 1);
       } else {
-        expandExpression = PushProgram.Empty;
+        result = PushProgram.Empty;
       }
 
-      interpreter.CodeStack.SetTop(expandExpression);
+      interpreter.CodeStack.SetTop(result);
       return true;
     }
@@ -252 +231 @@
       PushProgram result;
 
-      if (interpreter.CodeStack.Top.CanExpand) {
+      if (interpreter.CodeStack.Top.IsProgram) {
         var first = (PushProgram)interpreter.CodeStack.Pop();
-        var size = first.State.Length + 1;
+        var size = first.Expressions.Count + 1;
 
         if (size > interpreter.Configuration.MaxPointsInProgram) return false;
@@ -260 +239 @@
         var expressions = new Expression[size];
 
-        expressions[first.State.Length] = interpreter.CodeStack.Top;
-        Array.Copy(first.State as Expression[], expressions, first.State.Length);
-
-        result = new PushProgram(expressions);
+        first.CopyExpressionsTo(expressions);
+        expressions[first.Expressions.Count] = interpreter.CodeStack.Top;
+
+        result = PushProgram.Create(interpreter.PushProgramPool, expressions);
       } else {
-        result = new PushProgram(interpreter.CodeStack.Pop(), interpreter.CodeStack.Top);
+        result = PushProgram.Create(interpreter.PushProgramPool, interpreter.CodeStack.Top);
       }
 
@@ -303 +282 @@
 
       var subContainer =
-          current.State.Where(e => e.CanExpand)
+          current.Expressions.Where(e => e.IsProgram)
               .Select(e => GetContainer(e as PushProgram, target))
               .Where(e => e != null);
@@ -309 +288 @@
       var execExpandExpressions = subContainer as IList<PushProgram> ?? subContainer.ToList();
       return execExpandExpressions.Any()
-          ? execExpandExpressions.OrderBy(c => c.State.Length).LastOrDefault()
-          : current.State.Contains(target)
+          ? execExpandExpressions.OrderBy(c => c.Expressions.Count).LastOrDefault()
+          : current.Expressions.Contains(target)
               ? current
               : null;
@@ -324 +303 @@
     public override bool Eval(IPushInterpreter interpreter) {
       if (interpreter.CodeStack.Count < 2 ||
-         !interpreter.CodeStack[interpreter.CodeStack.Count - 2].CanExpand)
+         !interpreter.CodeStack[interpreter.CodeStack.Count - 2].IsProgram)
         return false;
 
       var values = interpreter.CodeStack.Pop(2);
       var second = (PushProgram)values[0];
-      var contains = second.State.Contains(values[1]);
+      var contains = second.Expressions.Contains(values[1]);
 
       interpreter.BooleanStack.Push(contains);
@@ -413 +392 @@
 
     private void DetermineUniqueItems(Expression source, IDictionary<int, int> items) {
-      if (source.CanExpand) {
-        var expand = source as PushProgram;
-
-        foreach (var e in expand.State) {
-          var id = e.GetHashCode();
+      if (source.IsProgram) {
+        var program = source as PushProgram;
+        var expressions = program.Expressions;
+
+        for (var i = 0; i < expressions.Count; i++) {
+          var id = expressions[i].GetHashCode();
           if (!items.ContainsKey(id)) items.Add(id, 1);
           else items[id]++;
@@ -442 +422 @@
       if (interpreter.IntegerStack.Count == 0 ||
           interpreter.CodeStack.Count == 0 ||
-          !interpreter.CodeStack.Top.CanExpand)
+          !interpreter.CodeStack.Top.IsProgram)
         return false;
 
@@ -532 +512 @@
       if (interpreter.IntegerStack.Count == 0 ||
           interpreter.CodeStack.Count < 2 ||
-          !interpreter.CodeStack.Top.CanExpand)
+          !interpreter.CodeStack.Top.IsProgram)
         return false;
 
@@ -540 +520 @@
 
       Expression[] newExpressions;
-      if (target.State.Length > 0) {
-        index = target.State.Length - 1 - Math.Abs(index % target.State.Length);
+      if (!target.IsEmpty) {
+        index = target.Expressions.Count - 1 - Math.Abs(index % target.Expressions.Count);
 
         newExpressions = target.CopyExpressions();
-        newExpressions[index] = source.CanExpand
-            ? ((PushProgram)source).Copy()
+        newExpressions[index] = source.IsProgram
+            ? ((PushProgram)source).Copy(interpreter.PushProgramPool)
             : source;
       } else {
@@ -551 +531 @@
       }
 
-      var result = new PushProgram(newExpressions);
+      var result = PushProgram.Create(interpreter.PushProgramPool, newExpressions);
       interpreter.CodeStack.SetTop(result);
 
@@ -572 +552 @@
       var count = 1;
 
-      if (expression.CanExpand)
-        count = ((PushProgram)expression).State.Length;
+      if (expression.IsProgram)
+        count = ((PushProgram)expression).Expressions.Count;
 
       interpreter.IntegerStack.Push(count);
@@ -591 +571 @@
       var first = interpreter.CodeStack.Pop();
       var second = interpreter.CodeStack.Top;
-      var expandExpression = new PushProgram(second, first);
+      var expandExpression = PushProgram.Create(interpreter.PushProgramPool, second, first);
 
       interpreter.CodeStack.SetTop(expandExpression);
@@ -610 +590 @@
       var expressions = interpreter.CodeStack.Pop(2);
 
-      var contains = expressions[1].CanExpand
-          ? ((PushProgram)expressions[1]).State.Contains(expressions[0])
+      var contains = expressions[1].IsProgram
+          ? ((PushProgram)expressions[1]).Expressions.Contains(expressions[0])
           : expressions[1].Equals(expressions[0]);
 
@@ -635 +615 @@
       Expression nthExpression;
 
-      if (expression.CanExpand) {
+      if (expression.IsProgram) {
         var subExpression = (PushProgram)expression;
 
@@ -641 +621 @@
           nthExpression = PushProgram.Empty;
         } else {
-          var index = (int)(subExpression.State.Length - 1 -
-                             Math.Abs(n % subExpression.State.Length));
-
-          nthExpression = subExpression.State[index];
+          var index = (int)(subExpression.Expressions.Count - 1 - Math.Abs(n % subExpression.Expressions.Count));
+
+          nthExpression = subExpression.Expressions[index];
         }
       } else {
@@ -674 +653 @@
       Expression nthExpression;
 
-      if (expression.CanExpand) {
-        var subExpressions = ((PushProgram)expression).State;
-
-        if (subExpressions.Length < 2) {
+      if (expression.IsProgram) {
+        var subExpressions = ((PushProgram)expression).Expressions;
+
+        if (subExpressions.Count < 2) {
           nthExpression = PushProgram.Empty;
         } else {
-          var index = (int)(subExpressions.Length - 2 - Math.Abs(n % (subExpressions.Length - 1)));
+          var index = (int)(subExpressions.Count - 2 - Math.Abs(n % (subExpressions.Count - 1)));
 
           nthExpression = subExpressions[index];
@@ -723 +702 @@
 
       var position = -1;
-      if (first.CanExpand) {
-        var expand = (PushProgram)first;
-        position = expand.State.Length - 1
-                   - Array.FindIndex((Expression[])expand.State, e => e.Equals(second));
+      if (first.IsProgram) {
+        var program = (PushProgram)first;
+        position = program.Expressions.Count - 1 - program.IndexOf(second);
       } else if (first.Equals(second)) {
         position = 0;
@@ -747 +725 @@
 
       var expression = interpreter.CodeStack.Pop();
-      var points = expression.CanExpand
-          ? ((PushProgram)expression).State.Length
+      var points = expression.IsProgram
+          ? ((PushProgram)expression).Expressions.Count
           : 1;
 
@@ -773 +751 @@
       var second = expressions[0];
       var first = expressions[1] as PushProgram;
-      var newExpressions = new Expression[first.State.Length];
-
-      for (var i = 0; i < first.State.Length; i++)
-        newExpressions[i] = first.State[i].Equals(third)
+      var firstExpressions = first.Expressions;
+      var newExpressions = new Expression[firstExpressions.Count];
+
+      for (var i = 0; i < firstExpressions.Count; i++)
+        newExpressions[i] = firstExpressions[i].Equals(third)
             ? second
             /* no cloning needed here because first is removed and therefore newExpression is the only container of sub expressions */
-            : first.State[i];
-
-      var result = new PushProgram(newExpressions);
+            : firstExpressions[i];
+
+      var result = PushProgram.Create(interpreter.PushProgramPool, newExpressions);
 
       interpreter.CodeStack.SetTop(result);

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/ExecExpressions.cs

@@ -41 +41 @@
       var top = interpreter.ExecStack.Top;
       var execYExpression = ExpressionTable.GetStatelessExpression<ExecYExpression>();
-
-      var result = new PushProgram(top, execYExpression);
+      var result = PushProgram.Create(interpreter.PushProgramPool, top, execYExpression);
 
       interpreter.ExecStack.SetTop(result);
@@ -81 +80 @@
       var c = interpreter.ExecStack.Top;
 
-      var newTop = new PushProgram(c, b);
+      var newTop = PushProgram.Create(interpreter.PushProgramPool, c, b);
 
       interpreter.ExecStack.SetTop(newTop);

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/Expression.cs

@@ -7 +7 @@
   using Interpreter;
 
+  [Serializable]
   public abstract class Expression {
-    public bool CanExpand { get { return this.GetType() == typeof(PushProgram); } }
+    public bool IsProgram { get { return this.GetType() == typeof(PushProgram); } }
 
     public static readonly IReadOnlyCollection<Expression> EmptyContainer = new Expression[0];

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/ExpressionTable.cs

@@ -5 +5 @@
 
   using HeuristicLab.Problems.ProgramSynthesis.Push.Attributes;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Stack;
 
@@ -123 +124 @@
     }
 
-    public static PushProgram GetProgram(int[] index) {
+    public static PushProgram GetProgram(IManagedPool<PushProgram> pool, int[] index) {
       var expressions = new Expression[index.Length];
 
@@ -130 +131 @@
       }
 
-      return new PushProgram(expressions);
+      return PushProgram.Create(pool, expressions);
     }
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.bk.cs

@@ -88 +88 @@
 //    public IEnumerable<Expression> DepthFirst() {
 //      foreach (var expr in this.Expressions) {
-//        if (expr.CanExpand) {
+//        if (expr.IsProgram) {
 //          var expandExpr = (PushProgram)expr;
 
@@ -114 +114 @@
 
 //    private int CalcDepth() {
-//      //var subExpressions = Expressions.Where(e => e.CanExpand);
+//      //var subExpressions = Expressions.Where(e => e.IsProgram);
 //      //var depth = subExpressions.Any()
 //      //    ? subExpressions.Select(e => e as PushProgram).Max(e => e.State.Depth) + 1
@@ -124 +124 @@
 //      for (var i = 0; i < Expressions.Count; i++) {
 //        var expression = Expressions[i];
-//        if (!expression.CanExpand) continue;
+//        if (!expression.IsProgram) continue;
 //        var expandExpression = (PushProgram)expression;
 
@@ -151 +151 @@
 //        local_treeIndex[i] = next;
 
-//        if (subExpression.CanExpand) {
+//        if (subExpression.IsProgram) {
 //          next += ((PushProgram)subExpression).State.TotalCount;
 //        } else {
@@ -184 +184 @@
 
 //      for (var i = 0; i < current.State.Expressions.Count; i++) {
-//        if (current.State.Expressions[i].CanExpand)
+//        if (current.State.Expressions[i].IsProgram)
 //          continue;
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs

@@ -6 +6 @@
   using System.Diagnostics;
 
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
+
   using Interpreter;
 
-  public class PushProgram : StatefulExpression<Expression[]> {
+  [Serializable]
+  public sealed class PushProgram : Expression {
+    private static readonly Expression[] EmptyExpressions = new Expression[0];
     public static readonly PushProgram Empty = new PushProgram();
 
@@ -17 +21 @@
     private const string Delimiter = " ";
 
-    public readonly bool IsEmpty;
-
-    public PushProgram(params Expression[] state) : base(state) {
-      IsEmpty = state.Length == 0;
-    }
-
-    public PushProgram(IEnumerable<Expression> state) : this(state.ToArray()) {
-      // TODO: lazy evaluation of ToArray()
+    private Expression[] expressions;
+
+    public PushProgram() : this(EmptyExpressions) {
+    }
+
+    public PushProgram(Expression[] expressions) {
+      this.expressions = expressions;
+    }
+
+    public bool IsEmpty { get { return Count == 0; } }
+    public int Count { get { return expressions.Length; } }
+
+    public IReadOnlyList<Expression> Expressions { get { return this.expressions; } }
+
+    public static PushProgram Create(IManagedPool<PushProgram> pool, params Expression[] expressions) {
+      var program = pool.Get();
+
+      program.expressions = expressions;
+      program.Reset();
+
+      return program;
+    }
+
+    private void Reset() {
+      stringRepresentation = null;
+      depth = null;
+      treeIndex = null;
+      hashCode = null;
+    }
+
+    public static PushProgram Merge(IManagedPool<PushProgram> pool, PushProgram first, Expression second) {
+      var program = pool.Get();
+
+      program.Reset();
+      program.expressions = new Expression[first.Expressions.Count + 1];
+      first.CopyExpressionsTo(program.expressions);
+      program.expressions[0] = first;
+
+      return program;
+    }
+
+    public static PushProgram Merge(IManagedPool<PushProgram> pool, Expression first, PushProgram second) {
+      var program = pool.Get();
+
+      program.Reset();
+
+      program.expressions = new Expression[second.Expressions.Count + 1];
+      program.expressions[0] = first;
+      second.CopyExpressionsTo(program.expressions, 0, 1, second.Count);
+
+      return program;
+    }
+
+    public static PushProgram Merge(IManagedPool<PushProgram> pool, PushProgram first, PushProgram second) {
+      var program = pool.Get();
+
+      program.Reset();
+      program.expressions = new Expression[first.Count + second.Count];
+
+      first.CopyExpressionsTo(program.expressions);
+      second.CopyExpressionsTo(program.expressions, 0, first.Count, second.Count);
+
+      return program;
+    }
+
+    public int IndexOf(Expression expression) {
+      return Array.IndexOf(this.expressions, expression);
     }
 
@@ -32 +95 @@
       get
       {
-        if (string.IsNullOrEmpty(stringRepresentation))
-          stringRepresentation = BuildString();
+        if (stringRepresentation == null) stringRepresentation = BuildString();
         return stringRepresentation;
       }
     }
 
-    private int depth = -1;
+
+    private int? depth;
     public int Depth
     {
       get
       {
-        if (depth == -1) depth = CalcDepth();
-        return depth;
+        if (depth == null) depth = CalcDepth();
+        return depth.Value;
       }
     }
@@ -53 +116 @@
       get
       {
-        return treeIndex ?? (treeIndex = BuildTreeIndex());
-      }
-    }
-
-    private int hashCode;
-    private int HashCode
-    {
-      get
-      {
-        if (hashCode == default(int)) hashCode = HashExpressions();
-        return hashCode;
-      }
+        if (treeIndex == null) treeIndex = BuildTreeIndex();
+        return treeIndex;
+      }
+    }
+
+    private int? hashCode;
+    public override int GetHashCode() {
+      if (hashCode == null) hashCode = HashExpressions();
+      return hashCode.Value;
     }
 
     //public PushProgram Copy() {
     //  // as the empty list is a static stateless expression, no copy required
-    //  return ReferenceEquals(this, Empty) || this.State.IsEmpty
+    //  return ReferenceEquals(this, Empty) || this.expressions.IsEmpty
     //    ? Empty
-    //    : new PushProgram(this.State.Copy());
+    //    : new PushProgram(this.expressions.Copy());
     //}
 
     public override bool Eval(IPushInterpreter interpreter) {
-      interpreter.ExecStack.Push(this.State);
+      interpreter.ExecStack.Push(this.expressions);
       return true;
     }
 
-    public override int GetHashCode() {
-      return HashCode;
-    }
-
     public override string ToString() {
-      return this.StringRepresentation;
+      return StringRepresentation;
     }
 
@@ -103 +159 @@
 
     public IEnumerable<Expression> DepthFirst() {
-      foreach (var expr in this.State) {
-        if (expr.CanExpand) {
+      foreach (var expr in this.expressions) {
+        if (expr.IsProgram) {
           var expandExpr = (PushProgram)expr;
 
@@ -114 +170 @@
 
     public PushProgram Copy() {
-      return IsEmpty ? this : new PushProgram(State) {
+      if (IsEmpty) return this;
+
+      var program = new PushProgram(this.expressions) {
         stringRepresentation = this.stringRepresentation,
         hashCode = this.hashCode,
@@ -120 +178 @@
         treeIndex = this.treeIndex
       };
-    }
-
-    public Expression[] CopyExpressions()
-    {
-      if (IsEmpty) return Empty.State;
-
-      var copy = new Expression[State.Length];
-      State.CopyTo(copy, 0);
+
+      return program;
+    }
+
+    public PushProgram Copy(IManagedPool<PushProgram> pool) {
+      if (IsEmpty) return this;
+
+      var program = pool.Get();
+      program.expressions = this.expressions;
+      program.stringRepresentation = stringRepresentation;
+      program.hashCode = hashCode;
+      program.depth = depth;
+      program.treeIndex = treeIndex;
+
+      return program;
+    }
+
+    public PushProgram Copy(IManagedPool<PushProgram> pool, int startIndex, int length) {
+      if (IsEmpty) return this;
+
+      var program = pool.Get();
+      program.expressions = CopyExpressions(startIndex, length);
+
+      program.Reset();
+
+      return program;
+    }
+
+    public Expression[] CopyExpressions() {
+      return CopyExpressions(Count);
+    }
+
+    public Expression[] CopyExpressions(int length) {
+      if (IsEmpty) return EmptyExpressions;
+
+      var copy = new Expression[length];
+      this.expressions.CopyTo(copy, 0);
 
       return copy;
+    }
+
+    public Expression[] CopyExpressions(int startIndex, int length) {
+      if (IsEmpty) return EmptyExpressions;
+
+      var copy = new Expression[length];
+      CopyExpressionsTo(copy, startIndex, 0, length);
+
+      return copy;
+    }
+
+    public void CopyExpressionsTo(Expression[] destination, int? sourceIndex = null, int? destinationIndex = null, int? length = null) {
+      if (IsEmpty) return;
+
+      Array.Copy(this.expressions, sourceIndex ?? 0, destination, destinationIndex ?? 0, length ?? Count);
     }
 
     private int CalcDepth() {
       var maxDepth = 1;
-      for (var i = 0; i < State.Length; i++) {
-        var expression = State[i];
-        if (!expression.CanExpand) continue;
+      for (var i = 0; i < Count; i++) {
+        var expression = this.expressions[i];
+        if (!expression.IsProgram) continue;
         var expandExpression = (PushProgram)expression;
 
@@ -149 +251 @@
       // prevent too big string
       return this.TotalCount > 50
-        ? PrefixReduced + this.State.Length + PostfixReduced
-        : Prefix + string.Join(Delimiter, this.State.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
+        ? PrefixReduced + this.Count + PostfixReduced
+        : Prefix + string.Join(Delimiter, this.expressions.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
     }
 
     private int[] BuildTreeIndex() {
-      var local_treeIndex = new int[State.Length];
+      var local_treeIndex = new int[Count];
 
       var next = 1;
 
-      for (var i = State.Length - 1; i >= 0; i--) {
-        var subExpression = State[i];
+      for (var i = Count - 1; i >= 0; i--) {
+        var subExpression = this.expressions[i];
 
         local_treeIndex[i] = next;
 
-        if (subExpression.CanExpand) {
+        if (subExpression.IsProgram) {
           next += ((PushProgram)subExpression).TotalCount;
         } else {
@@ -176 +278 @@
       var hash = 19 * 31 + this.GetType().FullName.GetHashCode();
 
-      for (var i = 0; i < State.Length; i++) {
-        hash = hash * 31 + State[i].GetHashCode();
+      for (var i = 0; i < Count; i++) {
+        hash = hash * 31 + this.expressions[i].GetHashCode();
       }
 
@@ -195 +297 @@
       }
 
-      for (var i = 0; i < current.State.Length; i++) {
-        if (current.State[i].CanExpand)
+      for (var i = 0; i < current.Count; i++) {
+        if (current.expressions[i].IsProgram)
           continue;
 
-        var subExpression = current.State[i] as PushProgram;
+        var subExpression = current.expressions[i] as PushProgram;
 
         if (ReferenceEquals(target, subExpression)) {
@@ -231 +333 @@
       if (index == 0) return resolver(parent, parent, this, 0, parentIndex);
 
-      var min = State.Length - 1;
+      var min = Count - 1;
       var max = 0;
       var mid = (min + max) / 2;
@@ -243 +345 @@
 
       return TreeIndex[mid] == index
-          ? resolver(parent, this, State[mid], mid, parentIndex)
-          : (State[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
+          ? resolver(parent, this, this.expressions[mid], mid, parentIndex)
+          : (this.expressions[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
               this, resolver);
     }

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/RandExpressions.cs

@@ -69 +69 @@
 
       var size = (int)(interpreter.IntegerStack.Pop() % interpreter.Configuration.MaxPointsInRandomExpression);
-      var program = CodeGenerator.RandomExpandExpression(
+      var program = CodeGenerator.RandomProgram(
+        interpreter.PushProgramPool,
         size,
         interpreter.Random,

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/StatefulExpression.cs

@@ -2 +2 @@
   public abstract class StatefulExpression<T> : Expression {
     public readonly T State;
-
-    private int hashCode;
-    private int HashCode
-    {
-      get
-      {
-        if (hashCode == default(int)) hashCode = CalcHashCode();
-        return hashCode;
-      }
-    }
+    private int? hashCode;
 
     protected StatefulExpression(T state) {
@@ -34 +25 @@
     }
 
+    public bool Equals(StatefulExpression<T> obj) {
+      if (ReferenceEquals(this, obj))
+        return true;
+
+      if (GetType() != obj.GetType())
+        return false;
+
+      return ReferenceEquals(State, obj.State) ||
+             GetHashCode() == obj.GetHashCode();
+    }
+
     public override int GetHashCode() {
-      return HashCode;
+      if (hashCode == null) hashCode = CalcHashCode();
+      return hashCode.Value;
     }
   }

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Generators/CodeGenerator.cs

@@ -5 +5 @@
   using HeuristicLab.Core;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
   using HeuristicLab.Random;
@@ -18 +19 @@
   public static class CodeGenerator {
 
-    public static PushProgram RandomProgram(int maxPoints, IRandom random = null, IReadonlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
+    public static PushProgram RandomProgram(IManagedPool<PushProgram> pool, int maxPoints, IRandom random = null, IReadonlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
       var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);
 
-      return new PushProgram(code.ToArray());
-    }
-
-    public static PushProgram RandomExpandExpression(int maxPoints, IRandom random = null, IReadonlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
-      var program = RandomProgram(maxPoints, random, pushGpConfiguration, customExpressions);
-
-      return new PushProgram(program);
+      return PushProgram.Create(pool, code.ToArray());
     }
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Interpreter/IPushInterpreter.cs

@@ -7 +7 @@
 
   using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
 
   using Stack;
@@ -23 +24 @@
 
     IReadonlyPushConfiguration Configuration { get; }
+
+    IManagedPool<PushProgram> PushProgramPool { get; }
 
     bool IsNameQuoteFlagSet { get; set; }

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Interpreter/PushInterpreter.cs

@@ -2 +2 @@
   using System;
   using System.Collections.Generic;
+#if DEBUG
+  using System.Linq;
+#endif
   using System.Runtime.CompilerServices;
   using System.Threading;
@@ -7 +10 @@
   using HeuristicLab.Core;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Parser;
@@ -82 +86 @@
     }
 
+    public IManagedPool<PushProgram> PushProgramPool { get; set; }
+
     public IReadonlyPushConfiguration Configuration { get; protected set; }
 
@@ -249 +255 @@
     }
 
+#if DEBUG
+    private Expression last;
+    private bool DoStep() {
+      var expression = ExecStack.Pop();
+
+      if (ExecStack.Any(e => e == null)) {
+        throw new InvalidProgramException();
+      }
+
+      var succ = expression.Eval(this);
+      last = expression;
+
+      return succ;
+    }
+#else
     [MethodImpl(MethodImplOptions.AggressiveInlining)]
     private bool DoStep() {
       return ExecStack.Pop().Eval(this);
     }
+#endif
 
     private Task InterpretAsync() {

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushEncoding.cs

@@ -42 +42 @@
 
     public static PushProgram MapToPushProgram(this IntegerVector vector, IReadOnlyList<string> enabledExpressions) {
-      var expressions = vector
-        .Select(i => ExpressionTable.GetExpression(enabledExpressions[i]))
-        .ToArray();
+      //var expressions = vector
+      //  .Select(i => ExpressionTable.GetExpression(enabledExpressions[i]))
+      //  .ToArray();
+
+      var expressions = new Expression[vector.Length];
+      for (var i = 0; i < vector.Length; i++)
+      {
+        expressions[i] = ExpressionTable.GetExpression(enabledExpressions[vector[i]]);
+      }
 
       return new Expressions.PushProgram(expressions);

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushProblem.cs

@@ -12 +12 @@
   using HeuristicLab.BenchmarkSuite;
   using HeuristicLab.Data;
+  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
+
   using Instances;
   using Interpreter;
@@ -26 +28 @@
     private readonly PushConfiguration config;
     private PushInterpreterPool pool;
+    private ManagedPoolProvider<PushProgram> pushProgramPoolProvider;
 
     public PushProblem() {
       config = new PushConfiguration();
       pool = new PushInterpreterPool(config);
+
+      pushProgramPoolProvider = new ManagedPoolProvider<PushProgram>(1024);
+      pushProgramPoolProvider.InitDummyPartition(() => new PushProgram());
 
       InitEvents();
@@ -56 +62 @@
       pool = new PushInterpreterPool(config);
       Instructions = config;
+
+      pushProgramPoolProvider = new ManagedPoolProvider<PushProgram>(1024);
+      pushProgramPoolProvider.InitDummyPartition(() => new PushProgram());
 
       InitEvents();
@@ -404 +413 @@
 
     public override double Evaluate(Individual individual, IRandom random) {
+      if (DataBounds[0, 1] <= 0) return default(double);
 
       var program = individual.PushProgram(config.EnabledExpressions as IReadOnlyList<string>);
-      var expandExpression = new PushProgram(program);
-      var results = new List<double>();
+      var result = 0d;
 
       using (var interpreter = pool.GetInstance(random)) {
         for (var i = DataBounds[0, 0]; i < DataBounds[0, 1]; i++) {
-          var example = this.DataDescriptor.Examples[i];
+          var example = DataDescriptor.Examples[i];
 
           interpreter.BooleanStack.Push(example.InputBoolean);
@@ -417 +426 @@
           interpreter.FloatStack.Push(example.InputFloat);
 
-          interpreter.Run(expandExpression);
-
-          var diff = GetDiff(example.OutputInt, interpreter.IntegerStack, this.DataDescriptor.WorstResult, LongDiffer) +
-                     GetDiff(example.OutputFloat, interpreter.FloatStack, this.DataDescriptor.WorstResult, DoubleDiffer) +
-                     GetDiff(example.OutputBoolean, interpreter.BooleanStack, this.DataDescriptor.WorstResult, BooleanDiffer);
-
-          results.Add(diff);
+          using (interpreter.PushProgramPool = pushProgramPoolProvider.CreatePool()) {
+            interpreter.Run(program);
+          }
+
+          result += GetDiff(example.OutputInt, interpreter.IntegerStack, DataDescriptor.WorstResult, LongDiffer)
+                  + GetDiff(example.OutputFloat, interpreter.FloatStack, DataDescriptor.WorstResult, DoubleDiffer)
+                  + GetDiff(example.OutputBoolean, interpreter.BooleanStack, DataDescriptor.WorstResult, BooleanDiffer);
+
           interpreter.Clear();
         }
       }
 
-      return results.Count == 0 ? 0d : results.Average();
+      return result / DataBounds[0, 1];
     }
 

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Simplifier/RandomSimplifier.cs

@@ -1 @@
-namespace HeuristicLab.Problems.ProgramSynthesis.Push.Simplifier {
-  using System;
-  using HeuristicLab.Core;
-  using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
+//namespace HeuristicLab.Problems.ProgramSynthesis.Push.Simplifier {
+//  using System;
+//  using HeuristicLab.Core;
+//  using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
 
-  public class RandomSimplifier : ISimplifier {
-    public int Trys { get; set; }
+//  public class RandomSimplifier : ISimplifier {
+//    public int Trys { get; set; }
 
-    public PushProgram Simplify(PushProgram program, IRandom random, Predicate<PushProgram> isBetter) {
+//    public PushProgram Simplify(PushProgram program, IRandom random, Predicate<PushProgram> isBetter) {
 
-      if (program.TotalCount == 1) {
-        return isBetter(PushProgram.Empty) ? PushProgram.Empty : program;
-      }
+//      if (program.TotalCount == 1) {
+//        return isBetter(PushProgram.Empty) ? PushProgram.Empty : program;
+//      }
 
-      var copy = program.Copy();
-      var maxTries = Math.Min(Trys, program.TotalCount - 2);
-      var successfulRemoves = 0;
+//      var copy = program.Copy();
+//      var maxTries = Math.Min(Trys, program.TotalCount - 2);
+//      var successfulRemoves = 0;
 
-      for (var i = 0; i < maxTries; i++) {
-        var rndIndex = random.Next(1, program.TotalCount - 1 - successfulRemoves);
-        var node = copy.GetFromTree(
-          rndIndex,
-          (super, parent, child, childIndex, parentIndex) => new {
-            Super = super,
-            Parent = parent,
-            ChildIndex = childIndex,
-            ParentIndex = parentIndex
-          });
+//      for (var i = 0; i < maxTries; i++) {
+//        var rndIndex = random.Next(1, program.TotalCount - 1 - successfulRemoves);
+//        var node = copy.GetFromTree(
+//          rndIndex,
+//          (super, parent, child, childIndex, parentIndex) => new {
+//            Super = super,
+//            Parent = parent,
+//            ChildIndex = childIndex,
+//            ParentIndex = parentIndex
+//          });
 
-        var oldParentExpressions = node.Parent.State;
-        var newParentExpressions = RemoveAt(oldParentExpressions, node.ChildIndex);
-        var newParent = new PushProgram(newParentExpressions);
+//        var oldParentExpressions = node.Parent.State;
+//        var newParentExpressions = RemoveAt(oldParentExpressions, node.ChildIndex);
+//        var newParent = new PushProgram(newParentExpressions);
 
-        var superExpressions = node.Super == null ? copy.State : node.Super.State;
-        superExpressions[node.ParentIndex] = newParent;
+//        var superExpressions = node.Super == null ? copy.State : node.Super.State;
+//        superExpressions[node.ParentIndex] = newParent;
 
-        if (isBetter(copy)) {
-          successfulRemoves++;
-        } else {
-          superExpressions[node.ParentIndex] = node.Parent;
-        }
-      }
+//        if (isBetter(copy)) {
+//          successfulRemoves++;
+//        } else {
+//          superExpressions[node.ParentIndex] = node.Parent;
+//        }
+//      }
 
-      return copy;
-    }
+//      return copy;
+//    }
 
-    private static T[] RemoveAt<T>(T[] source, int index) {
-      var dest = new T[source.Length - 1];
-      if (index > 0)
-        Array.Copy(source, 0, dest, 0, index);
+//    private static T[] RemoveAt<T>(T[] source, int index) {
+//      var dest = new T[source.Length - 1];
+//      if (index > 0)
+//        Array.Copy(source, 0, dest, 0, index);
 
-      if (index < source.Length - 1)
-        Array.Copy(source, index + 1, dest, index, source.Length - index - 1);
+//      if (index < source.Length - 1)
+//        Array.Copy(source, index + 1, dest, index, source.Length - index - 1);
 
-      return dest;
-    }
-  }
-}
+//      return dest;
+//    }
+//  }
+//}