Iterative evaluation of inherited attributes

[Jesper Öqvist]

Click here to view original trac ticket.

Recursive evaluation of inherited attributes has some performance penalty, and in some cases it can cause stack height problems.

It might be more efficient if inherited attributes used a loop to iterate over each ancestor until it finds one that can evaluate the attribute. This would require a separate method to test if a parent can define a value for the attribute.

[Jesper Öqvist]

Copied and edited the Trac description.

[Rudi Schlatte]

I think we're hitting this issue for large literal recursive data structures in source code; the point of breakage is an AST depth of about 15000. This is not a typical usage of our language (ABS; http://abs-models.org/) but it is encountered in generated code. How involved is the change to iteration? I've never needed to look at the insides of JastAdd2 before.

[Jesper Öqvist]

After a quick test with iterative inherited attribute evaluation in JastAddJ it seems like performance decreases a bit (~5%). The performance degradation is unfortunate, and probably unavoidable (extra method calls are needed to check each node first to see if it can define the inherited attribute, before calling the evaluator method).

[Niklas Fors]

rudis, another way is to increase the stack size using the flag -Xss to the JVM.

[Jesper Öqvist]

In case you are curious about how the iterative evaluator method looks, here is the template for it:

  /**
   * @apilevel internal
   */
  public #type Define_#name($ASTNode caller, $ASTNode child#inhParametersDeclTail) {
    ASTNode self = this;
    ASTNode parent = getParent();
    while (parent != null && !parent.canDefine_#name(self, caller#inhParametersTail)) {
      caller = self;
      self = parent;
      parent = self.getParent();
    }
$if(DebugMode)
    if (parent == null) {
      throw new RuntimeException("Trying to evaluate inherited attribute #name in detached subtree (parent == null)");
    }
$endif
    return parent.Define_#name(self, caller#inhParametersTail);
  }

  protected boolean canDefine_#name($ASTNode caller, $ASTNode child#inhParametersDeclTail) {
    return false;
  }

The Define_#name method is called when evaluating an inherited attribute. In the standard JastAdd implementation the default Define_ method for a node that does not have an equation for the corresponding attribute will simply call getParent().Define_(), causing one recursive invocation for each node on the path to some ancestor with an equation for the attribute. The canDefine_#name method is a helper method I added to check if a node can have an equation for the attribute (which is complicated to check, so I just make it return true for all nodes with any equation for the attribute). With the modified version a recursive call is only made to nodes that have at least one equation for the inherited attribute.

These extra method calls to canDefine_ are probably what is causing the slower evaluation. I was hoping for an improvement here. I think this modified version might be easier to debug because you can set a breakpoint after the loop to speed up the traversal past nodes without an equation. This is usually a really tedious process when debugging the standard JastAdd code because you have to use step over/step into interchangeably for each node on the path to the equation.

[Jesper Öqvist]

I did some more benchmarking and the reason my first results were slower appears to be unrelated to the iterative attribute evaluator. During testing I enabled remote debugging (jdwp) in the JVMs I was testing with to debug a silly error. I forgot to disable remote debugging when I measured runtime using the iterative evaluator.

With remote debugging disabled again the performance regression is gone. There might even be a slight performance increase, but in that case it is a small improvement.

[Jesper Mattsson]

We have also hit this issue recently - the AST depth in that case is ~5000. Are there any plans to push this solution to trunk?

[Jesper Öqvist]

Iterative inherited attribute evaluator

Rewrote inherited attribute evaluation to use an iterative evaluator. This reduces the stack depth needed to evaluate inherited attributes in large trees.

fixes #91 (bitbucket)

→ <<cset 47c9cf6309e9>>