Opened 3 years ago

Closed 2 years ago

#2363 closed defect (done)

TreeSimplifier performance gets worse the deeper a tree is nested

Reported by: mkommend Owned by: mkommend
Priority: medium Milestone: HeuristicLab 3.3.12
Component: Problems.DataAnalysis.Symbolic Version: 3.3.11
Keywords: Cc:

Description (last modified by mkommend)

Currently the tree simplifier cannot simplify a tree with a tree depth above 40. At least not the tree I encountered (see attached sample file), because it was calculating more than 12 hours.

Attachments (1)

simplifier test.hl (747.3 KB) - added by mkommend 3 years ago.
File containing a tree that cannot be simplified

Download all attachments as: .zip

Change History (10)

Changed 3 years ago by mkommend

File containing a tree that cannot be simplified

comment:1 Changed 3 years ago by mkommend

  • Description modified (diff)

comment:2 Changed 3 years ago by mkommend

  • Status changed from new to accepted

comment:3 Changed 3 years ago by mkommend

  • Owner changed from mkommend to gkronber
  • Status changed from accepted to reviewing

r12227: Improved performance of symbolic expression tree simplifier.

The attached sample tree is now simplified in under a second. r12227 introduces ToArray calls in the linq queries (simplification of +, -, *, /), but I am still unsure why the laziness of the linq queries caused the slow performance.

comment:4 Changed 2 years ago by gkronber

r12262: implemented a fix for the performance problem without a call to .ToArray() (overwrites changes of r12227)

comment:5 Changed 2 years ago by gkronber

The reason for the performance problem is that we evaluate GetSimplifiedTree twice for the first element for the simplification of subtraction and division because of the call to .First() and .Skip(1). Additionally, this is only a problem if we have trees that are deeply nested to the left.

using System;
using System.Linq;
using System.Collections.Generic;

using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Problems.DataAnalysis.Symbolic;

public class MyScript : HeuristicLab.Scripting.CSharpScriptBase {
  public override void Main() {
    // type your code here
    var varNode = (VariableTreeNode)new HeuristicLab.Problems.DataAnalysis.Symbolic.Variable("a", "a").CreateTreeNode();
    varNode.VariableName = "a";
    varNode.Weight = 1.0;
    var treeNode = (ISymbolicExpressionTreeNode)varNode;
    for(int i = 0; i< 40; i++) {
      treeNode = MakeSum(2.0, treeNode);
    }
    
    var start = new StartSymbol().CreateTreeNode();
    var root = new ProgramRootSymbol().CreateTreeNode();
    root.AddSubtree(start);
    start.AddSubtree(treeNode);
    treeNode = root;
    
    SymbolicDataAnalysisExpressionTreeSimplifier simpl = new SymbolicDataAnalysisExpressionTreeSimplifier();
    var simplified = simpl.GetSimplifiedTree(treeNode);
    
    var simpleTree = new SymbolicExpressionTree(simplified);
    var tree = new SymbolicExpressionTree(treeNode);    
    vars["simpleTree"] = simpleTree;
    vars["tree"] = tree;
  }

  public ISymbolicExpressionTreeNode MakeSum(double x, ISymbolicExpressionTreeNode  tree) {
    var c = (ConstantTreeNode)(new HeuristicLab.Problems.DataAnalysis.Symbolic.Constant().CreateTreeNode());
    c.Value = x;
    var p = new Subtraction().CreateTreeNode();         // subtraction uses a skip(1)
    // this variant works 
    // p.AddSubtree(c);
    // p.AddSubtree(tree);

    // this variant is slow 
    p.AddSubtree(tree);
    p.AddSubtree(c);

    return p;
  }
}

comment:6 Changed 2 years ago by gkronber

  • Owner changed from gkronber to mkommend

comment:7 Changed 2 years ago by gkronber

r12264: fixed a bug in the simplifier introduced with r12262 (an a few minor code improvements)

Last edited 2 years ago by gkronber (previous) (diff)

comment:8 Changed 2 years ago by mkommend

  • Status changed from reviewing to readytorelease

Reviewed r12262 & r12264.

comment:9 Changed 2 years ago by mkommend

  • Resolution set to done
  • Status changed from readytorelease to closed

r12277: Merged r12227, r12262 and r12264 into stable.

Note: See TracTickets for help on using tickets.