[xsl] Re: Re: String parsing in XSLT/XPath?

Subject: [xsl] Re: Re: String parsing in XSLT/XPath?
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Sat, 8 Sep 2001 04:35:47 -0700 (PDT)
> I doubt this is relevant, since you're dealing with addresses, which
> tend to be fairly short, but if you're dealing with long strings with
> lots of line breaks in them, then you may find it more efficient to
> use a divide-and-conquer approach whereby you split the remaining
> string. This has the advantage of limiting the depth of the recursion,
> and therefore the call stack, but the disadvantage of not being tail
> recursive and therefore not amenable to optimisation:

[nice divide and conquer code snipped]

> With this, you will have to add the <br /> to the end of the string
> yourself.
> If performance is an issue, I suggest that you try both of the
> templates on your particular data and processor to see which is best
> for you; if neither is significantly faster than the other, then use
> the one you feel most comfortable with maintaining.

Wow... I've been waiting for this moment to see someone on this list describe and
recommend divide and conquer recursive algorithms -- thank you, Jeni!

To the above description I can only add the following:

DvQ algorithms will be naturally the fastest on a parallel execution multiprocessor
environment. Virtually nothing has to be changed in them in order to execute each
"half processing" on an available processor.

I wish I would live long enough to see an XSLT processor that takes advantage in
this way of an available multi-processor configuration.

Not long ago I raised the question whether a special new XSLT instruction will be
necessary in order to specify that a contained sequence of XSLT instructions can be
performed in parallel. As there was no answer, I'm asking this question again.

Reading the working draft (3) of XSLT 2.0 it seems to me that such an explicit XSLT
instruction will not be necessary -- is this understanding right or wrong?

Another comment is on the fact that it is easy to write a DvQ algorithm for
replacing every occurrence of a ***single character*** within a string with another
string. However, it is very difficult and not at all trivial to produce a DvQ
algorithm for the solution of the general replace problem. I went through this
excersice a month ago and the resulting DvQ algorithm is outperforming the simple
sequential one-at-a time recursive algorithm only when considerably big number of
replacements have to be made. This is because quite complex synchronisation is
necessary. Even in this case it would be possible to have very efficient parallel
execution implementation of this algorithm. The same is not true for any
tail-recursive algorithm, as it is synonimous with sequential execution and having
more than one processor cannot help speeding up such sequential algorithm.

Apart from this extreme case, I've implemented DvQ algorithms for solving a number
of well-known problems (e.g. min/max, tokenisation, summation of calculated values,
reversing a string, pow(). ... etc.)  In most of this cases with the increase of
length of the input the performance of the DvQ algorithms becomes much better even
than that of a corresponding tail recursive implementation. Tail recursion is
extremely efficient only in cases when not many string parameters have to be passed
and when the algorithm is very simple, e.g. just write a number to the output tree.

Dimitre Novatchev. 

Do You Yahoo!?
Get email alerts & NEW webcam video instant messaging with Yahoo! Messenger

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

Current Thread