XSLT: Riding the challenge: 2008年12月

Dimitre 的个人资料XSLT: Riding the challen...日志列表网络

工具

帮助

<< 第一页 < 上一页下一页 > 最后一页 >>

12月24日

Optimized Repetitive Prepends, Part III: Understanding the Solution

Technorati Tags: performance optimization, algorithms, algorithmic complexity, functional programming

In Part II of this post a solution was given to the problem presented in Part I:

"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?"

The solution is implemented within the function my:prepend-iter() that is defined in the following way:

<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>

The first argument passed to this function, pNumTimes, is the number of times to perform the prepend operation on the initial sequence pstartSeq, which is passed as the second argument.

The third argument has an auxiliary purpose. As its name, pInserts suggests, it contains the accumulation of all sequences that are to be prepended to pstartSeq.

The idea is to produce the final result only when pNumTimes is zero, using at this time the accumulated prepends in pInserts and the initial sequence pstartSeq.

The idea of the algorithm is to replace the repetitive prepend operations with repetitive append operations, which are carried out by the xslt processor with linear complexity.

We notice that:

y2s ++ y1s ++ xs =

reverse( reverse(y1s) ++ reverse(y2s) ) ++ xs (1)

Or in general, if we have N sequences:

y1s, y2s, ..., yNs

to be prepended to an initial sequence xs in that order,

yNs ++ yN-1s ++ ... y2s ++ y1s ++ xs =

reverse(reverse(y1s)++reverse(y2s) ++ ...

... ++ reverse(yNs) ) ++xs (2)

Remarkably, the argument of the outermost reverse() is a repetitive appends operation and it has only linear complexity with P1!

We have added N+1 reverse() operations, but each of them is of linear complexity, so the total complexity of implementing (2) is O(N).

Certainly, the function my:prepend-iter() we have demonstrated is a simplified case of the many different real world scenarios we may encounter that will require repetitive prepends. Nevertheless its use is sufficient to prove and demonstrate how such an O(N) algorithm can be constructed.

We could use essentially the same algorithm, with a modification that accepts as argument a function
next-prepend(), which produces the next sequence to be prepended. To signal the end of the repetitive prepend operation, we can use a convention that next-prepend() will indicate this by producing some special sequence, such as the empty sequence.

In case you may be wondering how can a function be passed as an argument to another function in XSLT, do read about FXSL.

12月22日

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

Technorati Tags: Performance optimization, algorithmic complexity, XPath sequence operations
Technorati Profile

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.

Performance Feat: Eliminate a dimension of complexity in XSLT Processor's repetitive prepends. Part I: The Problem.

Update: Minor code cleanup.

Prepending a list xs with a list ys to obtain the concatenation (of ys ++ xs ) of the two is usually a cheap operation which, when done non-destructively, requires only to copy the list ys to a new list y1s and link the last item of y1s to the head of xs.

Thus if we have to prepend K such lists:

y1s, y2s, ..., yks

starting with the prepend of y1s to xs, and prepending each of the following lists above to the result of the last prepend operation, the result will be a list consisting of the items of:

yks, ..., y2s, y1s, xs

in that order. Every list will be copied only once and the total operation of K prepends will require copying the items of all the lists. So, prepending a number of lists is a linear operation -- proportional to the total number of items in those lists.

On the other side, continuous appending of lists may be O(N^2) when done in a naive way, because the growing list will have to be copied again and again in each append operation.

In the XSLT 2.0 processors available today, the cost of repetitive prepending and appending are different than the above. I have studied two XSLT 2.0 processors, P1 and P2.

P1 optimizes repetitive appends, by achieving linear complexity. Its time complexity for repetitive prepending is O(N^2) -- square.

P2 doesn't optimize either way.

The simple transformation below:

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

      <xsl:variable name="vAppends" 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:iter($vRepetitions, ())"/>
      </xsl:variable>

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

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

            <xsl:sequence select=
             "if($pNumTimes gt 0)
                 then
                   my:iter($pNumTimes -1,
                           ($pstartSeq, $vAppends)
                           )
                 else
                   $pstartSeq
             "/>
      </xsl:function>
</xsl:stylesheet>

when run with P1 with different number of repetitions, takes the following times:

Appends	Time, ms	Remarks
100	42	Hundred appends.
1000	47	Thousand appends.
10000	85	Ten thousand appends
100000	458	One hundred thousands appends.
1000000	7141	One million appends.

We see that the claims of P1's linear or better performance are true.

P2 behaves much worse and has O(N^2) results:

Appends	Time, ms	Remarks
100	21	Hundred appends.
1000	7420	Thousand appends.
5000	38100	Failed after 38 seconds. Five thousand appends
10000	------	Failed. Ten thousands appends.

With repetitive prepends both P1 and P2 have square time complexity. This was tested with the following transformation:

<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="1000"/>

<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:iter($vRepetitions, ())"/>
   </xsl:variable>

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

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

       <xsl:sequence select=
        "if($pNumTimes gt 0)
            then
              my:iter($pNumTimes -1, insert-before($pstartSeq, 1, $vPrepends))
            else
              $pstartSeq
              "/>
</xsl:function>
</xsl:stylesheet>

P1's prepend results were the following:

Prepends	Time, ms	Remarks
100	62	Hundred prepends.
1000	1729	Thousand prepends.
10000	204682	Ten thousand prepends

P2's prepend results were again O(N^2) and much worse than P1's.

The problem I am trying to solve here is the following:

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?

P1's O(N^2) repetitive prepends performance has stayed the same for years so maybe its developer thought it could not be improved or an improvement would be not too important.

At first, it may seem that repetitive prepends are not so important (as repetitive appends -- the process via which we create every output). However, some of the most important data structures, such as the stack, often undergo a long series of prepends (the "push" operation). Another important use-case is any attempt to port an existing application that uses repetitive list prepends.

The answer to this question is contained in my next post.

"Real World Haskell" is a JOLT Finalist

Technorati Tags: Functional Programming, Haskell, Books

The book "Real World Haskell" has been nominated a JOLT Finalist.

I have been reading this book

in online form for the past month and got the hardcopy a few days ago. Two thirds through, I can confidently say that this is the best Haskell book I have read.

From the Jolt Awards Site:

"How are the winners selected?
Our judges not only examine the standard criteria of audience suitability, productivity, innovation, quality, ROI, risk and flexibility, but also seek to honor products that are ahead of the curve. Jolt-winning products are universally useful; are simple, yet rich in functionality; redefine their product space; and/or solve a nagging problem that has consistently eluded other products and books."