Changeset 14746 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs

Timestamp:

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

Author:

pkimmesw

Message:

#2665 PooledPushProgram reduces memory usage and increases performance

File:

• branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs (modified) (12 diffs)

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);
     }