Performance Feat: Eliminate a dimension of complexity in XSLT Processor’s repetitive prepends. Part II: The Solution.

Update: Minor code cleanup (using better names now).

In my previous post I defined the problem of improving the quadratical performance of an XSLT processor P1 when performing repetitive prepends to a sequence, while having an excellent linear repetitive appends performance.

The question asked was:

"Can we implement an algorithm for repetitive prepends that will be run by P1 in linear time, in addition to its excellent linear performance of repetitive appends?"

This transformation produces the result of repetitive prepends:

<xsl:stylesheet version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:my="my:namespace"
  exclude-result-prefixes="my"
>
      <xsl:output method="text"/> 

      <xsl:variable name="vRepetitions" as="xs:integer"
       select="1000000"/> 

      <xsl:variable name="vPrepends" as="element()*">
       <my:node/><my:node/><my:node/><my:node/><my:node/>
       <my:node/><my:node/><my:node/><my:node/><my:node/>
      </xsl:variable>

      <xsl:template match="/">
        <xsl:variable name="vNodes" as="element()*">

          <xsl:sequence select=
              "my:prepend-iter($vRepetitions, (), ())"/>
        </xsl:variable>

        <xsl:value-of select="name($vNodes[last()])"/>

        <xsl:text>, </xsl:text>

        <xsl:value-of select="count($vNodes)"/>
      </xsl:template>

      <xsl:function name="my:prepend-iter">
        <xsl:param name="pNumTimes" as="xs:integer"/>
        <xsl:param name="pstartSeq" as="element()*"/>
        <xsl:param name="pInserts" as="element()*"/>

          <xsl:sequence select=
           "if($pNumTimes gt 0)
               then
                 my:prepend-iter
                        ($pNumTimes -1,

                         $pstartSeq,
                         ($pInserts, reverse($vPrepends) )
                         )
               else
                 (reverse($pInserts), $pstartSeq)
            "/>
      </xsl:function>
</xsl:stylesheet>

When run with the P1 XSLT processor, the results are:

 

Prepends

Time, ms

Speedup
tNonOpt / tOpt

Remarks

100

42

1.47

Hundred prepends.

1000

67

25

Thousand prepends.

10000

145

1411

Ten thousand prepends

100000

932

~ 16000

Estimated speedup for one hundred thousand prepends.

1000000

11666

~ 160000

Estimated speedup for one million prepends.

So, we see that the repetitive prepends have been carried out with linear complexity! We achive a speedup that can reach thousands and even hundred of thousands times!

When carried out with P2, the time complexity remains quadratical, however the actual results are two times faster than with the non-optimized algorithm.

I will explain the algorithm implemented in the above transformation, in Part III of this post.

Advertisements
This entry was posted in Performance Optimization. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s