[
Lists Home |
Date Index |
Thread Index
]
Tatu,
I suspect this is one of the reasons why such things as the
development of intermediate node trees is such a big facet of XSLT 2.0
(and why x:node-set() is implemented in just about every 1.0
implementation) - these make it permissable to effectively optimize
recursions.
-- Kurt
On 3/26/06, Tatu Saloranta <cowtowncoder@yahoo.com> wrote:
> --- Stefan Tilkov <info@tilkov.com> wrote:
>
> > On reflection, that sounds like something I did not
> > want to say. I
> > meant that the use of recursion is perfectly fine in
> > languages that
> > are designed to support it properly.
>
> I think there are both cases where using recursion
> would generally be a bad idea (cases where there are
> solutions with lower complexity; such as many toy
> examples used for teaching recursion), and many others
> were recursion may be a reasonable choice (like
> typical tree/graph traversing use cases).
> In latter category, choice has to do with things
> already mentioned (if and how efficiently
> language/runtime can optimize tail recursion; are
> there some extra penalties for deep call stacks etc),
> as well as clarity of code. But for former category it
> doesn't really matter: there's no way to fix an
> algorithmically bad solution to scale well.
>
> Recursion solutions are often cleaner, and I do not
> claim that all uses of recursion are bad. For
> tree/graph traversal they are usually good starting
> points.
>
> Regarding xslt, what I have always wondered is whether
> there are many (enough?) cases where having stateful
> alternative (with real variables or such to store
> state) would have benefits: it seems as if computing
> certain things just once (or cumulatively) could yield
> significant improvements.
> For example: instead of computing counts of nodes in a
> node set consisting of all previous siblings of
> certain element type, keeping track of number of such
> elements encountered. Keeping track would require bit
> more code (or new constructs to simplify it), but
> would seem likely to perform faster.
> Supporting state would be against XSL as a language
> (wouldn't it?), and would also reduce many
> optimization possibilites (document would have to be
> traversed and processed in a specific order, no
> parallel processing of sub-trees etc). But for some
> transformations it'd be much faster, possibly
> including lower complexity.
> On one hand, it is certainly true that higher level
> abstractions give more optimization.
> But on the other hand, such optimizations can not
> compete with better algorithmic solutions: that is,
> even if computing node sets and their counts is as
> efficient as it could be, it still wouldn't match
> performance of low-overhead counters.
>
> So would there perhaps be also room for other xml
> transformation approaches, besides dominant functional
> alternatives? (but above 'wrap your own SAX-based
> solution' level)
> Anyone have links to papers on such alternatives? (the
> one regarding SAX event reuse was a very interesting
> one)
>
> -+ Tatu +-
>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam? Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
>
> The list archives are at http://lists.xml.org/archives/xml-dev/
>
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://www.oasis-open.org/mlmanage/index.php>
>
>
--
Kurt Cagle
http://www.understandingxml.com
|
