BizTalk Utilities CV ,   Jobs ,   Code library
 
Home Page


Add/Edit your code items
Search the code library
Browse for the code library

XSLT

XSLT

XSLT Contents

Another way of avoiding XSLT processor crash
Re: DVC Algorithms in XSLT
trig functions in xslt
XSLT string Replace function
A Slide-In Menu made with XML/XSLT
What is SVG?
Family Tree maker
Alternative Ordering - ""Women and Children to the lifeboats first""
Restructuring flat delimited XML
Hex and Binary Conversions in XSLT - with Boolean math functions
Using XSLT to produce SVG (1)
Using XSLT to produce SVG (2)
Performance Tuning XSLT - Part 1
Performance Tuning XSLT - Part 2
Performance Tuning XSLT - Part 3
Performance Tuning XSLT - Part 4
Using XSLT to produce SVG (3)
XPath as parameters
Table with more than one column
Create an N-Column Table from XML node-set
 
 

<< XQuery.NET and XML >>

By Dimitre Novatchev
First Posted 01/07/2002
Times viewed 155

DVC Algorithms in XSLT

Summary This snippet shows an example of an even better technique to decrease the maximum call stack depth of recursive solutions using the Divide and Conquer approach. What Slavomir's snippet does with a maximum depth of 200 can be done with maximum depth of only 14.

Slawomir Tyszko wrote in http://www.topxml.com/snippetcentral/main.asp?view=viewsnippet&id=v20020106162513 > The way of avoiding XSLT processor crash presented in Dimitre > Novatchev's snippet (posted 24 March 2001) is very interesting, but > it can be used only in the simplest case - when recursion is used > just to count the number of iterations, and there is no passing of > data computed in a given step on to the following steps. Only in > such simple cases you can give up recursion completely and adopt > the solution based on a for-each loop, provided you'll be able to > find a node-set containing a very large number of nodes. > > But there are situations when you can't give up recursion, while > you still want to avoid XSLT processor crash due to excessive > recursion depth. > Take, for instance, the template named total-sales-value from > chapter 8 (9 in the second edition) of the Michael Kay's XSLT > Programmer's Reference. This recursive template calculates the > total sales value of books specified by the list parameter as sum > of the sales*price products for all book elements contained in the > input node-set. > In a case like this you can't replace recursion with a for-each > loop. > Luckily there is another, quite effective, way of avoiding the > crash, without relinquishing recursion, consisting in drastically > reducing recursion depth. > Suppose you've got 10000 items for which you want to compute sum of > 10000 sales*price products by way of recursion, which considerably > exceeds the depth of recursion allowed by your processor. In such a > case you can partition that node-set into e.g. 100 "chunks", each > chunk containing 100 nodes, and use two recursive templates instead > of just one. The template A would recursively compute the sum > inside chunks, while template B would recursively call template A > in order to process successive chunks. The combined maximum depth > of recursion will be only 200 (100+100) instead of 10000 (100*100). > Assuming that all XSLT processors allow recursion depth of at least > 1000, this method allows you to safely carry out processing that > would otherwise require recursion depth of 250000 (500*500). > Conceptually this is very simple, something similar to nested for > loops in a typical procedural programming language. It is still easy to reinvent the wheel in programming. The Divide and Conquer (DVC) pattern of algorithmic design has been well-known for many years, but only recently has been applied in XSLT programming. One can read about DVC for example in Robert Sedgewick's book "Algorithms and Data Structures with C++". I remember explaining the DVC in a post to the xsltalk group last year. I also sent several messages with concrete examples to the xsl-list. Once again, here's the explanation of DVC: Instead of applying a named-template recursively on every node of a node-list, following DVC we split the node-list into two parts and then apply the same procedure with each of this two parts, until there's only one node to operate on. In this simplest case the real processing is performed. The result of processing the two halves is combined as dictated by the problem at hand (e.g. if we are calculating the sum of products, then we will add together the results of processing of the two halves). Because the nodeset is halved every time the recursive template is called, it can be easily proven, that the maximum depth of the call stack when processing a nodeset of N nodes will be Log2(N). In the case of the specific problem that Slavomir's snippet is solving, Log2(10000) < 14. My original example for the xsl-list was in reversing a string. A 1MB string will be reversed by a DVC algorithm with a maximum call-stack depth of only 19. Another extremely important feature of the DVC pattern is that the DVC algorithms can very naturally be executed on parallel processor architecture, assigning the processing of each half of the input to a different processor. The code of the DVC solution of the same problem is presented in the code section. I ran it upon a 10000 nodes node-set. The processing time with my P3 800MHz 128MB PC was 3.785 seconds using MSXML3. Slavomir's solution took 12.748 seconds to run -- the DVD solution is 3.37 times faster. It is also necessary to notice, that the code for the DVC solution is simpler, because it requires just one template. The Conclusion: Whenever attempting to perform recursive processing on very big input, the solution that guarantees Log2(N) for the maximum depth of the call-stack, the solution that is conceptually simple and that is straightforward to parallelize -- this solution is DVC.

Additional information

Rate this article on a scale of 1 to 10 (0 votes, average 0)

Your vote :  

<< XQuery.NET and XML >>



Leave a comment for this article
Your name
Your email (optional)
Your comment
Optional: Upload an attachment
Enter the code shown:

 
 

    Email TopXML