December 22
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.
Tools 
Help
