Re: Re: reverse() template (Was: RE: XSL output method

Francis Norton wrote:

> Dimitre Novatchev wrote:
> > 
> > 
> > Here are two templates for reversing a string. The first is much faster and more
> > straightforward, the second will almost never cause an XSLT processor to crash
due
> > to deep recursive processing (it has a maximum recursion depth of only 20 for
> > reversing a 1MB long string):
> > 
> 
> A logarithmic decrease in stack depth, very nice. How great is the
> difference in performance?


Surprisingly enough, the "least recursive" version fares pretty well -- I expected
it to be grossly inefficient, but this isn't the case.

I compared the speed of the two kinds of transformations on an 350MHz 64MB RAM
Pentium, doubling the string length from 100 to 3200.

Here are the results in milliseconds:

Length        Simple        Least Recursive
-------------------------------------------
 100              37                    58
 200              85                   117
 400             199                   235
 800             522                   469
1600            1460                   927
3200           35000                  1870


I can explain the extremely large times for the first algorithm with the inefficient
way MSXML3 handles recursion -- most probably virtual memory had to be used and most
probably there was trashing.

Otherwise both algorithms must be almost linear, the second one a little bit more
complex.

Cheers,
Dimitre Novatchev.

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list