Reviewing and optimizing underperforming XSLT

Question

At work I've recently been tasked with creating an XSLT to transform some XML as it is being genereated on a scanner. The point being to disgard some pages, that we are not interrested in for further processing, and this is what I've come up with.

    <?xml version="1.0" encoding="utf-8"?>
       <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
       xmlns:msxsl="urn:schemas-microsoft-com:xslt" exclude-result-prefixes="msxsl">

     <xsl:output method="xml" indent="yes"/>
     <xsl:strip-space elements="*"/>


    <!-- Do an indentity transform for all root nodes/attributes -->
    <xsl:template match="@* | node()">
      <xsl:copy>
        <xsl:apply-templates select="@* | node()"/>
      </xsl:copy>
    </xsl:template>

    <!-- Strip out the sheet with RETURN barcode by replacing it with nothing (blank template) -->
    <xsl:template match="Page[contains(Fields/Barcode, 'RETURN')]" />

    <!-- Check if there is a page containing RETURN in the barcode field.
       If yes append 'return' to all barcodes
       If no just copy everything -->
    <xsl:template match="Barcode">
       <xsl:choose>
         <xsl:when test="count(../../../Page[Fields/Barcode[contains(text(), 'RETURN')]]) > 0">
            <xsl:element name="Barcode">
              <xsl:value-of select="concat(ancestor::Page/Fields/Barcode, 'Return')"/>
            </xsl:element>
          </xsl:when>
        <xsl:otherwise>
         <xsl:copy>
           <xsl:apply-templates select="@* | node()"/>
         </xsl:copy>
       </xsl:otherwise>
     </xsl:choose>
    </xsl:template>
   </xsl:stylesheet>

Running on XML files with the following simplified structure. The actual files have around 100-3000 pages on avarage with some 40 fields under "Fields".

<Data>
  <Batch>
    <Page>
      <Fields>
        <Barcode>|||||||||||</Barcode>
      </Fields>
    </Page>
    <Page>
      <Fields>
        <Barcode>|RETURN|||||||||</Barcode>
      </Fields>
    </Page>
    <Page>
      <Fields>
        <Barcode>||5454|||||||||</Barcode>
      </Fields>
    </Page>
  </Batch>
</Data>

Its working but Im a bit worried about the "Barcode" template running too slow as it must be O(n^2). A quick profilling showed my concern to be correct.

Not enough rep to post pictures yet, but heres an image of the hot path during execution: http://postimage.org/image/hiyq2pii3/

As this will be running on somewhat limited hardware, i would like to ask if anyone has any suggestions for improvements?

Answer 1

I'd go with a <xsl:key ...> index, like so (at top level):

<xsl:key name="contains_RETURN" match="Barcode" use="contains(text(), 'RETURN')"/>

and then rewrite your hotspot to:

<xsl:when test="count(key('contains_RETURN', 'true')) > 0">
  ...
</xsl:when>

The idea is to parition Barcode nodes into 2 sets, the ones that contain 'RETURN' and the ones that don't. The key function as shown then evaluates to a nodeset that only contains Barcode nodes that contain 'RETURN' and hence count works as expected.

Answer 2

I wonder if your contains() should really be an "="? It's common to find people translating the english requirement "the element contains 'RETURN'" into a call on contains() when it should be a call on "=" (i.e. Fields/Barcode[.='RETURN']).

Either way, keys are the way to go, but the solution will be simpler if the test is '=' rather than contains().