Project

Profile

Help

Bug #1974

Performance regression with tail expressions

Added by Michael Kay over 2 years ago. Updated about 2 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Byte code generation
Sprint/Milestone:
-
Start date:
2014-01-08
Due date:
% Done:

100%

Spent time:
-
Legacy ID:
Applies to branch:
Fix Committed on Branch:
Fixed in Maintenance Release:
Found in version:
9.5
Fixed in version:
9.5.1.6

Description

A "tail expression" here can be taken as a call on tail(), whether it is written as such, or in various other ways such as subsequence($x, 2), or remove($x,1), or $x[position() gt 1]. (This has nothing directly to do with tail call optimization, though the two things often appear in conjunction).

Tail expressions are handled specially in the interpreter to avoid repeated copying of the base sequence, to improve performance in the case where the code calls tail() as many times as there are items in the original sequence (typically in head-tail recursion). The normal implementation would be to create a Closure.

This special handling of tail expressions is happening only in interpreted code and not in generated bytecode. This results in a substantial performance regression (from 0.2 seconds to 25 seconds in the case submitted).

A possibly contributory factor is that any variable reference V used as the first operand of a filter expression V[P] is being marked as potentially indexable, even if P is a simple numeric predicate such as [1]. This results in the variable being materialized as an IndexedValue rather than a MemoClosure (see EnterpriseConfiguration.makeClosure()).

There is in fact a "TODO" in the code at LetExpressionCompiler line 209 that indicates the absence of this optimization in compiled code.

History

#1 Updated by O'Neil Delpratt over 2 years ago

  • Status changed from In Progress to Resolved

Bug now fixed and committed to subversion. It will be available in the next maintenance release.

#2 Updated by O'Neil Delpratt over 2 years ago

  • Status changed from Resolved to Closed
  • % Done changed from 0 to 100
  • Fixed in version set to 9.5.1.4

Bug fix applied in Saxon maintenance release 9.5.1.4

#3 Updated by O'Neil Delpratt about 2 years ago

  • Status changed from Closed to In Progress

This fix has introduced a bug in the LetExpressionCompiler which causes a crash in the QT3 test suite on test case Axes089. Reproduced when debugByteCode is enabled.

The code which relates to the following was reviewed and corrected:

                    return new SequenceExtent(
                            (SequenceExtent) base,
                            tail.getStart() - 1,
                            ((SequenceExtent) base).getLength() - tail.getStart() + 1).reduce();

#4 Updated by O'Neil Delpratt about 2 years ago

  • Status changed from In Progress to Resolved
  • Fixed in version deleted (9.5.1.4)

#5 Updated by O'Neil Delpratt about 2 years ago

Just to report that the following QT3 test case tail-006 was failing with an incorrect result. Bug fix applied in the LetExpressionCompiler.

This relates to the following code:

 if (base instanceof MemoClosure) {
   SequenceIterator it = base.iterate();
   base = SequenceTool.toGroundedValue(it);
}

#6 Updated by O'Neil Delpratt about 2 years ago

  • Status changed from Resolved to Closed
  • Fixed in version set to 9.5.1.6

As a reopened Bug the fixes were applied in Saxon maintenance release 9.5.1.6

Also available in: Atom PDF